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.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.4k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.4k
- Others 1.7k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,654 questions

56,169 answers

193,879 comments

94,301 users