In context free grammar, the left-hand side of production rules contains only one variable, and right side may contain any number of variables or terminals in production rule. The production rules in context free grammar are in the form.
A -> a, where A is a variable, and a is string of any symbols from (V ∪ T)*
If we want to impose restriction on the right side of production rule, then context free grammar is said to be in a “normal form”.
In Chomsky Normal Form, there are restrictions on the length of right-hand side, and type of symbols is used in right hand side of production rules.
A -> BC
A -> a
In this, A, B and C are variables, and a is terminal
Steps to convert Context Free Grammar to Chomsky’s Normal Form (CNF)
Example:
Convert the following Context Free Grammar to Chomsky’s Normal Form (CNF)
S -> ASA
S -> aB
A -> B
A -> S
A -> ε
B -> b
B -> ε
Solution:
Step 1: S is the start variable in any production rule. In above given production rules, S variable appears in R.H.S, then we can add a new start symbol S’ and add a new Production S’ -> S in above given production.
S’ -> S
S -> ASA
S -> aB
A -> B
A -> S
A -> ε
B -> b
B -> ε
Step 2: Remove the null productions i.e.
A -> ε and B -> ε
After removing the null productions B -> ε
S’ -> S
S -> ASA
S -> aB
S -> a
A -> B
A -> S
A -> B
A -> ε
B -> b
Now removing the null production A -> ε, and after removing the null productions A -> ε. The new production is:
S’ -> S
S -> ASA
S -> aB
S -> a
S -> AS
S -> SA
S -> S
A -> B
A -> S
B -> b
Step 3: Remove Unit productions. i.e.
S -> S
S’ -> S
A -> B
A -> S
After removing the unit production S -> S, the new production is:
S’ -> S
S -> ASA
S -> aB
S -> a
S -> AS
S -> SA
A -> B
A -> S
B -> b
After removing the unit production A -> B, the new production is:
S’ -> ASA|aB|a|AS|SA
S -> ASA|aB|a|AS|SA
A -> b|S
B -> b
After removing the unit production A -> S, the new production is:
S’ -> ASA | aB | a| AS | SA
S -> ASA | aB | a| AS | SA
A -> b ASA | aB | a| AS | SA
B -> b
Step 4: Now, find out the productions that has more than two variables in R.H.S.
S’ -> ASA
S -> ASA
A -> ASA
After removing this production, the new production we get
S’ -> AX | aB | a| AS|SA
S -> AX | aB |a |AS|SA
A -> b| AX | ASA|aB|a|AS|SA
B -> b
X -> AX
Step 5: Now change the productions:
S’ -> aB
S -> aB
A -> aB
Finally, we get the production after converting the given Context Free Grammar to Chomsky’s Normal Form (CNF)
S’ -> AX | YB| aB | a| AS|SA
S -> AX | YB | aB |a |AS|SA
A -> b| AX | YB | ASA| aB |a| AS |SA
B -> b
X -> SA
Y -> a
This is the required Context Normal Form(CNF) for given Context Free Grammar (CFG).