Context-Free Grammars and PDAs

Context-Free Grammars and PDAs

Context-Free Grammars generate context-free languages recognized by Pushdown Automata.

Context-Free Grammar (CFG)

CFG is a 4-tuple: G = (V, T, P, S)

• V: Variables (non-terminals)
• T: Terminals
• P: Production rules (A → α, where A ∈ V, α ∈ (V ∪ T)*)
• S: Start symbol

Example:

G = ({S}, {0, 1}, {S → 0S1 | ε}, S)

Generates: {0ⁿ1ⁿ | n ≥ 0}

Derivation

Derivation applies production rules.

Leftmost Derivation: Replace leftmost variable first.

Rightmost Derivation: Replace rightmost variable first.

Parse Tree: Tree representation of derivation.

Ambiguity

Ambiguous Grammar: Multiple parse trees for same string.

Inherently Ambiguous Language: All grammars are ambiguous.

Example: E → E + E | E * E | id is ambiguous.

Pushdown Automaton (PDA)

PDA is a 7-tuple: M = (Q, Σ, Γ, δ, q₀, Z₀, F)

• Q: States
• Σ: Input alphabet
• Γ: Stack alphabet
• δ: Transition function
• q₀: Start state
• Z₀: Initial stack symbol
• F: Accepting states

Types:

• Deterministic PDA (DPDA): At most one transition
• Nondeterministic PDA (NPDA): Multiple transitions

Acceptance:

• Final State: Accept if in final state
• Empty Stack: Accept if stack empty

PDA and CFG Equivalence

NPDA ≡ CFG

• Every CFG has equivalent NPDA
• Every NPDA has equivalent CFG

Normal Forms

Chomsky Normal Form (CNF)

Rules:

• A → BC (two non-terminals)
• A → a (single terminal)
• S → ε (only if ε ∈ L)

Benefits:

• Easier parsing
• CYK algorithm

Greibach Normal Form (GNF)

Rules:

• A → aα (terminal followed by variables)

Benefits:

• Left-to-right parsing

Pumping Lemma for CFL

Pumping Lemma: If L is CFL, then:

• ∃ n such that ∀ w ∈ L with |w| ≥ n
• w = uvxyz where:
• |vxy| ≤ n
• |vy| > 0
• uvⁱxyⁱz ∈ L for all i ≥ 0

Use: Prove language is NOT context-free.

Example: L = {0ⁿ1ⁿ2ⁿ | n ≥ 0} is not context-free.

Closure Properties

CFLs are closed under:

• Union
• Concatenation
• Kleene star
• Homomorphism
• Substitution

CFLs are NOT closed under:

• Intersection
• Complement
• Intersection with regular

CFL ∩ Regular = CFL

GATE CS Important Points

1. CFG Construction: Write grammar for language
2. PDA Construction: Build PDA for language
3. Ambiguity: Identify and remove ambiguity
4. Normal Forms: CNF, GNF
5. Pumping Lemma: Prove non-CFL

Practice Tips

1. Write CFG: Practice for various languages
2. Construct PDA: Build PDA for languages
3. Remove Ambiguity: Practice disambiguation
4. Normal Forms: Convert to CNF/GNF
5. Previous Year Questions: Solve GATE CFG/PDA questions