Upon successful completion of the course, students will be able to:
1. Understand the function of context-free grammars and pushdown automata through their theoretical description and use this description in theoretical exercises. They will also be able to understand the mathematical nature of these models and prove their properties using classical algebraic and logical proof techniques.
2. In conjunction with the prerequisite knowledge of the course "Theoretical Informatics I", students will be able to understand the concept of hierarchy of classes of typical languages in terms of their structural complexity.
3. In addition, they will be able to understand how to study a class of typical language e.g. determine closure properties of the class, and also how to study the properties of the theoretical models that define the languages of the class, e.g. their distinction in machines that produce languages and machines that recognize languages, their ability to be minimized in order to improve their performance in potential applications.
4. Finally, students will be able to understand the utility of mathematical modeling and study of processes and phenomena that we encounter in Computer Science.
Course Content (Syllabus)
Complete minimization of finite automata. Context-free grammars. Syntactic trees. Context-free languages. Properties of context-free languages. Relation among recognizable and context-free languages. Pushdown automata.
Course Bibliography (Eudoxus)
- Στοιχεία Θεωρίας Υπολογισμού, H.Lewis, Χ.Παπαδημητρίου, Κριτική, 2005, Αθήνα.
- Εισαγωγή στη Θεωρία Υπολογισμού, M. Sipser, Παν/κές Εκδόσεις Κρήτης, 2007 έδοση 2009.
Additional bibliography for study
- John Hopcroft, Rajeev Motwani, Jeffrey Ullman, Introduction to Automata Theory,
Languages, and Computation, Addison-Wesley, 3rd edition 2007.
- Juraj Hromkovic, Theoretical Computer Science, Texts in Theoretical Computer
Science, EATCS Series, Springer, 2004.
- Harry Lewis, Christos Papadimitriou, Elements of the Theory of Computation,
Prentice-Hall Inc., 2nd edition 1998.
- Grzegorz Rozenberg, Arto Salomaa eds., Handbook of Formal Languages, volumes 1-3,
Springer-Verlag, Berlin, 1997.