UIINFNP009 Seminar on Formal Languages I

Faculty of Philosophy and Science in Opava
Winter 2024
Extent and Intensity
0/2/0. 4 credit(s). Type of Completion: z (credit).
Teacher(s)
RNDr. Radka Poláková, Ph.D. (seminar tutor)
RNDr. Šárka Vavrečková, Ph.D. (seminar tutor)
Guaranteed by
RNDr. Radka Poláková, Ph.D.
Institute of Computer Science – Faculty of Philosophy and Science in Opava
Timetable of Seminar Groups
UIINFNP009/A: Thu 18:05–19:40 B1, R. Poláková
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 seminar is designed to complement and deepen the knowledge of the lecture "Chapters from the theory of formal languages and automata I". It is recommended to take it at the same time as the lecture.
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-1-284-07724-7. info
  • HOPCROFT, John E, Rajeev MOTWANI and Jeffrey D. ULLMAN. Introduction to automata theory, languages, and computation. 3rd ed. New international ed. Harlow: Pearson Addison-Wesley, 2014. ISBN 978-1-292-03905-3. info
  • MEDUNA, A. Automata and Languages: Theory and Applications. Springer, London, 2000. info
  • ROZENBERG, Grzegorz and Arto SALOMAA. The mathematical theory of L systems. New York: AcademicPress, 1980. ISBN 0-12-597140-0. info
  • ROZENBERG, Grzegorz and Arto SALOMAA. The mathematical theory of L systems. New York: AcademicPress, 1980. ISBN 0-12-597140-0. info
Teaching methods
Interactive lecture
Discussion
Assessment methods
Seminar work. Mandatory participation in the exercises min. 75%.
Language of instruction
Czech
The course is also listed under the following terms Winter 2021, Winter 2022, Winter 2023.
  • Enrolment Statistics (recent)
  • Permalink: https://is.slu.cz/course/fpf/winter2024/UIINFNP009