CSC 551: Automata, Calculability and Formal Languages

Finite state automata and regular expressions - Regular sets - the Pumping lemma - Context-free grammars and derivation trees - Chomsky and Greiback normal forms - Context-free languages - Recognizers - Turing machines - recursive and recursively innumerable languages - Decidability problems - The halting problem - Rice’s theorem and Chomsky hierarchy.