Week 2 - Chomsky Normal forms

Question 1

What is a Chomsky Normal Form?

Answer 1

A way to define and represent a grammer that will help in various constructions. A grammer is CNF if each of its rules is one of the following types:
A -> BC
A -> a
Where A, B, C are variables, a is a terminal and B, C may not be the start variable.
In addition, S -> ɛ is permiited for the start variable.

Question 2

TRUE OR FALSE: A CFL os in CNF.

Answer 2

TRUE.

Question 3

How do you convert a CFG into CNF?

Answer 3

1. Add a new start variable S0 and the rule ( S0 -> S ) where S is the old start variable.
2. For every rule of type A -> ɛ for A /= S0, look at all the rest of the rules, and if they contain A in any of the ways below then follow that rule:
   o If there exists a rule of type B -> uAv, for u, v ∈ (Σ ∪ V)*, add B -> uv.
   o If there exists a rule of type B -> uAvAw, wwe add the rules
   B -> uvAw
   B -> uAvw
   B -> uvw
   and similarly for any number of occurrences of A in a rule.
   o If there exists a rule B -> A, we replace it with B->ɛ Unless this was a unit rule already removed.
   Repeat this procedure for each ɛ-rule until no such rules exist.
3. Remove any rule B -> B, because it is redundant.
4. Remove each unit rule of type A -> B, then we replace each rule of type B -> u with A -> u. Rules of type B -> ɛ are replaced by A -> ɛ unless A -> ɛ has already been removed.

5. We replace each rule of type:
A -> u1u2...uk     where k>= 2, ui ∈ Σ ∪ V
with the rules
A -> u1A1
A1 -> u2A2
...
Ak-2 -> uk-1uk
Where A1, A2,... Ak-2 are new variables.

6. For any rule of type:
A -> aB     where a is a terminal
Replace the rule with
A -> A1B
And add a new rule
A1 -> a

…And were done