UINA328 Chapters in Theory of Formal Languages I

Faculty of Philosophy and Science in Opava
Winter 2021
Extent and Intensity
2/0/0. 4 credit(s). Type of Completion: zk (examination).
Teacher(s)
doc. RNDr. Lucie Ciencialová, Ph.D. (lecturer)
Guaranteed by
doc. RNDr. Lucie Ciencialová, Ph.D.
Institute of Computer Science – Faculty of Philosophy and Science in Opava
Course Enrolment Limitations
The course is also offered to the students of the fields other than those the course is directly associated with.
fields of study / plans the course is directly associated with
Course objectives
The content of the course is the theory of Lindenmayer systems.
Learning outcomes
The student will be able to:
- define and describe the different types of Lindenmayer systems;
- create examples of Lindenmayer systems having certain properties.
Syllabus
  • 1. Lindenmayer systems. Introduction, motivation.
    2. 0L systems. Generative power. Closure properties.
    3. Deterministic 0L systems. Developmental sequences.
    4. Growth function.
    5. Adult languages. Their relation to context free languages.
    6. Extended 0L systems, closure properties, relation to Chomsky hierarchy of languages.
    7. Table 0L systems. Complexity results.
    8. Interactive L systems. Influence of the interaction to the development of the system.
    9. Regeneratiom in IL systems.
    10. Program environments for development on the basis of L systems.
Literature
    required literature
  • HERMAN, Gabor T, Grzegorz ROZENBERG and Aristid LINDENMAYER. Developmental systems and languages. New York: American Elsevier Pub. Co, 1975. ISBN 978-0-444-10650-6. info
    recommended literature
  • LINZ, Peter. An introduction to formal languages and automata. Sixth edition. Burlington, MA: Jones, [2017]. ISBN 978-128-4077-247.
  • ROZENBERG, Grzegorz and Arto SALOMAA. The mathematical theory of L systems. New York: AcademicPress, 1980. ISBN 0-12-597140-0. info
Teaching methods
nteractive lecture
Discussion
Assessment methods
Seminar work
Language of instruction
English
Further comments (probably available only in Czech)
The course can also be completed outside the examination period.
Teacher's information
Written exam - Theory including the proofs of the theorems, exersices
The course is also listed under the following terms Winter 2017, Winter 2018, Winter 2019, Winter 2020, Winter 2022, Winter 2023, Winter 2024.
  • Enrolment Statistics (Winter 2021, recent)
  • Permalink: https://is.slu.cz/course/fpf/winter2021/UINA328