Automation theory and Formal language

FINITE AUTOMATA: Definition and Description of a Finite Automaton, Deterministic and Non

deterministic Finite State Machines, Transition Systems and Properties of Transition Functions,

Acceptability of a String by a Finite Automaton, The Equivalence of DFA and NDFA, Mealy and Moore

Machines, Minimization of Finite Automata, Basics of Strings and Alphabets, Transition Graph and

Properties of Transition Functions, Regular Languages, The Equivalence of Deterministic and Non

deterministic Finite Automata

REGULAR EXPRESSIONS AND REGULAR SETS: Regular Expressions and Identities for Regular Expressions, Finite Automata and Reguler Expressions: Transition System Containing null moves, NDFA with mull moves and Regular Expressions, Conversion of Non-deterministic Systems to Deterministic Systems, Algebraic Methods using Arden’s Theorem, Construction of Finite Automata Equivalent to a Regular Expression, Equivalence of Two Finite Automata and Two Regular Expressions, Closure Properties of Regular Sets, Pumping Lemma for Regular Sets and its Application, Equivalence between regular languages: Construction of Finite Automata Equivalent to a Regular Expression, Properties of Regular Languages, Non-deterministic Finite Automata with Null Moves and Regular Expressions, Myhill-Nerode Theorem

FORMAL LANGUAGES: Derivations and the Language Generated by a Grammar, Definition of a Grammar, Chomsky Classification of Languages, Languages and their Relation, Recursive and

Recursively Enumerable Sets, Languages and Automata, Chomsky hierarchy of Languages

REGULAR GRAMMARS Regular Sets and Regular Grammars, Converting Regular Expressions to Regular Grammars, Converting Regular Grammars to Regular Expressions, Left Linear and Right Linear Regular Grammars

CONTEXT- FREE LANGUAGES: Ambiguity in CFG, Leftmost and nightmost derivations, Language of a CFG, Sentential forms, Applications of CFG, Pumping Lemma for CFG, Derivations Generated by a Grammar, Construction of Reduced Grammars, Elimination of null and unit productions, Normal Forms for CFG: Chomsky Normal Form SIMPLIFICATION OF CONTEXT-FREE GRAMMARS: Construction of Reduced Grammars,

Greibach Normal Form

PUSHDOWN AUTOMATA AND PARSING: Description and Madel of Pushdown Automata,

Representation of PDA, Acceptance by PDA, Pushdown Automata: NDPDA and OPDA, Context free

languages and PDA, Pushdown Automata and Context Free Languages, Comparison of deterministic

and non-deterministic versions, closure properties, LL (k) Grammars and Its Properties, LR(K)

Grammars and its Properties, PARSING: Top-Down and Bottom-Up Parsing