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

written 8.7 years ago by

teamques10 ★ 69k

modified 3.1 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 8.7 years ago by

teamques10 ★ 69k

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 2 others joined a min ago.

ADD COMMENT EDIT

Please log in to add an answer.