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

WHAT is a CFG?

The crucial constraint is the left-hand side: in a context-free production it is exactly one variable. (If the LHS could be a string of symbols, you'd have a context-sensitive grammar.)

HOW to read the notation (shorthand)

Several rules with the same LHS are stacked with |: $A \rightarrow \alpha_1 \mid \alpha_2 \mid \alpha_3 \quad\text{means}\quad A\to\alpha_1,\; A\to\alpha_2,\; A\to\alpha_3.$ The empty string is written $\varepsilon$ ; a rule $A \to \varepsilon$ erases $A$ .

Worked Example 1 — Matched parentheses

Grammar $G_1$ : $\;S \to (S)\,S \mid \varepsilon$ .

Worked example Derive

(()) $S \underset{1}{\Rightarrow} (S)S \underset{2}{\Rightarrow} (S) \underset{3}{\Rightarrow} ((S)S) \underset{4}{\Rightarrow} ((S)) \underset{5}{\Rightarrow} (())$

Step 1 — why? We need an opening paren, so use $S\to(S)S$ .
Step 2 — why? The outer string should be just one balanced group, so kill the trailing $S$ via $S\to\varepsilon$ .
Step 3 — why? Inside we want another nested pair → expand the inner $S$ again with $S\to(S)S$ .
Steps 4–5 — why? Both remaining $S$ 's contribute nothing, so apply $S\to\varepsilon$ twice.

Result (()) ∈ $L(G_1)$ . This grammar cannot be done by a DFA — counting unbounded nesting needs a stack, which is exactly what CFGs give you.

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 \mid E * E \mid (E) \mid a$ .

WHY CFGs matter (the 80/20)

The 20% you must own: (1) CFG = single-variable-LHS rewrite rules; (2) language = all terminal strings derivable from $S$ ; (3) parse tree encodes structure; (4) ambiguity = ≥2 parse trees. From these you can reason about every parser, every programming-language syntax, and every nesting/counting problem regular expressions fail at.

Common Mistakes

Active Recall

Recall What are the four components of a CFG, and the LHS restriction?

$G=(V,\Sigma,R,S)$ : variables, terminals, productions, start symbol. Every production's LHS is exactly one variable $\Rightarrow$ context-free.

Recall Define

$L(G)$ precisely. $L(G)=\{w\in\Sigma^* \mid S\Rightarrow^* w\}$ — only fully-terminal strings derivable from $S$ .

Recall What makes a grammar ambiguous? (careful wording)

Some string has two distinct parse trees (equiv. two distinct leftmost derivations). Property of the grammar, not the language.

Recall Why can't a DFA recognise

$\{(^n)^n\}$ but a CFG can? Unbounded nesting needs unbounded counting (a stack); finite states can't, but $S\to(S)\mid\varepsilon$ recurses freely.

Recall Feynman: explain a parse tree to a 12-year-old.

See hidden block below.

Recall (hidden Feynman)

Recall Explain like I'm 12

Think of a grammar as LEGO instructions. You begin with one special block called $S$ . Each instruction says "you may swap this block for these smaller blocks." You keep swapping until every block is a real letter you can't break further — that finished line of letters is your word. A parse tree is just the family photo showing which big block split into which small blocks. If the same word can be built into two different family photos, the instructions were sloppy — that sloppiness is called ambiguity.

Connections

Regular expressions and DFAs — strictly weaker; CFGs add a stack's worth of memory.
Pushdown automata — the machine model that exactly accepts context-free languages.
Chomsky hierarchy — CFG = Type-2, between regular (Type-3) and context-sensitive (Type-1).
Chomsky normal form — a restricted CFG shape used by the CYK parsing algorithm.
Pumping lemma for CFLs — proves some languages are not context-free.
Compilers — parsing — real-world use: turning source code into parse/syntax trees.

A CFG is formally a 4-tuple of what?

(V,\Sigma,R,S)

— variables, terminals, productions, start symbol.

What restriction defines "context-free" on productions?

The left-hand side is exactly one variable.

What is a production's general form?

A\to\alpha

with

A\in V

and

\alpha\in(V\cup\Sigma)^*

Define one derivation step

\Rightarrow

\alpha A\beta\Rightarrow\alpha\gamma\beta

A\to\gamma\in R

; surrounding

\alpha,\beta

unchanged.

What is

L(G)

\{w\in\Sigma^*\mid S\Rightarrow^* w\}

— all terminal strings derivable from

S

What is a sentential form?

Any string over

V\cup\Sigma

derivable from

S

(may still contain variables).

What is the yield of a parse tree?

The leaves read left-to-right = the derived terminal string.

Leftmost vs rightmost derivation?

Always rewrite the leftmost (resp. rightmost) variable next.

How many leftmost derivations correspond to one parse tree?

Exactly one (bijection).

Definition of an ambiguous grammar?

Some string has ≥2 distinct parse trees (≥2 leftmost derivations).

Is ambiguity a property of the language or grammar?

The grammar; some languages have an unambiguous grammar.

Give a CFG for matched parentheses.

S\to(S)S\mid\varepsilon

Why is

\{a^n b^n\}

context-free but not regular?

Needs unbounded counting (a stack);

S\to aSb\mid\varepsilon

does it, a DFA can't.

How do you remove ambiguity from

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

Use precedence layers:

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

Which automaton recognises exactly the CFLs?

Pushdown automata (PDA).

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Socho ek grammar ek recipe hai strings banane ki. Aap ek hi special symbol $S$ se shuru karte ho, aur productions (rules) lagaate ho jisme har baar ek variable ko kisi aur cheez se replace karte ho — tab tak jab tak sirf real letters (terminals) bach jaayein. Jo final string banti hai, woh language $L(G)$ ka part hai. "Context-free" ka matlab simple hai: rule ke left side par sirf ek variable hota hai, isliye aap usse kahin bhi replace kar sakte ho, aas-paas ke symbols matter nahi karte.

CFG itna important kyun hai? Kyunki ye nesting/recursion handle kar sakta hai — jaise matched brackets (()), ya programming language ka syntax. Regular expression aur DFA ye nahi kar paate kyunki unke paas counting ke liye memory (stack) nahi hoti. CFG ka rule $S\to(S)S\mid\varepsilon$ apne aap ko andar bula sakta hai (recursion), isliye unlimited nesting ban jaati hai.

Parse tree ek family photo jaisa hai — kaunsa bada block kis chhote block me toota, ye dikhata hai. Derivation ki order (kaunsa variable pehle expand kiya) matter nahi karti, sirf tree ka structure matter karta hai. Ek tree ke liye exactly ek leftmost derivation hota hai. Agar ek hi string ke do alag-alag parse tree ban jaayein, toh grammar ambiguous hai — jaise a+a*a me precedence clear na ho toh do meanings ban jaate hain. Compiler ke liye ye galat hai, isliye hum precedence layers ( $E,T,F$ ) laga ke grammar ko unambiguous bana dete hain. Yaad rakho: ambiguity ka test = do tree alag hone chahiye, sirf alag order se derive karna ambiguity nahi hai.

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

WHAT is a CFG?

HOW to read the notation (shorthand)

Worked Example 1 — Matched parentheses

Parse trees — structure, not order

Worked Example 2 — Arithmetic & ambiguity

WHY CFGs matter (the 80/20)

Common Mistakes

Active Recall

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Theory of Computation

Connections