Simplified CFG

Question

Consider the following grammar

$S\rightarrow Aa\mid B $

$B\rightarrow a\mid BC$

$C \rightarrow a\mid \in$

the no of productions in simplified cfg is

Comments

I think 4 ?

---

5???

---

we may remove A as its of no use

now S is producing only B so instead of that we may also remove S and make B as starting symbol and in B ,  C is Producing only a/NULL so we may substitute in B and it would be like

B --> a/ba/b

---

These type of questions are Poorly framed & Non-sense as the answer depends on the Algorithm that is being used here.

You can study different standard books Or standard resources, apply their “Null Production Removal Algorithm” on this question, you’ll get different answers.

Also, the problem of finding a Smallest CFG is Not easy, seems NP Hard Or undecidable, Not Sure.

Students should Avoid such Poor Questions & the sources which ask them.

Answer 1

1.Removal of null production

S->Aa|B
B->a|B|BC
C->a

2.Removal of Unit production
S->Aa|a|BC
B->a|BC
C->a

3.Removal of useless production

S->a|BC
B->a|BC
C->a
so total 5 production in simplified CFG.

Comments

Why you have removed S -> Aa

 A is variable here??

---

But you can't reachA from S therefore we removed it

---

Do we remove, A because its definition is not present in the grammar??

---

plz give me proper explanation why A is not removed in that grammer

Answer 2

We can remove Aa as A is not defined.
S->B
B-->a|bC
C-->a|eps

now, S->B is unit production
S-->a|bC
C-->a|eps

removing epsilon production,
S-->a|b|bC
C-->a

So, simplified CFG contains 4 productions.

Comments

@kapil is it necessary to write production S -> bC

---

yes,

Even if you want to replace C value, then,

S->a | b | bC | ba (still 4 productions)

---

ok i got it.

Answer 3

It's 4.. firstly epsilon is removed from C.. making C->a and B->a|b|bC and den unit production S->B is replaced by production of B making S->a|b|bC and also Aa is removed from S coz of useless symbol.. so total production will be

S->a|b|bC

C->a

That's 4...

Comments

But given answer is 8.

---

And you removed S-->B unit production,  it's okay.  But why you removed all B productions,  thts not unit productions,  please check and according to me answer should be 7(if we are not including S-->Aa production)

---

when u remove unit production it will be like S-> a|b|bC.. then after B will be a useless symbol coz B is not coming in any production rule of S.. that's why I removed B.. and total production is 4..

---

Ok I understand now.  Ok kirti Thanks for the help.  

One last help,  

finally

Steps for simplification of CFG - -

1. Remove all null productions

2. Remove unit productions  

3. Remove useless productions

Check, if it is anything there we need to do for simplification,  

Please check and correct me if I am wrong

---

@kriti singh why u left C->a??
it should also be removed because we can further simplify the CFG as

S->a/ba/b..isnt it??

---

C-->a is neither useless nor unit production

infact any non terminal which gives terminal string should not be removed here a is terminal which is derived from C so C is ueful symbol for simplified CFG

---

hmmm yea...u r right..thanks

---

@cse23 is there any sequence for simplifying CFG like firstt epsilon removal then unit production..or any way possible?

---

Wherever I studied it was in sequence only:

If G is a CFG , then we can construct a simplified equivalent CFG G’ with the help of following steps:

 1. Eliminate all null productions.

2. Eliminate all unit productions

3. Eliminate all useless productions

---

@devwritt
yes.. if any of the following things is in production rule.. den dey must be eliminated in the order.. order of elimination matters.. so eliminate in order as 1.null production
2.unit production
3.useless symbols

---

Okay okay,  Thanks.  Got it

Answer 4

S->a|b|bC

C->a
hence 4 productions.