Elementary concepts of formal language theory( alphabet, word, language, operations on languages). Methods of language description using finite amount of information. Production systems, formal grammars, languages generated by them. Classification of grammars and languages, Chomsky hierarchy theorem. Extension theorems, normal forms. Versions of finite automata and their equivalence. Characterization of regular languages by finite deterministic automaton. Small Bar-Hillel lemma, Myhill-Nerode theorem, Kleene theorem. Characterization of context-free languages by push-down automaton, deterministic context-free languages. Derivation trees, Bar-Hillel lemma. Strategies of parsing, LL(k) and LR(k) grammars. Some decidable problems of formal language theory.