Question: Design CFG for ${a^n} {b^n}$ where n >=1 and convert to Chomsky Normal form.
0

Mumbai University > Information Technology > Sem 4 > Automata Theory

Marks : 10M

automata theory • 183 views
ADD COMMENTlink
modified 8 weeks ago by gravatar for RB RB100 written 5 months ago by gravatar for pratikj2208 pratikj22080
0

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.

ADD COMMENTlink
written 8 weeks ago by gravatar for RB RB100
Please log in to add an answer.