I have to put this CFG into Chomsky Normal Form, and I was having difficulty doi
ID: 3804319 • Letter: I
Question
I have to put this CFG into Chomsky Normal Form, and I was having difficulty doing it. (e represents epsilon)
S -> aAbS | bBaS | e
A -> aAbA | e
B -> bBaB | e
I removed all the epsilons and symbols that were not generating and not reachable and got
S -> aAbS | bBaS | abS | aAb | ab | ba | bBa | baS
A -> aAbA | abA | aAb | ab
B -> bBaB | baB | bBa | ba
I feel like this is correct so far, but I don't know where to go from here. Could you show the step by step conversion from here.
Explanation / Answer
Answer: A CFG is said to be in Chomsky Normal Form if the production rules in CFG take the following form:
A -> a
A -> BC
S -> e
where A,B,C are non-terminals, S is start symbol, e is empty string and a is terminal.
Procedure to convert CFG into Chomsky Normal Form:
1. If start symbol S is present on RHS on any production rule, then create a new start symbol S0 and production rule S0 -> S.
For the given CFG, S appears on RHS of many production rule. So, we will add new start symbol S0 and production rule S0 -> S. Then, CFG will become:
-----------------------------------------
S0 -> S
S -> aAbS | bBaS | e
A -> aAbA | e
B -> bBaB | e
------------------------------------------
2. If null production(s) is(are) present in CFG, remove. A null production is the production that ends in e.
In the given CFG, there are null productions. So we will remove them.
First we will remove B -> e. The CFG will become
---------------------------------------
S0 -> S
S -> aAbS|bBaS|baS|e
A -> aAbA|e
B -> bBaB|baB|bBa|ba
-------------------------------
Next we remove A -> e. The CFG will become:
---------------------------------
S0 -> S
S -> abS|bBaS|baS|e
A ->aAbA|abA|aAb|ab
B->bBaB|baB|bBa|ba
--------------------------------
At last we will remove S -> e. After that we will get:
-----------------------------
S0 -> S
S -> aAbS | bBaS | abS | aAb | ab | ba | bBa | baS
A -> aAbA|abA|aAb|ab
B -> bBaB|baB|bBa|ba
---------------------------------------
3. If any unit productions are present in CFG, the remove them. A unit production is one that ends in another single non-terminal.
For the given CFG, there is only a single unit production S0 -> S. So, we will remov it. After removing it, we will get:
--------------------------------------
S0 -> aAbS | bBaS | abS | aAb | ab | ba | bBa | baS
S -> aAbS | bBaS | abS | aAb | ab | ba | bBa | baS
A -> aAbA|abA|aAb|ab
B -> bBaB|baB|bBa|ba
--------------------------------
4. Next step is to replace all productions having more than 2 non-terminals with productions having only two non-terminals by introducing new non-terminals if required.
In our CFG, there is no such production. So we will move further.
5. Next step is to replace production rules which have one terminal and one non-terminal on RHS. So now we will replace all such production rules. We get:
-----------------------------------
X -> a
Y -> b
P -> RB
Q -> XB
R -> BX
T -> AYA
U -> YA
V -> AY
S0 -> AS | XV | XY | YX | YR | BS
S -> AS | XV | XY | YX | YR | BS
A -> XT|XU|XV|XY
B -> YP|YQ|YR|YX
-------------------------------------------