SUBJECT

Title

Formal Languages

Type of instruction

lecture + practical

Level

bachelor

Part of degree program
Credits

2+2

Recommended in

Semester 2

Typically offered in

Spring semester

Course description
  • 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.

Readings
  • 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)