1
2.2kviews
Design CFG for ${a^n} {b^n}$ where n >=1 and convert to Chomsky Normal form.
1 Answer
0
161views

CFG for $a^n b^n$

S = asb | ab

Convert it to CNF

Let Az $\rightarrow$ a

B $\rightarrow$ b

$\therefore$ s $\rightarrow$ A SB | AB

S $\rightarrow A A_1 | AB$

$A_1 \rightarrow SB$ and

A $\rightarrow$ a

B $\rightarrow$ b

Above grammer is in CNF.

Please log in to add an answer.