GATE CS - THEORY OF COMPUTATION:Finite Automata and Regular Languages
Mastering finite automata and regular languages concepts and implementation.
Finite Automata and Regular Languages for GATE CS
GATE FA questions: build/minimize DFA, NFA↔DFA, regex ↔ FA, and pumping lemma "which language is not regular?"
DFA vs NFA
Same power (regular languages). NFA may have ε-moves and multiple transitions; convert via subset construction (up to (2^n) DFA states).
Closure
Regular languages closed under ∪, ∘, *, complement, intersection. Use closure + known non-regulars to argue.
Pumping lemma (use carefully)
For regular (L), ∃ (p) such that any (w in L) with (|w| ge p) splits (w=xyz) with (|xy| le p), (|y| ge 1), and (xy^k z in L) ∀ (k ge 0).
To show non-regular: pick a clever (w), argue every split fails for some (k). Classic: ({a^n b^n}), ({ww}).
Myhill–Nerode (exam mention)
Inequivalent prefixes ⇒ lower bound on DFA size; minimization merges equivalent states.
Next: CFG and PDA. Hub: GATE.