Context-free grammars, derivations and parse trees

1. Is { aⁿbᵐ : n ≡ m (mod 3) } regular?
   Stuck? Peek at 2.4.4 Drill: regular or not?

   • Bounded fact (mod, flag, last k, capped count, bounded difference) ⇒ regular.
   • Exact comparison of two unbounded counts, ww, wwᴿ, squares, primes, 2ⁿ ⇒ not regular.
   • Finite ⇒ regular. Unary: regular ⇔ lengths eventually periodic.
   • wxwᴿ, wxw (x ∈ Σ⁺) regular. #ab = #ba regular. ww over one letter regular.

   Read lesson 2.4.4

2. What does L(G) mean for a grammar G?
   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 S → aA, A → Sb | b not a regular grammar?
   Stuck? Peek at 2.3.2 Right-linear and left-linear grammars

   • Right-linear: A → wB | w. Left-linear: A → Bw | w. Regular grammar = one of the two (not mixed).
   • DFA → grammar: δ(A,a)=B ⇒ A → aB; A accepting ⇒ A → ε.
   • Grammar → NFA: A → aB is an arrow; A → a goes to a new accepting state.
   • Mixed linear can give aⁿbⁿ. Non-regular grammar does not imply non-regular language.

   Read lesson 2.3.2

Every compiler you have used starts by checking that your code is grammatical: that if (x) { y = (a + b) * c; } has matching brackets, operators between operands, and so on. The rules in the language manual look like Expr → Expr + Term | Term. Those are context-free grammars (CFGs). They generate exactly the structures finite automata could not: nested, matched, recursive. This lesson makes them precise and shows the tree that every derivation builds.

Grammar: S → aSb | ε. Draw (in your head) the tree of rule applications for aabb. How many times is the rule S → aSb used?

Prediction check

Twice, then S → ε once. The tree has S at the root, an a–S–b layer, another a–S–b layer, and an ε leaf in the middle. Read the leaves left to right: a a ε b b = aabb.

Definition

“Context-free” means a variable can be rewritten regardless of what surrounds it. Right-linear grammars are a special case, so every regular language is context-free. A language is context-free (a CFL) if some CFG generates it.

Leftmost and rightmost derivations

When a sentential form has several variables, you choose which to rewrite.

• Leftmost derivation (⇒ₗₘ): always rewrite the leftmost variable.
• Rightmost derivation (⇒ᵣₘ): always the rightmost.

Example G: S → AB, A → aA | a, B → bB | b, w = aab.
Leftmost: S ⇒ AB ⇒ aAB ⇒ aaB ⇒ aab.
Rightmost: S ⇒ AB ⇒ Ab ⇒ aAb ⇒ aab.
Different orders, the same tree.

Parse trees

Key fact: for every string, parse trees ↔ leftmost derivations ↔ rightmost derivations, one-to-one. A tree forgets only the order in which variables were rewritten.

Language of a CFG

L(G) = { w ∈ T* | S ⇒* w }. To show w ∈ L(G), give a derivation or tree. To show L(G) equals some described set, prove both directions (every derived string has the property; every string with the property can be derived) — usually by induction on derivation length or string length.

Putting it together

• A CFG rewrites one variable at a time, regardless of context.
• Each derivation builds a parse tree; leftmost and rightmost orders correspond one-to-one with trees.
• CFLs include every regular language and also aⁿbⁿ.

G:  E → E + T | T        T → T * F | F        F → (E) | id
parse tree of id + id * id (this grammar forces * below +):

                 E
               / | \
              E  +  T
              |   / | \
              T  T  *  F
              |  |     |
              F  F     id
              |  |
              id id
leftmost derivation: E ⇒ E+T ⇒ T+T ⇒ F+T ⇒ id+T ⇒ id+T*F ⇒ id+F*F ⇒ id+id*F ⇒ id+id*id

CFGs can generate what finite automata cannot. Next: the toolkit for writing CFGs for the standard languages — aⁿbⁿ, palindromes, balanced brackets, equal counts, unequal counts.

1. MCQ

   Which production is NOT allowed in a CFG?

   1. S → ε
   2. S → aSbS
   3. aS → b
   4. A → BCD
2. MSQ

   For a fixed string w and grammar G, which are in one-to-one correspondence?

   1. parse trees of w
   2. leftmost derivations of w
   3. rightmost derivations of w
   4. all derivations of w
3. NAT

   With S → aSb | ε, how many derivation steps produce a⁵b⁵?

   Write your answer before opening the key.

4. MCQ

   L(S → aSa | bSb | ε) is:

   1. all palindromes
   2. even-length palindromes
   3. odd-length palindromes
   4. (a+b)*

• context-free grammar (CFG)
• context-free language (CFL)
• leftmost derivation
• rightmost derivation
• parse tree (derivation tree)
• yield

1. What makes a grammar context-free?
   Reveal answer

   Every production has a single variable on the left: A → α.
2. Parse trees vs leftmost derivations?
   Reveal answer

   One-to-one for each string.
3. Is every regular language context-free?
   Reveal answer

   Yes (right-linear grammars are CFGs).