FORMAL LANGUAGES AND AUTOMATA THEORY

This book discusses the most significant features of formal language theory: the classes of the Chomsky hierarchy and the corresponding classes of automata. There are three descriptions of the regular languages given: regular grammars, regular expressions and finite automata (both deterministic and nondeterministic versions). The equivalence of these descriptions are proven. Moreover, finite state transducers, for example, Mealy and Moore automata are described. Linear languages are presented. The class of context-free languages is also widely used, Chomsky normal form and Bar-Hillel pumping lemma is presented. This class is also characterized by the class of pushdown automata. The parsing problem is solved by CYK and Earley algorithms. Context-sensitive languages form a much wider class. Kuroda normal form is proven for this class. Linear-bounded automata is shown. Turing machines and the class of recursively enumerable languages, as well as, the class of recursive languages are presented. Finally, closure properties of the mentioned classes are also proven.