Converting a long CFG to Chomsky Normal Form

116 Views Asked by At

I know there's a lot of examples on here, although I just cant seem to get this one, it seems significantly harder than any examples I've seen, the grammar is:

S-> ABAC | BaA

A-> Aa | BAbC | lambda

B-> bB | aBaC | lambda

C-> a|b

now by removing the lambda's, and replacing a's and b's with Ta, Tb I have:

S-> ABAC | BAC | BC | ABC | BTa| AAC | Ta

A-> ATa | Ta | BAbC | BTbC | AbC | TbC

B-> TbB | TaBTaC | Tb | TaTaC

C-> Ta | Tb

Ta-> a

Tb-> b

Now my question is, where do I go from here, do I just replace every single RHS variable with a different letter until I have massive list?