The Gateway to Computer Science Excellence

+3 votes

**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.....**

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...???

+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.

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.

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.

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.

52,215 questions

60,015 answers

201,242 comments

94,700 users