Unit I Formal Language Theory and Finite Automata Finite Automata (FA) : An informal picture of FA, Finite State Machine (FSM), Language accepted by FA, Definition of Regular Language. FA without output : Deterministic and Nondeterministic FA (DFA and NFA), epsilon - NFA and inter-conversion. Minimization of DFAs. FA with output : Moore and Mealy machines -Definition, models, inter-conversion. (Chapter - 1) Unit IIRegular Expressions (RE) Introduction, Operators of RE, Precedence of operators, Algebraic laws for RE, Language to Regular Expressions, Equivalence of two REs. Conversions : RE to NFA, DFA, DFA to RE using Arden’s theorem, Pumping Lemma for Regular languages, Closure and Decision properties of Regular languages. Myhill-Nerode theorem. (Chapter - 2) Unit IIIContext Free Grammar (CFG) and Context Free Language (CFL) Basic Elements of Grammar, Formal Definition of Context Free Grammar, Sentential form, Derivation and Derivation Tree / Parse Tree, Context Free Language (CFL), Ambiguous Grammar, writing grammar for language. Simplification of CFG : Eliminating - productions, unit productions, useless production, and useless symbols. Normal Forms : Chomsky Normal Form, Greibach Normal Form, Pumping Lemma for CFG, Closure properties of CFL, Decision properties of CFL, Chomsky Hierarchy, Cock-Younger-Kasami Algorithm. (Chapter - 3) Unit IVPushdown Automata (PDA) Introduction, Formal definition of PDA, Equivalence of Acceptance by Final State and Empty stack, Non-deterministic PDA (NPDA), PDA and Context Free Language, Equivalence of PDA and CFG, PDA vs CFLs. Deterministic CFLs. (Chapter - 4) Unit V Turing Machines (TM) Turing Machine Model, Formal definition of Turing Machines, Language Acceptability by Turing Machines, Design of TM, Description of TM, Techniques for TM Construction, Computing function with Turing Machine, Variants of Turing Machines, Unit VI Computability and Complexity Theory
