Theory of Computation

Unit 1: Languages

• Introduction to Alphabets
• Introduction to String
• Introduction to Language
• Basic operations on language
• Concatenation
• Union Kleene star

Unit 2: Regular Expressions and Finite Automata

• Regular expressions
• Deterministic finite automata (DFA)
• Non-deterministic Finite Automata (NFA)
• relationship between NFA and DFA
• Transition Graphs (TG)
• properties of regular languages
• The relationship between regular languages and finite automata
• pumping lemma
• Kleene’s Theorem

Unit 3: Context-Free Language(CFL) and PDA

• Context-Free Grammar (CFG)
• Deterministic and non-deterministic Pushdown Automata (PDA)
• Relationship between CFG and PDA
• Parse trees
• Leftmost derivation
• Ambiguities in grammars
• Pumping lemma for Context-Free Languages (CFL)
• Properties of Context-Free Languages (CFL)
• Chomsky Normal Form

Unit 4: Turing Machines and Models of Computation

• Turing machine as a model of computation
• Configuration of Turing machine
• Recursive and recursively enumerable languages,
• Church Turing Thesis
• Universal Turing Machine
• Decidability
• Halting problem