Removing useless symbols, ε- and unit productions

1. What proves a grammar ambiguous?
   Stuck? Peek at 3.1.3 Ambiguity

   • Ambiguous: some w has ≥ 2 parse trees (≡ ≥ 2 leftmost derivations).
   • Witnesses: E+E/E*E with id+id*id; SS with three pieces; aS|Sa with aa; dangling else.
   • Fix with precedence layers E → E+T | T, T → T*F | F, F → (E) | id.
   • Inherently ambiguous language: every grammar ambiguous, e.g. aⁱbʲcᵏ with i=j or j=k. No algorithm decides ambiguity in general.

   Read lesson 3.1.3

2. CFG for balanced parentheses?
   Stuck? Peek at 3.1.2 Writing CFGs for standard languages

   • Wrap: S → aSb | ε (aⁿbⁿ); ratios S → aSbb.
   • Nested: outer wrap → inner wrap. Concatenation: S → XY. Union: S → S₁ | S₂. Star: S → S₁S | ε.
   • Palindromes S → aSa | bSb | a | b | ε. Balanced S → SS | (S) | ε. #a = #b: S → aSbS | bSaS | ε.
   • i ≠ j: S → AC | CB, C → aCb | ε, A → aA | a, B → bB | b.

   Read lesson 3.1.2

3. How do you test whether a DFA’s language is empty?
   Stuck? Peek at 2.4.2 Algorithms for regular languages

   • Membership: run. Emptiness: reachable F? Finiteness: trim + cycle (or lengths n..2n−1). Universality: complement + emptiness. Equivalence: minimize & compare, or symmetric difference empty. Containment: L₁ ∩ L̅₂ = ∅.
   • All these have always-terminating algorithms for regular languages.

   Read lesson 2.4.2

A grammar written by people collects junk: variables that can never finish into a terminal string, variables that are never reached from S, rules like A → ε that complicate algorithms, and chains A → B → C that do no work. Before converting to a normal form, we clean all of it out without changing the language (except possibly ε).

S → AB | a, A → aA, B → b. Can A ever produce a terminal string? What happens to S → AB?

Prediction check

No — A → aA never ends, so A is non-generating. Any rule using A is useless: S → AB goes. Then B is no longer reachable from S and goes too. Result: S → a.

Useless symbols

1. Find generating symbols: terminals generate; A generates if some rule A → α has only generating symbols in α. Repeat until stable. Delete the rest.
2. Find reachable symbols from S (graph reachability, 0.2.5). Delete the rest.

Doing step 2 before step 1 can leave useless symbols behind.

ε-productions

A variable is nullable if A ⇒* ε. Find nullable variables (A → ε, or A → B₁…Bₖ with all Bᵢ nullable). Then for every rule, add versions with every subset of nullable occurrences removed (but don’t add A → ε). Finally delete all ε-rules. The new grammar generates L − {ε}; if ε ∈ L, add S₀ → S | ε with a new start.

Example: S → aSb | ε. S is nullable. S → aSb gives S → aSb | ab. Result generates aⁿbⁿ, n ≥ 1.

Unit productions

A unit production is A → B (one variable). Find all unit pairs (A, B) with A ⇒* B using only unit rules. For each pair and each non-unit rule B → α, add A → α. Then delete all unit rules.

Example: E → T | E + T, T → F | T * F, F → (E) | id. Unit pairs include (E,T), (E,F), (T,F); E gets T’s and F’s non-unit bodies.

Safe order

1. Remove ε-productions.
2. Remove unit productions.
3. Remove useless symbols (generating, then reachable).

This order never re-introduces something already removed.

Putting it together

• Useless = non-generating or unreachable; remove in that order.
• ε-removal adds versions with nullable symbols dropped; unit removal copies bodies along unit chains.
• Cleanup order: ε, unit, useless.

before:  S → AB | a,  A → aA,  B → b
generating: {a, b, B, S}      A ✗  → delete S → AB and A → aA
reachable from S:  {S, a}     B ✗  → delete B → b
after:   S → a                 L = {a} unchanged

A clean grammar is ready for a strict format. Next: Chomsky Normal Form, where every rule is A → BC or A → a — and every derivation of a length-n string takes exactly 2n − 1 steps.

1. MCQ

   In which order should useless symbols be removed?

   1. unreachable, then non-generating
   2. non-generating, then unreachable
   3. either order
   4. only non-generating
2. MSQ

   Grammar: S → AB | a, A → BC | ε, B → b | ε, C → c. Which variables are nullable?

   1. S
   2. A
   3. B
   4. C
3. NAT

   After removing ε-rules from S → aSbS | ε (not adding ε back), how many S-rules are there?

   Write your answer before opening the key.

4. MCQ

   A unit production is:

   1. A → a
   2. A → B
   3. A → ε
   4. A → AB

• useless symbol
• generating symbol
• reachable symbol
• nullable variable
• ε-production
• unit production
• unit pair

1. Which useless-symbol step comes first?
   Reveal answer

   Remove non-generating symbols, then unreachable ones.
2. Safe simplification order?
   Reveal answer

   ε-productions, unit productions, useless symbols.
3. What is a nullable variable?
   Reveal answer

   A ⇒* ε.