UIN3129 Chapters in Formal Language Theory II

Faculty of Philosophy and Science in Opava
Summer 2025
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 course extends the knowledge of the theory of formal languages with information about controlled-derivation grammars and models of cooperating grammars.
Learning outcomes
The student will be able to:
- define Matrix grammars, Programmed grammars, Random content grammars and cooperating grammars;
- describe the relationship of controlled derivation grammars to L systems and Chomsky hierarchy grammars;
- analyze and create examples of grammars;
Syllabus
  • 1. Matrix grammars. 2. Programmed grammars. 3. Random content grammars. 4. The relation of controlled derivation grammars to L systems and Chomsky hierarchy grammars. 5. Cooperating grammars.
Literature
    required literature
  • MEDUNA, Alexander and Petr ZEMEK. Regulated grammars and automata. New York: Springer, 2014. ISBN 978-1-4939-0368-9. info
    recommended literature
  • DASSOW, Jürgen a Gheorghe PAUN. Regulated rewriting in formal language theory. Berlin: Springer, 1989.
  • ROZENBERG, G., T. BÄCK, J.N. KOK. Handbook of Natural Computing. Springer, New York, 2012.
  • Bel-ENGUIX, G. Natural Language processing and biological methods. In Encyclopedia of Artificial Intelligence (3 Volumes) RABUNAL, J.R., DORADO, J., PAZOS, A. (eds). IGI Global, London, 2009
  • PAUN, Gh., A. SALOMAA (eds). Grammatical Models of Multi-Agents Systems. Gordon and Breach, Amsterdam, 1999
  • 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
Teaching methods
Interactive lecture
Discussion
Assessment methods
Seminar work
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 Summer 2016, Summer 2017, Summer 2018, Summer 2019, Summer 2020, Summer 2021, Summer 2022, Summer 2023, Summer 2024.
  • Enrolment Statistics (Summer 2025, recent)
  • Permalink: https://is.slu.cz/course/fpf/summer2025/UIN3129