This course is a continuation of the course Theoretical Computer Science I. The students are introduced to further minimization algorithms of finite automata. Furthermore, they study the class of context-free languages, i.e., the mathematical model of programming languages generated by context-free grammars. They also study pushdown automata and they are introduced to the practical use of these models to syntactical analysis as well as the main compilers' properties.
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.
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.