Summary

The theory of automata and formal languages is one of the classical fields of theoretical computer science. It forms the basis for the development of programming languages and their analysis and translation. The roots of this theory go back to combinatorics (A. Thue, E. Post), computability (A. Turing), linguistics (N. Chomsky), and biology (A. Lindenmayer). As a formal language is just a set of words, there are potentially many different ways for describing a formal language. Here we will focus on a generative approach using formal grammars and on an analytical approach using various types of automata. A grammar tells us in detail how to generate all the words of a language, while an automaton processes an input word, accepting it if and only if it belongs to the language of that automaton. Different types of grammars and automata yield different classes of languages. Here the classes REG of regular languages, CFL of context-free languages, CSL of context-sensitive languages, and RE of recursively enumerable languages are of particular interest, as they form the famous Chomsky hierarchy. We will study various characterizations of these classes by grammars and different types of automata, consider the closure properties of these classes under various language operations, and study algorithmic problems (decision problems) for them like the membership problem, the emptiness problem, and the finiteness problem.