UNIT - I Finite State Machines Basic Concepts : Symbols, Strings, Language, Formal Language, Natural Language. Basic Machine and Finite State Machine. FSM without Output : Definition and Construction-DFA, NFA, NFA with epsilon-Moves, Minimization Of FA, Equivalence of NFA and DFA, Conversion of NFA with epsilon moves to NFA, Conversion of NFA With epsilon moves to DFA. FSM with Output : Definition and Construction of Moore and Mealy Machines, Inter-conversion between Moore and Mealy Machines. (Chapter - 1) UNIT - II Regular Expressions Definition and Identities of Regular Expressions, Construction of Regular Expression of the given L, Construction of Language from the RE, Construction of FA from the given RE using direct method, Conversion of FA to RE using Arden’s Theorem, Pumping Lemma for RL, Closure properties of RLs, Applications of Regular Expressions. (Chapter - 2) UNIT - III Context Free Grammar and Languages Introduction, Formal Definition of Grammar, Notations, Derivation Process : Leftmost Derivation, Rightmost Derivation, derivation trees, Context Free Languages, Ambiguous CFG, Removal of ambiguity, Simplification of CFG, Normal Forms, Chomsky Hierarchy, Regular grammar, equivalence of RG(LRG and RLG) and FA. (Chapter - 3) UNIT - IV Pushdown Automata and Post Machines Push Down Automata : Introduction and Definition of PDA, Construction (Pictorial/ Transition diagram) of PDA, Instantaneous Description and ACCEPTANCE of CFL by empty stack and final state, Deterministic PDA Vs Nondeterministic PDA, Closure properties of CFLs, pumping lemma for CFL. Post Machine - Definition and construction. (Chapter - 4) UNIT - V Turing Machines Formal definition of a Turing machine, Recursive Languages and Recursively Enumerable Languages, Design of Turing machines, Variants of Turing Machines : Multi-tape Turing machines, Universal Turing Machine, Nondeterministic Turing machines. Comparisons of all automata. (Chapter - 5) UNIT - VI Computational Complexity Decidability : Decidable problems concerning regular languages, Decidable problems concerning context-free languages, Un-decidability, Halting Problem of TM, A Turing-unrecognizable language. Reducibility : Un-decidable Problems from Language Theory, A Simple Un-decidable Problem PCP, Mapping Reducibility. Time Complexity : Measuring Complexity, The Class P, Examples of problems in P, The Class NP, Examples of problems in NP, NP-completeness. (Chapter - 6)
