a. Convert the following CFG to GNF S->AA|a A->SS|b

28kviews

written 8.7 years ago by

teamques10 ★ 70k

• modified 3.8 years ago

Mumbai University > Computer Engineering > Sem 4 > Theoretical Computer Science

Marks: 10M

Year: Dec 2016

theory of computation

ADD COMMENT EDIT

1 Answer

4.0kviews

written 8.7 years ago by

teamques10 ★ 70k

Observe that the CFG is in CNF. If we rename S as A1 and A as A2 respectively, the production will be then

A1->A2A2|a

and A2=A1A1|b

We leave A2->b, as it is in the required form.

Now consider A2->A1A1. To convert this we will use lemma to get

A2->A2A2|a

A2->aA1 …

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.