Unit II - Context Free Grammar

Example 1: Simple CFG

Grammar G for language {0ⁿ1ⁿ | n ≥ 1}:

S → 01          (base case)
S → 0S1         (recursive case)
                

Derivations:

• n=1: S ⇒ 01
• n=2: S ⇒ 0S1 ⇒ 0011
• n=3: S ⇒ 0S1 ⇒ 00S11 ⇒ 000111

Example 2: Balanced Parentheses

Grammar for valid parentheses strings:

S → ε           (empty string)
S → SS          (concatenation)
S → (S)         (nesting)
                

Examples generated: ε, (), (()), ()(), (()()), (()())

S → 01S
S → ε
                

S → S10
S → ε
                

Converting Right-Linear Grammar to NFA:

Grammar:

S → 0A
S → 1B
A → 0S
A → 1B
B → 0B
B → 1B
B → ε
                

NFA Construction:

1. Each variable becomes a state
2. Add a final state F
3. For production A → wB, add transition from state A to B on input w
4. For production A → w, add transition from A to F on input w
5. Start state is S

Example: Grammar and its Parse Tree

Grammar:

E → E + E
E → E * E
E → (E)
E → id
                

String: id + id * id

Parse Tree 1:

           E
          /|\
         E + E
         |   |\
        id  E * E
            |   |
           id  id
                

Interpretation: id + (id * id) - multiply first

Parse Tree 2:

           E
          /|\
         E * E
        /|\  |
       E + E id
       |   |
      id  id
                

Interpretation: (id + id) * id - add first

⚠️ This grammar is ambiguous (same string, multiple parse trees)

Example 1: Classic Ambiguous Grammar (Dangling Else)

S → if E then S
S → if E then S else S
S → other
                

Ambiguous String: if E then if E then other else other

Two Parse Trees possible:

1. else matches with outer if
2. else matches with inner if

Example 2: Arithmetic Expression Grammar

Ambiguous Grammar:

E → E + E | E - E | E * E | E / E | id
                

String "id + id * id" has multiple parse trees (different precedence)

Unambiguous Grammar (with precedence):

E → E + T | E - T | T
T → T * F | T / F | F
F → (E) | id
                

Now "id + id * id" has unique parse tree: id + (id * id)

Algorithm to Find Generating Symbols:

1. Initialize: Mark all terminals as generating
2. Iterate: Mark variable A as generating if there exists production A → α where all symbols in α are already marked generating
3. Repeat: Until no new variables are marked
4. Remove: All variables and productions containing non-generating symbols

Example:

Original Grammar:
S → AB | a
A → b
B → CD
C → c
D → d | E
E → EF
                

Analysis:

• Round 1: Terminals a, b, c, d are generating
• Round 2: A → b (b is terminal), so A is generating
• Round 2: C → c (c is terminal), so C is generating
• Round 2: D → d (d is terminal), so D is generating
• Round 3: B → CD (both C, D generating), so B is generating
• Round 4: S → AB (both generating) and S → a, so S is generating
• E and F are NOT generating (E → EF has E on right, circular)

After Removing Non-Generating:
S → AB | a
A → b
B → CD
C → c
D → d
                

Algorithm to Find Reachable Symbols:

1. Initialize: Mark S (start symbol) as reachable
2. Iterate: If A is reachable and A → α is a production, mark all symbols in α as reachable
3. Repeat: Until no new symbols are marked
4. Remove: All unreachable symbols and their productions

Example:

After removing non-generating:
S → AB | a
A → b
B → CD
C → c
D → d
E → e        (separate component)
                

Reachable from S: S, A, B, C, D, a, b, c, d

E is unreachable!

Final Simplified Grammar:
S → AB | a
A → b
B → CD
C → c
D → d
                

Algorithm to Remove ε-Productions:

1. Find all nullable variables
2. For each production A → α containing nullable variables, add new productions with all combinations of including/excluding nullable variables
3. Remove all ε-productions (except S → ε if ε ∈ L(G))

Example:

Original:
S → AB
A → aA | ε
B → bB | ε
                

Nullable: A, B, S

After Removing ε-Productions:
S → AB | A | B | ε
A → aA | a
B → bB | b
                

Algorithm:

1. Find all pairs (A, B) such that A ⇒* B using only unit productions
2. For each such pair and each non-unit production B → α, add A → α
3. Remove all unit productions

Example:

Original:
S → A
A → B
B → a | b
                

After Removing Unit Productions:
S → a | b
A → a | b
B → a | b
                

Converting to CNF: Steps

1. Start Symbol: Add new start symbol S₀ → S
2. Eliminate ε-productions: Remove all A → ε
3. Eliminate unit productions: Remove all A → B
4. Replace terminals: For production with mixed terminals and variables, replace terminal a with new variable Ta and add Ta → a
5. Break long productions: For A → B₁B₂...Bₙ (n > 2), introduce new variables:
   • A → B₁C₁
   • C₁ → B₂C₂
   • ...
   • Cₙ₋₂ → Bₙ₋₁Bₙ

Example: Convert to CNF

Original Grammar:
S → ASA | aB
A → B | S
B → b | ε
                

Step 1: Eliminate ε-productions (B is nullable)

S → ASA | aB | a
A → B | S | ε
B → b
                

Step 2: Eliminate ε-productions (A is nullable)

S → ASA | AS | SA | S | aB | a
A → B | S
B → b
                

Step 3: Eliminate unit productions

S → ASA | AS | SA | aB | a | b
A → b
B → b
                

Step 4: Replace terminals in mixed productions

S → ASA | AS | SA | TA B | a | b
A → b
B → b
TA → a
                

Step 5: Break long productions

S → AC₁ | AS | SA | TC₂ | a | b
C₁ → SA
C₂ → AB
A → b
B → b
TA → a
TC → a
                

Final CNF:

S → AC₁ | AS | SA | TC₂ | a | b
C₁ → SA
C₂ → AB
A → b
B → b
TA → a
                

Example: Grammar in GNF

S → aAB | bB | a
A → aA | bB | a
B → bB | b
                

✓ Every production starts with a terminal

✓ Followed by any number of variables (can be zero)

Normal Forms

• CNF: A→BC | a (plus S→ε optionally). Steps: new S₀, ε, unit, terminals→symbols, binarize.
• GNF: A→aα (terminal first), no left recursion; each step yields 1 terminal.