Unit I Formal Language Theory and Finite Automata Introduction to Formal language, introduction to language translation logic, Essentials of translation, Alphabets and languages, Finite representation of language, Finite Automata (FA): An Informal Picture of FA, Finite State Machine (FSM), Language accepted by FA, Definition of Regular Language, Deterministic and Nondeterministic FA(DFA and NFA), epsilon- NFA, FA with output: Moore and Mealy machines -Definition, models, inter-conversion. Case Study: FSM for vending machine, spell checker Unit II Regular Expressions (RE) Introduction, Operators of RE, Building RE, Precedence of operators, Algebraic laws for RE, Conversions: NFA to DFA, RE to DFA Conversions: RE to DFA, DFA to RE Conversions: State/loop elimination, Arden‘s theorem Properties of Regular Languages: Pumping Lemma for Regular languages, Closure and Decision properties. Case Study: RE in text search and replace Unit III Context Free Grammars (CFG) and Languages Introduction, Regular Grammar, Context Free Grammar- Definition, Derivation, Language of grammar, sentential form, parse tree, inference, derivation, parse trees, ambiguity in grammar and Language- ambiguous Grammar, Simplification of CFG: Eliminating unit productions, useless production, useless symbols, and -productions, Normal forms- Chomsky normal form, Greibach normal form, Closure properties of CFL, Decision properties of CFL, Chomsky Hierarchy, Application of CFG: Parser, Markup languages, XML and Document Type Definitions. Case Study- CFG for Palindromes, Parenthesis Match, Unit IV Turing Machines (TM) Turing Machine Model, Representation of Turing Machines, Language Acceptability by Turing Machines, Design of TM, Description of TM, Techniques for TM Construction, Variants of Turing Machines, The Model of Linear Bounded Automata , TM & Type 0 grammars, TM‘s Halting Problem. Unit V Pushdown Automata(PDA) Basic Definitions, Equivalence of Acceptance by Finite State & Empty stack, PDA & Context Free Language, Equivalence of PDA and CFG, Parsing & PDA: Top-Down Parsing, Top-down Parsing Using Deterministic PDA, Bottom-up Parsing, Closure properties and Deterministic PDA. Unit VI Undecidability & Intractable Problems A Language that is not recursively enumerable, An un-decidable problem that is RE, Post Correspondence Problem, The Classes P and NP : Problems Solvable in Polynomial Time, An Example: Kruskal's Algorithm, Nondeterministic Polynomial Time, An NP Example: The Traveling Salesman Problem, Polynomial-Time Reductions NP Complete Problems, An NP Complete Problem: The Satisfiability Problem, Tractable and Intractable Representing Satisfiability Instances, NP Completeness of the SAT Problem, A Restricted Satisfiability Problem: Normal Forms for Boolean Expressions, Converting Expressions to CNF, The Problem of Independent Sets, The Node-Cover Problem.
