Study of Automata.
Finite Automata and Regular Languages
- Finite Automaton
- Regular Expression
- Kleene’s Theorem
- Pumping Lemma for Regular Languages
- Myhill-Nerode Theorem
- DFA Minimization
- Closure Properties of Regular Languages
- Two-way Finite Automata
Context-Free Languages
- Context-Free Grammars
- Derivation Trees
- Pushdown Automaton
- Equivalence of CFGs and PDAs
- Chomsky Normal Form
- Greibach Normal Form
- Pumping Lemma for Context-Free Languages
- Ogden’s Lemma
- Parikh’s Theorem
- Context-Free Language
Context-Sensitive Languages
Turing Machines and Computability
- Turing Machine
- Multitape Turing Machines
- Nondeterministic Turing Machines
- Church-Turing Thesis
- Universal Turing Machine
- Decidable and Recognizable Languages
- Halting Problem
- Rice’s Theorem
- Reducibility and Many-One Reductions
- The Recursion Theorem
- Post Correspondence Problem