Covert to Chomsky Normal Form Please show all steps in cover
Covert to Chomsky Normal Form:
Please show all steps in coverting this. THANK YOU!
S asb.SIAaBSolution
S -> aSbS|AaB
A -> BaA|a
B -> Sa|bB|b
Adding a new start(S\'):
S\' -> S
S -> aSbS|AaB
A -> BaA|a
B -> Sa|bB|b
Next:
S\' -> aSbS|AaB
S -> aSbS|AaB
A -> BaA|a
B -> Sa|bB|b
Next:
S\' -> aS\'\' | AB\'
B\' -> aB
S\'\' -> SS\'\'\'
S\'\'\' -> bS
S -> aS\'\'|AB\'
A->BA\'|a
A\'->aA
B -> Sa|bB|b
