UNIT - I Introduction to Finite Automata: Structural Representations, Automata and Complexity, the Central Concepts of Automata Theory - Alphabets, Strings, Languages, Problems. Nondeterministic Finite Automata: Formal definition, an application, Text Search, Finite Automata with Epsilon - Transitions. Deterministic Finite Automata: Definition of DFA, How A DFA Process Strings, The language of DFA, Conversion of NFA with - transitions to NFA without - transitions. Conversion of NFA to DFA, Moore and Melay machines. (Chapter - 1) UNIT - II Regular Expressions: Finite Automata and Regular Expressions, Applications of Regular Expressions, Algebraic Laws for Regular Expressions, Conversion of Finite Automata to Regular Expressions. Pumping Lemma for Regular Languages: Statement of the pumping lemma, Applications of the Pumping Lemma, Closure Properties of Regular Languages: Closure Properties of Regular Languages, Decision Properties of Regular Languages, Equivalence and Minimization of Automata. (Chapter - 2) UNIT - III Context-Free Grammars: Definition of Context-Free Grammars, Derivations Using a Grammar, Leftmost and Rightmost Derivations, the Language of a Grammar, Sentential Forms, Parse Tress, Applications of Context-Free Grammars, Ambiguity in Grammars and Languages. Push Down Automata: Definition of the Pushdown Automaton, the Languages of a PDA, Equivalence of PDA's and CFG's, Acceptance by final state, Acceptance by empty stack, Deterministic Pushdown Automata, From CFG to PDA, From PDA to CFG. (Chapter - 3) UNIT - IV Normal Forms for Context - Free Grammars: Eliminating useless symbols, Eliminating - productions, Chomskey normal form Griebech normal form. Pumping Lemma for Context-Free Languages: Statement of pumping lemma, Applications. UNIT - V Types of Turing Machine
