Context-free grammars (CFG) — productions, derivations, parse trees

4.6.8 · Coding › Theory of Computation

WHAT is a CFG?

Sabse zaroori constraint left-hand side hai: ek context-free production mein woh exactly ek variable hota hai. (Agar LHS symbols ki ek string ho sakti, toh woh ek context-sensitive grammar hoti.)

HOW to read the notation (shorthand)

Ek hi LHS wale kai rules | se stack kiye jaate hain: $A \to α_{1} ∣ α_{2} ∣ α_{3} means A \to α_{1}, A \to α_{2}, A \to α_{3} .$ Empty string $ε$ likhi jaati hai; ek rule $A \to ε$ $A$ ko erase kar deta hai.

Worked Example 1 — Matched parentheses

Grammar $G_{1}$ : $S \to (S) S ∣ ε$ .

Parse trees — structure, not order

Figure — Context-free grammars (CFG) — productions, derivations, parse trees

Worked Example 2 — Arithmetic & ambiguity

Ambiguous grammar $G_{2}$ : $E \to E + E ∣ E * E ∣ (E) ∣ a$ .

WHY CFGs matter (the 80/20)

20% jo tumhare paas hona chahiye: (1) CFG = single-variable-LHS rewrite rules; (2) language = $S$ se derivable saari terminal strings; (3) parse tree structure encode karta hai; (4) ambiguity = ≥2 parse trees. Inse tum har parser, har programming-language syntax, aur har woh nesting/counting problem ke baare mein reason kar sakte ho jisme regular expressions fail hote hain.

Common Mistakes

Active Recall

Recall Ek CFG ke char components kya hain, aur LHS restriction kya hai?

$G = (V, Σ, R, S)$ : variables, terminals, productions, start symbol. Har production ka LHS exactly ek variable hai $\Rightarrow$ context-free.

Recall

$L (G)$ precisely define karo. $L (G) = {w \in Σ^{*} ∣ S \Rightarrow^{*} w}$ — sirf fully-terminal strings jo $S$ se derivable hain.

Recall Grammar ko ambiguous kya banata hai? (careful wording)

Kisi string ke do distinct parse trees hain (equiv. do distinct leftmost derivations). Grammar ki property hai, language ki nahi.

Recall DFA

${(^{n})^{n}}$ kyun recognize nahi kar sakta lekin CFG kar sakta hai? Unbounded nesting ke liye unbounded counting chahiye (ek stack); finite states nahi kar sakte, lekin $S \to (S) ∣ ε$ freely recurse karta hai.

Recall Feynman: ek 12-saal ke bache ko parse tree explain karo.

Neeche hidden block dekho.

Recall (hidden Feynman)

Recall Explain like I'm 12

Grammar ko LEGO instructions samjho. Tum ek special block $S$ se shuru karte ho. Har instruction kehta hai "tum is block ko in chote blocks se swap kar sakte ho." Tum tab tak swap karte rehte ho jab tak har block ek real letter na ho jo aur toot na sake — letters ki woh finished line tumhara word hai. Ek parse tree bas woh family photo hai jo dikhata hai kaun sa bada block kis chote block mein split hua. Agar wahi word do alag family photos mein build ho sakta hai, toh instructions sloppy the — woh sloppiness ambiguity kehlati hai.

Connections

Regular expressions and DFAs — strictly weaker; CFGs ek stack ki memory add karte hain.
Pushdown automata — woh machine model jo exactly context-free languages accept karta hai.
Chomsky hierarchy — CFG = Type-2, regular (Type-3) aur context-sensitive (Type-1) ke beech.
Chomsky normal form — ek restricted CFG shape jo CYK parsing algorithm use karta hai.
Pumping lemma for CFLs — prove karta hai ki kuch languages context-free nahi hain.
Compilers — parsing — real-world use: source code ko parse/syntax trees mein convert karna.

Ek CFG formally kis 4-tuple ka hota hai?

(V, Σ, R, S)

— variables, terminals, productions, start symbol.

Productions par "context-free" kaunsi restriction define karti hai?

Left-hand side exactly ek variable hota hai.

Ek production ka general form kya hai?

A \to α

jahan

A \in V

aur

α \in (V \cup Σ)^{*}

Ek derivation step

\Rightarrow

define karo.

α A β \Rightarrow α γ β

agar

A \to γ \in R

ho; surrounding

α, β

unchanged.

L (G)

kya hai?

{w \in Σ^{*} ∣ S \Rightarrow^{*} w}

— saari terminal strings jo

S

se derivable hain.

Sentential form kya hota hai?

S

se derivable koi bhi string over

V \cup Σ

(abhi bhi variables contain kar sakti hai).

Parse tree ka yield kya hai?

Leaves ko left-to-right padhna = derived terminal string.

Leftmost vs rightmost derivation?

Hamesha sabse leftmost (resp. rightmost) variable ko aage rewrite karo.

Ek parse tree se kitne leftmost derivations correspond karte hain?

Exactly ek (bijection).

Ambiguous grammar ki definition?

Kisi string ke ≥2 distinct parse trees hain (≥2 leftmost derivations).

Kya ambiguity language ki property hai ya grammar ki?

Grammar ki; kuch languages ka ek unambiguous grammar hota hai.

Matched parentheses ke liye ek CFG do.

S \to (S) S ∣ ε

{a^{n} b^{n}}

context-free kyun hai lekin regular nahi?

Unbounded counting chahiye (ek stack);

S \to a S b ∣ ε

karta hai, ek DFA nahi kar sakta.

E \to E + E ∣ E * E ∣ (E) ∣ a

se ambiguity kaise hatate hain?

Precedence layers use karo:

E \to E + T ∣ T, T \to T * F ∣ F, F \to (E) ∣ a

Exactly CFLs ko kaunsa automaton recognize karta hai?

Pushdown automata (PDA).