SUBJECT
Formal Languages
lecture + practical
bachelor
2+2
Semester 2
Spring semester
-
Fundamental notions of formal language theory (alphabet, word, language, language family, operations on words and languages).
-
Constructive methods of description of languages (pure listing, logical formula, structural recursion, partial decision algorithms, enumeration, mathematical machines, formal grammars).
-
The generative grammar, examples, classification of grammars and languages. Restricted versions of grammars, normal forms.
-
The Chomsky-hierarchy of languages, the limits of description by grammars, the Church-thesis.
-
Relation between Chomsky-families and language operations.
-
The word-problem and its decision on Chomsky-families.
-
Finite automaton models, their equivalence, examples.
-
Type 3 languages and their related automata. Properties of type 3 languages.
-
Synthesis, analysis and minimization of automata. Applications of finite automata.
-
Context-free languages, their properties. Practical tools for definition of programming languages (BNF, EBNF, syntax-graphs).
-
Push-down automata. Relation between push-down automata and context-free languages.
-
The general top-down and the bottom-up parsing with back-tracking, Deterministic parsers.
-
Arto Salomaa: Formal Languages (Academic Press, 1973)
-
J.E. Hopcroft, J.D. Ullman: Introduction to Automata Theory, Languages Computation (Addison Wesley, 1979)
-
A. V. Aho, R. Sethi, J. D. Ullman: Compilers - Principles, Techniques, and Tools (Addison Wesley, 1986)
-
Révész György: Bevezetés a formális nyelvek elméletébe (Akadémiai Kiadó, 1979)
-
Fülöp Zoltán: Formális nyelvek és szintaktikus elemzésük (Polygon jegyzettár, 1999)
-
Hunyadvári László: Formális nyelvek (2006, elektronikus jegyzet)
Recommended literature:
-
Csörnyei Zoltán: Bevezetés a fordítóprogramok elméletébe, I., II. (Nemzeti Tankönyvkiadó, Budapest, 1996)
-
Demetrovics János, Jordan Denev, Anton Pavlov: A számítástudomány matematikai alapjai (Tankönyvkiadó, Budapest, 1985)
-
M. A. Harrison: Introduction to Formal Language Theory (Addison Wesley, 1978)
-
J. E. Hopcroft, A. V. Aho: Introduction to Automata Theory, Languages, and Computation (Addison Wesley, 1979)
-
Salomaa, G. Rozenberg (Editors): The Handbook of Formal Languages I., II. (Springer Publishing Company, 1997)