Convert the contextfree grammar to Chomsky Normal Form where

Convert the context-free grammar

to Chomsky Normal Form, where P consists of the rules:

Show your work...

A CFG is in chomsky normal form if the productions are in the following forms:

A -> a

A - > epsilon

A -> BC.

Add these productions to given rules:

A_a -> a

B_b -> b

C_c -> c

The grammar becomes:

S -> S_ab C | S_ac

C -> C_cC | epsilon

S_ab -> A_a S_abB | epsilon

S_ac -> A_a S_ac C | B

B -> B_b B | epsilon

also add..

S1 -> A_a S_ab

S2 -> A_a S_ac

_{New grammar becomes:}