1

2.4kviews

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

written 5.9 years ago by pratikj2208 • 140

modified 4.7 years ago by prashantsaini • 0

automata theory

ADD COMMENT FOLLOW SHARE EDIT

1 Answer

0

164views

written 5.6 years ago by teamques10 ★ 68k

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 COMMENT SHARE EDIT