Convert the following grammar to its CNF form: S->ASB | aB | CaB ; A->B|CB B->b|€
Question
Convert the following grammar to its CNF form:
S->ASB | aB | CaB
A->B|CB
B->b|€
Solutions of the question be “PDF” format and solution with not be handwritten. So use the editor to convert (word, latex etc) to write the solution and convert to pdf.
Summary
The productions are given CFG is not in the format of grammar in CNF. Hence, to convert to CNF form first the lambda productions are removed. Then, the unit productions are removed. And then, the useless productions are removed. Finally, each of the productions is brought to the proper format. And hence obtained the CNF as explained below.
Explanation
- A CFG is said to be in CNF (Chomsky Normal form) if and only if all of its productions are in the form:
A -> BC or A -> a
Where A, B, C are Non-terminal variables and ‘a’ is a terminal variable.
G = (V, T, S, P)
Here, V represents the Non-terminal variable
T represents Terminal Variable
S represents the Start variable
P represents a finite set of productions
- Given CFG G = (V, T, S, P)
Where, V = {S, A, B}
T = {a, b, ε}
S = S
P, Productions are
S -> ASA | aB | CaB
A -> B | CB
B -> b | ε
The above productions are not in a valid format to be in CNF
- Conversion to CNF
Before converting to CNF, we have to first remove lambda productions, then remove unit productions and then remove useless productions
- Removing lambda productions:
S -> ASA | aB | CaB | a | Ca
A -> B | CB | C
B -> b
- Removing Unit-productions:
S -> ASA | aB | CaB | a | Ca
A -> b | CB
B -> b
- Removing useless productions
The variable ‘C’ is non-reachable, hence it is useless
S -> ASA | aB | a
A -> b
B -> b
S -> ASA | aA | a
A -> b
- Bringing all the productions in proper format:
S -> ASA | CB | a
A -> b
C -> a
S -> AD | CB | a
A -> b
C -> a
D -> SA
Therefore, all the productions are in proper format
The CFG is
G = (V, T, S, P)
Where, V = {S, A, B, C, D}
T = {a, b}
S = S
P = {
S -> AD | CB | a
A -> b
C -> a
D -> SA
}
