GATE CS - THEORY OF COMPUTATION:Context-Free Grammars and PDAs

CFGs and PDAs for GATE CS

GATE asks CFG↔language, ambiguity, PDA acceptance (empty stack vs final state), and closure differences vs regular languages.

CFG

Productions (A o alpha). Leftmost/rightmost derivations; parse trees. Ambiguous if some string has two trees — not good for deterministic parsing.

PDA

Finite control + one stack. Nondeterministic PDA ≡ CFL. Deterministic PDA ⊂ CFL (classic example languages separate them).

Acceptance: final state and/or empty stack — GATE states which.

Closure (remember the gaps)

CFLs closed under ∪, ∘, *. Not closed under complement or intersection (in general). Intersection of CFL with regular is CFL.

Pumping lemma for CFLs

Harder than regular; used to show non-CFL (e.g. ({a^n b^n c^n})). If options only need FA-level pumping, stay there.

Next: Turing Machines.