Theory of Languages and Automata

The notion of formal language. Operations with formal languages.
Regular languages. Specification of languages. Rewriting systems and
grammars. Chomsky's classification of grammars.
Finite automata: dterministic, nondeterministic. Languages recognized
by finite automata. Kleene's Theorem.
Automata morphisms, minimization of finite automata. Finite automata
and regular grammars.
Context-free grammars. Pushdown automata. Languages generated by
context-free grammars and recognized by pushdown automata.
Context-sensitive languages generated by context grammars and
recognized by linear bounded automata. Turing machines. Languages
accepted and recognized by Turing machines (recursively enumerable and
recursive languages). Post's Theorem. Algorithmic solvability.
Church-Turing thesis.
Further topics in the area of finite automata (2-way automata,
automata with weights, ...)
Further topics in the area of context-free languages (deterministic
context-free languages, ...)
Tree languages
Relation of languages, automata, and logical theories
Further selected topics