Week 8 Lecture 1 - Simplifying Grammars and Chomsky and Greibach Normal Forms

When is a non-terminal A nullable?

if 𝐴 ⇒* 𝜆

In the production, B → CAD, A is nullable.

Therefore, in a derivation, A may or may not derive 𝜆

How is this fixed?

Making 2 versions of the production:

B → CAD
B → CD

Then we can forget A derives 𝜆

What is the algorithm for elimination of 𝜆-productions

1. First compute the nullable symbols:
   → Basic: Productions of the form 𝐴 → 𝜆 tells us that A is nullable.
   → Induction: Given a production B → C1C2…Ck, if every Ci is nullable, then B is nullable.

2. Delete all 𝜆-productions

3. For each production 𝐴 → 𝑋1𝑋2 … 𝑋𝑘 with k ≥ 1, replace the new productions, where the nullable Xi’s in all possible combinations are present or absent.
   → If m of one of the Xi’s are nullable, then the production will be replaced by 2^m productions.
   → Exception! If all symbols are nullable, then we would exclude the case where all Xi’s are absent (would give 𝐴 → 𝜆)

Consider the CFG:

S → AB
A → aAA | λ
B → bBB | λ

Remove the nullable symbols (A, B and S)

• 𝑆 → 𝐴𝐵 becomes 𝑆 → 𝐴𝐵 | 𝐴 | 𝐵

• 𝐴 → 𝑎𝐴𝐴 becomes 𝐴 → 𝑎𝐴𝐴 | 𝑎𝐴 | 𝑎

• 𝐵 → 𝑏𝐵𝐵 becomes 𝐵 → 𝑏𝐵𝐵 | 𝑏𝐵| 𝑏

• Hence, the new 𝜆-production free grammar: 𝑆 → 𝐴𝐵 | 𝐴 | 𝐵 𝐴 → 𝑎𝐴𝐴 | 𝑎𝐴 | 𝑎 𝐵 → 𝑏𝐵𝐵 | 𝑏𝐵 | 𝑏

What are unit pairs?

1. Find all unit pairs of the original grammar

2. Construct a set of productions: for all unit pairs (A,B), add all the productions A → a, where B → a is a production of the original grammar but not a unit production

When are symbols generating and reachable?

A symbol X is generating if there is a derivation X ⇒* w for some terminal string w.

A symbol X is reachable if there is a derivation S ⇒* 𝛼X𝛽 for some 𝛼 and 𝛽

Useless and Useful symbols

A symbol is useful if it is both generating and reachable, otherwise it is useless.

Consider the grammar:

S → AB | a
A → b

What symbol is not generating?

→ b. If we eliminate B, we must eliminate S → AB:

S → a
A → b

In

S → a
A → b

What symbol isn’t reachable?

A → b

eliminate to leave only S → a

Algorithm for eliminating useless symbols

1. Compute generating symbols:
   Basis: Every terminal is generating
   Induction: Given a production A → a, if every symbol in a is generating, then A is too generating.

2. Eliminate all productions involving non-generating symbols.

3. Compute reachable symbols:

4. Basis: S is reachable
   Induction: Suppose that non-terminal A is reachable. Then for every production A → a, every symbol in a is also reachable.

5. Eliminate all productions involving symbols that are not reachable

What is normal form used for?

Simplifying CFGs.

This makes it easier to prove facts about CFLs, since we know their grammar can be made to conform to the restrictions of this normal form.

When is a CFG said to be in Chomsky Normal Form?

If every production is of the form:

A → BC (non-terminal on the left hand side, generating 2 terminals)

A → a (non-terminal generating exactly 1 terminal)

What is the safe order to execute the methods to reach CNF?

1. Eliminate λ-productions

2. Eliminate unit productions

3. Eliminate useless symbols

And then ensure that the productions are of the form A → BC or A → a

Ensuring CNF when there are more than 2 non-terminals on one side

What is greibach normal form?

All rules are of the form

A → aA₁A₂…A_n

where a is a single non-terminal and aA₁A₂…A_n is 0 or more non-terminals

Derivations with Greibach Normal Form

The right-hand side of each production begins with a single terminal.

This means that a string of length n will be derived by a grammar in Greibach Normal Form using exactly n derivations - the i’th derivation will result in the terminal at the i’th position in the string being generated.

A parse tree for a string of length n will have a maximum depth of n.