Writing CFGs for standard languages

1. How many parse trees correspond to one leftmost derivation?
   Stuck? Peek at 3.1.1 Context-free grammars, derivations and parse trees

   • CFG: A → α, single variable on the left. CFL = L(G) for some CFG. Regular ⊂ CFL.
   • Leftmost / rightmost derivations; parse tree with yield = leaves left to right.
   • Trees ↔ leftmost derivations ↔ rightmost derivations (one-to-one per string).

   Read lesson 3.1.1

2. Grammar for palindromes over {a,b}?
   Stuck? Peek at 2.3.1 What a grammar is

   • G = (V, T, P, S); A → x | y; sentential form; ⇒, ⇒*; L(G) = {w ∈ T* : S ⇒* w}.
   • S → aSb | ε gives aⁿbⁿ (not regular) — general grammars exceed DFAs.
   • Palindromes: S → aSa | bSb | a | b | ε.

   Read lesson 2.3.1

3. Why is aⁿbⁿ not regular (pumping view)?
   Stuck? Peek at 2.4.3 Pumping lemma for regular languages

   • L regular ⇒ ∃p ∀w ∈ L, |w| ≥ p, ∃ xyz: |xy| ≤ p, |y| ≥ 1, ∀i ≥ 0: xyⁱz ∈ L. p = #states.
   • Game: they pick p and split; you pick w and i. Beat every split.
   • Standard picks: aᵖbᵖ; a^{p²}; aᵖbaᵖb (ww); prime q ≥ p+2 with i = q+1.
   • Necessary, not sufficient. Finite languages pass vacuously.

   Read lesson 2.4.3

GATE regularly shows a grammar and asks “which language does it generate?”, or gives a language and four grammars. The trick is that CFGs build strings with a few patterns: wrap (grow both ends together), concatenate (glue independent parts), choose (union), and repeat. Recognize the pattern and both directions become fast.

How would you generate { aⁿb²ⁿ : n ≥ 0 } with one variable?

Prediction check

S → aSbb | ε. Every a placed on the left is paired with two b’s on the right, wrapping from the outside in.

Pattern 1 — wrap (matched counts)

{aⁿbⁿ}: S → aSb | ε. {aⁿbᵐcᵐdⁿ}: S → aSd | T, T → bTc | ε (outer wrap, then inner wrap). Wrapping always matches a block on the left with a block on the right, nested.

Pattern 2 — palindromes

Even: S → aSa | bSb | ε. All: add | a | b for the middle symbol. Palindromes are a wrap where both ends must be the same symbol.

Pattern 3 — balanced parentheses

S → SS | (S) | ε (concatenate balanced pieces, or wrap one). An unambiguous alternative: S → (S)S | ε.

Pattern 4 — equal numbers of a’s and b’s

S → aSbS | bSaS | ε. Idea: look at the first symbol; if it is a, find the b that “balances” it; between them and after them are again balanced strings. Also correct: S → SS | aSb | bSa | ε.

Pattern 5 — unequal counts

{aⁱbʲ : i ≠ j} = {more a’s} ∪ {more b’s}. S → AC | CB, C → aCb | ε (equal core), A → aA | a (extra a’s, at least one), B → bB | b (extra b’s).

Union of grammars: new start S → S₁ | S₂. Concatenation: S → S₁S₂. Star: S → S₁S | ε.

Putting it together

• Four building moves: wrap, glue, choose, repeat.
• Wraps give nested matching; two counts that cross (aⁿbᵐcⁿdᵐ) cannot be wrapped.
• Always test ε and the shortest strings against a grammar.

language                      grammar                                 pattern
aⁿbⁿ                          S → aSb | ε                              wrap
aⁿb²ⁿ                         S → aSbb | ε                             wrap 1:2
aⁿbᵐcᵐdⁿ                      S → aSd | T,  T → bTc | ε               nested wraps
aⁿbⁿcᵐdᵐ                      S → XY, X → aXb | ε, Y → cYd | ε         concatenation
palindromes                   S → aSa | bSb | a | b | ε                symmetric wrap
balanced ( )                  S → SS | (S) | ε                         concat + wrap
#a = #b                       S → aSbS | bSaS | ε                      split at partner
aⁱbʲ, i ≠ j                   S → AC | CB, C → aCb | ε, A → aA|a, B → bB|b   union
aⁱbʲcᵏ, i = j or j = k        S → XC | AY, X → aXb | ε, Y → bYc | ε, A → aA | ε, C → cC | ε

Some of these grammars give two different trees for the same string (S → SS | (S) | ε does, for ()()()). When a grammar does that, it is ambiguous — the topic of the next lesson, and a real problem for compilers.

1. MCQ

   Which grammar generates { aⁿbⁿ⁺¹ : n ≥ 0 }?

   1. S → aSb | b
   2. S → aSb | ε
   3. S → aSbb | b
   4. S → aS | b
2. MSQ

   S → aSbS | bSaS | ε generates which strings?

   1. abab
   2. aabb
   3. abba
   4. aab
3. MCQ

   S → XY, X → aXb | ε, Y → cYd | ε generates:

   1. aⁿbⁿcⁿdⁿ
   2. aⁿbⁿcᵐdᵐ
   3. aⁿbᵐcᵐdⁿ
   4. aⁿbᵐcⁿdᵐ
4. NAT

   Number of strings of length 4 generated by S → aSa | bSb | ε?

   Write your answer before opening the key.

• wrap pattern
• nested and concatenated grammars
• union / concatenation / star of CFGs
• balanced-parentheses grammar
• equal-count grammar

1. CFG for aⁿbⁿcᵐdᵐ?
   Reveal answer

   S → XY, X → aXb | ε, Y → cYd | ε
2. CFG for aⁱbʲ with i ≠ j?
   Reveal answer

   S → AC | CB, C → aCb | ε, A → aA | a, B → bB | b
3. CFG for strings with #a = #b?
   Reveal answer

   S → aSbS | bSaS | ε
4. CFG for balanced parentheses?
   Reveal answer

   S → SS | (S) | ε (unambiguous: S → (S)S | ε)