Chomsky-Normal

Question 1

How do you shorten rules?

Answer 1

If a rule is in the form A—->o1o2…ok, k>=3, A is a variable and ox is either a terminal or variable. Then it should be replaced by k-1 rules where A–>o1C1, C1—>o2C2 …. Ck-3 = ok-2Ck-2
Ck-2 = ok-1 ok

where C’s are all new variables

Question 2

How do you eliminate Lambda rules?

Answer 2

For example for the rule B ---> lambda
A is some variable
If A----->BB, 
- If A---> lambda hasn't already been eliminated replace with A---> BB, A----> B, A---->lambda else 
- A---->BB, A---->B

If A—->B

• If A—> lambda hasn’t already been eliminated replace with A—–>B, A—–>lambda
• else A——>B

if A—->Bo or oB, o is not B
- Replace with A—-> Bo or oB and A—->B

Question 3

How do you eliminate Unit Rules?

Answer 3

For example for the rule A—>B

If B—>C

• If A–> Chas not already been eliminated and A is not equal to C
• don’t add another rule if A–>C has been eliminated or A = C

If B—>o where o is a terminal
- add the rule A—>o

If B —>o1o2 ox is variable or terminal
- add rule A—>o1o2