Question

Convert the following grammar into Chomsky Normal Form (CNF): SaSAS A → AbBa| aAa B+bb | bBb Note: you need to first simplify the grammar (remove any - productions, unit productions, and useless productions), and then convert the simplified grammar to CNF.

Convert the following grammar into Chomsky Normal Form (CNF):

S $LaTeX: \rightarrow$→ aS | A | bS

A $LaTeX: \rightarrow$→ aA | bBa | aAa

B $LaTeX: \rightarrow$→ bb | bBb

Note: you need to first simplify the grammar ( remove any $LaTeX: \lambda$λ - productions, unit productions, and useless productions), and then convert the simplified grammar to CNF.

Answer 1

Chomsky Normal Form format
S0 -> epsilon
NT -> NT NT
NT -> T
where NT = Non terminal and T = terminal
--------------------------------------
Add S0 to the grammar
S0 -> S
S -> aS | A | bS
A -> aA | aBa | aAa
B -> bb | bBb

Remove the epsilon productions: None
Remove the unit productions
S0 -> aS | aA | aBa | aAa | bS
S -> aS | aA | aBa | aAa | bS
A -> aA | aBa | aAa
B -> bb | bBb

Remove useless productions: S0 is redundant

S -> aS | aA | aBa | aAa | bS
A -> aA | aBa | aAa
B -> bb | bBb

Replace the Ts with NTs for non-unit productions
S -> XS | XA | XBX | XAX | YS
A -> XA | XBX | XAX
B -> YY | YBY
X -> a
Y -> b

Final CNF Format
S -> XS | XA | CX | DX | YS
A -> XA | CX | DX
B -> YY | EY
X -> a
Y -> b
C -> XB
D -> XA
E -> YB
--------------------------------------
Hit the thumbs up if you are fine with the answer. Happy Learning!