UINA328 Chapters in Theory of Formal Languages I

Faculty of Philosophy and Science in Opava
Winter 2019
Extent and Intensity
2/0/0. 4 credit(s). Type of Completion: zk (examination).
Teacher(s)
prof. RNDr. Alice Kelemenová, CSc. (lecturer)
Guaranteed by
prof. RNDr. Alice Kelemenová, CSc.
Institute of Computer Science – Faculty of Philosophy and Science in Opava
Prerequisites (in Czech)
TYP_STUDIA(N)
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
1. Lindenmayer systems: introduction and biological motivation. 2. 0L systems: generative power, closure properties. 3. D0L systems: growth function. 4. Adult and stable languages: relation to context free languages. 5. E0L systems: closure properties, relation to the sequential grammars 6. T0L systems: hierarchy 7. IL systems: different interaction
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
    Herman, G. T., Rozenberg, G.: Developmental Systems and Languages. North-Holland, Amsterdam, 1975
    Kari, L., Rozenberg, G., Salomaa, A.: L systems. In: Handbook of formal languages. (G. Rozenberg, A. Salomaa, eds.) Vol 1. Springer, Berlin, 1997, 253-324
    Rozenberg, G., Salomaa, A.: The Mathematical Theory of L Systems. Academic Press, New York, 1980
Teaching methods
Interactive lecture
Lecture with a video analysis
Assessment methods
Exam
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 2020, Winter 2021, Winter 2022, Winter 2023, Winter 2024.
  • Enrolment Statistics (Winter 2019, recent)
  • Permalink: https://is.slu.cz/course/fpf/winter2019/UINA328