Credit points: 3.0
Phrase structure grammars, the Chomsky hierarchy of languages, type-0 grammars and Turing machines, context-sensitive languages and linearly bounded automata, context free languages, characterizations, homomorphism theorems and subfamilies, push-down automata - various models, stack automata. Operations on languages,decision problems, time and tape bounded Turing machines, complexity hierarchies of languages, time and space bounds for recognizing families of languages, complexity of problems informal languages.