The Gateway to Computer Science Excellence
+3 votes
459 views

in this question given ans is  9 

s->Aa | a | bC | b

B->a | bC | b

C -> a

but here B is unreachable   ans has to 5

clarify plz.....

in Compiler Design by Active (1.6k points) | 459 views
0
here S->B is not unit production u shouldn't remove that
0

@Pooja Palod ma'am how can you say here S->B is not unit production. according to me it is  unit production .

can you explain plz...???

2 Answers

+11 votes
Best answer
Simplified CFG means:

1. Remove useless productions.
2. Remove epsilon productions.
3. Remove unit productions.

S->Aa. since A is useless.

After step 1, grammar would be:
S->B
B->a|bC
C->a|^

After step 2, grammar would be:
S->B
B->a|bC|b
C->a

After step 3, we will get:
S->a|bC|b
B->a|bC|b
C->a
Now, Production of B are useless (unreachable from S), so final CFG is

S-> a|bC|b

C->a

Therefore, total of 4 productions.
by Loyal (9.4k points)
selected by
+1

why dont we replace 'C'  by 'a '?

By Substituion Rule: 

S-> a|bc|b

0

monanshi,@Praveen Saini sir it is not correct bcoz the order of execution of removal algorithm is- 

(1) Remove epsilon productions.

(2) Remove unit productions.
(3)  Remove useless productions.

0 votes

monanshi,@Praveen Saini sir it is not correct bcoz the order of execution of removal algorithm is- 

(1) Remove epsilon productions.

(2) Remove unit productions.
(3)  Remove useless productions.

by Active (4.4k points)
0
is it really correct?Check it once again.There are many mistakes in your solution.
0

LeenSharma sir if there are many mistakes in my solution then plz point out bcoz one of my faculty teach removal in that order only.

+1
In your simplified CFG.A is a useless symbol.and B is unreachable from start symbol s.

Related questions

0 votes
0 answers
4
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,654 questions
56,169 answers
193,879 comments
94,301 users