Consider the following grammar G = (V, T, P, S), V = {S, X, Y}, T {a, b} and productions P are Convert this grammer in Chomsky Normal Form (CNF).

2.2kviews

written 8.4 years ago by

teamques10 ★ 68k

modified 2.8 years ago by

pedsangini276 • 4.8k

Mumbai university > Comp > SEM 4 > TCS

Marks: 10M

Year: Dec 2015

theory of computation

ADD COMMENT EDIT

1 Answer

47views

written 8.4 years ago by

teamques10 ★ 68k

Let us start by adding new start symbols for the terminals.

$$S →XYX$$ $$X → aX|€$$ $$Y→bY|€$$

Let us take S->XYX for converting to CNF.

Replace

$$YX→X1$$

a→A

b→B

$$€ → E$$

So,

$$S → XX1$$ $$X → AX$$ $$X → E$$ $$Y → BY$$ $$Y → E$$ $$X1 → YX$$ $$a → A$$ $$b → B$$ $$ € → E$$

Hence, the above rule is in CNF format.

ADD COMMENT EDIT

Please log in to add an answer.