Fundamentals of Theory of Computation I

Lecture: Wednesday 8:15 - 9:45, room 2.502
Practice class:
- Wednesday 12:15 - 13:45, Chemistry building, room 115
- Monday 14:15 - 15:45, room 1.819

Lecturer: Tamás Lukovszki

Content:

Basic concepts, grammars, languages, Chomsky hierarchy. Finite automata (FA) (deterministic, nondeterministic). DFA minimization. Regular expressions, regular grammars. Algorithmic problems of regular languages (membership, emptyness, equality, disjointness). Closure properties. Pumping lemma for regular languages. Context-free (CF) languages. Derivation tree, unambiguous grammar. Chomsky and Greibach normal form. Pumping lemma for CF languages. Pushdown automata. Deterministic CF languages. Algorithmic problems of CF languages. Applications of formal languages: lexical analysis and parsing. Leftmost derivation in CF grammars. Buttom-up and top-down parsing.

Requirements, evaluation:

1. Active partitipation and work in pactice classes: solving and discussing excercises
2. Successful exams (grade is computed as average of 2 exams)

Important dates:

- midterm test/exam (written): 2024-10-16
- final test/exam (written): 2024-11-27
- repeat exam (second trial exam in case of unsuccessful exam): 2024-12-04

Slides:

-	foliák
1. Introduction	PDF

Literature:

- M. Sipser, Introduction to the Theory of Computation, 3rd edition, Cengage, 2012.
- J. E. Savage, Models of Computation: Exploring the Power of Computing, Brown University, 1998. https://cs.brown.edu/people/jsavage/book/pdfs/ModelsOfComputation.pdf
- J.E. Hopcroft, R. Motwani, J.D. Ullman: Introduction to Automata Theory, Languages, and Computation, 3rd ed. Pearson Education Ltd., 2014.
- A. Salomaa, G. Rozenberg (eds.): The Handbook of Formal Languages I., II., Springer Publishing Company, 1997.
- Arto Salomaa: Formal Languages, Academic Press, 1973.