COURSE OBJECTIVES:
To understand foundations of computation including automata theory
To construct models of regular expressions and languages.
To design context free grammar and push down automata
To understand Turing machines and their capability
To understand Undecidability and NP class problems
UNIT I AUTOMATA AND REGULAR EXPRESSIONS
Need for automata theory – Introduction to formal proof – Finite Automata (FA) – Deterministic Finite
Automata (DFA) – Non-deterministic Finite Automata (NFA) – Equivalence between NFA and DFA
– Finite Automata with Epsilon transitions – Equivalence of NFA and DFA- Equivalence of NFAs
with and without ε-moves- Conversion of NFA into DFA – Minimization of DFAs.
UNIT II REGULAR EXPRESSIONS AND LANGUAGES
Regular expression – Regular Languages- Equivalence of Finite Automata and regular expressions
– Proving languages to be not regular (Pumping Lemma) – Closure properties of regular languages.
UNIT III CONTEXT FREE GRAMMAR AND PUSH DOWN AUTOMATA
Types of Grammar – Chomsky‘s hierarchy of languages -Context-Free Grammar (CFG) and
Languages – Derivations and Parse trees – Ambiguity in grammars and languages – Push Down
Automata (PDA): Definition – Moves – Instantaneous descriptions -Languages of pushdown
automata – Equivalence of pushdown automata and CFG-CFG to PDA-PDA to CFG – Deterministic
Pushdown Automata.
UNIT IV NORMAL FORMS AND TURING MACHINES
Normal forms for CFG – Simplification of CFG- Chomsky Normal Form (CNF) and Greibach Normal
Form (GNF) – Pumping lemma for CFL – Closure properties of Context Free Languages –Turing
Machine : Basic model – definition and representation – Instantaneous Description – Language
acceptance by TM – TM as Computer of Integer functions – Programming techniques for Turing
machines (subroutines).
UNIT V UNDECIDABILITY
Unsolvable Problems and Computable Functions –PCP-MPCP- Recursive and recursively
enumerable languages – Properties – Universal Turing machine -Tractable and Intractable problems
P and NP completeness – Kruskal’s algorithm – Travelling Salesman Problem- 3-CNF SAT
problems
unit 1
1. Deterministic Finite Automata
2. Non-deterministic Finite Automata (NFA)
3. Finite Automata with Epsilon Transitions
UNit 2
1. Equivalence and Minimization of Automata.
2. Closure Properties of Regular Languages
3. FA and Regular Expressions
UNIT 3
• Equivalence of Pushdown Automata and CFG
• Deterministic Pushdown Automata.
• Parse Trees
UNIT 4
- Pumping Lemma for CFL
- Closure Properties of CFL
- Turing Machines*** related problems too
unit 5
- Universal lang (Recursive and recursively enumerable languages)
- P and NP completeness rrare