Redirected
retagged by
10,126 views
2 votes
2 votes

retagged by

7 Answers

14 votes
14 votes
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.
5 votes
5 votes
After eliminating null productions, unit productions, productions without useful variables and productions containing variables not reachable from start symbol, we get the following productions

S-> a | ba | b.

So 3 productions are there is simplified CFG.
edited by
2 votes
2 votes
Answer will be 3 ... here is how ..

step 1) remove epsilon productions.

we get .. S-> Aa | B

              B-> a| bC | b

              C -> a

step 2) remove unit productions .. S->B is the only unit production here

we get ..

S-> Aa | a | bC | b

B-> a | bC | b

C -> a

step 3) Removing useless symbols

we cannot reach to B From S , hence B is useless.

and  S -> Aa, cannot reach any terminal string .. hence it is useless ..

now .. substitute C->a .. we get simplified CFG as.

S-> a| ba |b

ans. 3 Productions

Related questions

0 votes
0 votes
0 answers
1
Shubhanshu asked Aug 29, 2017
3,029 views
Consider the following grammar :S- Aa / BB - a / bCC - a / epsilonThe number of productions in simplified CFG is_________.I am getting 3. As S - Aa / a / b.
1 votes
1 votes
0 answers
4