Automata Theory, Languages and Computations 1000-215aJAO

1.The rudiments of formal language theory: words, languages, star operation, regular expressions, formal grammars.
2.Finite automata: Kleene theorem; deterministic vs. nondeterministic automata, Myhill-Nerode theorem and minimal automata; application of finite automata to pattern matching problem.
3.Context-free languages: grammars and their normal forms; recognition of the context-free languages; pumping lemmas; pushdown automata.
4.The Chomsky hierarchy: classification of grammars, context-sensitive languages.
5.Models of computation: Turing machines and their variants, random access machine.
6.Computability: universal Turing machine, undecidability of the halting problem, other undecidable problems, computable vs partial computable functions, Turing-Church thesis.
7.Complexity: basic concepts and basic complexity classes (L,P,NP, PSPACE); NP complete problems, Cook theorem; application of hard problems in cryptography; complexity of parallel computation.