FORMAL
LANGUAGES AND AUTOMATA THEORY
·
Syllabus
·
Module I
Finite state systems - Deterministic
Finite Automata(DFA) & Non-deterministic Finite Automata (NFA)-Equivalence
of NFA & DFA - NFA with epsilon(ε) moves - Equivalence of NFA with & without
epsilon moves.
·
Module II
Regular
expressions(RE) - Equivalence
of finite automata & regular expressions - Conversion of FA
into RE -Finite automata
with output -Moore & Meelay machine - Equivalence of Moore & Meelay
machine - Applications –Lexical analysis -- Properties of regular sets -- Pumping lemma for regular sets -- Closure properties -- Decision algorithms -- Myhill
Nerode’s theorem & minimisation of finite automata -- minimisation algorithm.
·
Module V