UIN3028 Chapters in Theory of Formal Languages I

Faculty of Philosophy and Science in Opava
Winter 2017
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
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
Czech
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 1993, Winter 1994, Winter 1995, Winter 1996, Winter 1997, Winter 1998, Winter 1999, Winter 2000, Winter 2001, Winter 2002, Winter 2003, Winter 2004, Winter 2005, Winter 2006, Winter 2007, Winter 2008, Winter 2009, Winter 2010, Winter 2011, Winter 2012, Winter 2013, Winter 2014, Winter 2015, Winter 2016, Winter 2018, Winter 2019, Winter 2020, Winter 2021, Winter 2022, Winter 2023, Winter 2024.
  • Enrolment Statistics (Winter 2017, recent)
  • Permalink: https://is.slu.cz/course/fpf/winter2017/UIN3028