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.4kviews

written 9.4 years ago by

teamques10 ★ 70k

modified 3.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

48views

written 9.4 years ago by

teamques10 ★ 70k

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 → …

Create a free account to keep reading this post.

and 4 others joined a min ago.

ADD COMMENT EDIT

Please log in to add an answer.