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

2.6kviews

Design CFG for

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

written 6.2 years ago by

pratikj2208 • 140

modified 5.1 years ago by

prashantsaini • 0

automata theory

ADD COMMENT EDIT

1 Answer

166views

written 6.0 years ago by

teamques10 ★ 69k

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 EDIT

Please log in to add an answer.