Register

useless productions

6,301 views
0 0 votes

Eliminate all useless productions

S->a|aA|B|C,  A->aB|λ, B->Aa C->cCD , D->ddd

also eliminate all λ productions from 

S->AaB|aaB, A->λ, B->bbA|λ

2 Answers

Best answer
2 2 votes

Useless production are those which cannot generate terminal

Here C is useless

So, after removing useless production grammar will be

S-> a | aA | B

A-> aB | ⋋

B -> Aa

Eliminating ⋋ production from 2nd grammar it will be

S->a|aa|aB|aaB,

B->bb

• selected by
2 2 votes
First one :

S->a|aA|B

A->aB

B->Aa|a

Epsilon production also removed

Second one :

S->aB|aaB|a|aa

B->bb
Voting & Accepting an answer helps improve the community
← Previous · s-grammarNext → · CYK algo
← Previous in category · s-grammarNext in category → · CYK algo
Position:
Show:

Related questions

1 1 vote
2 2 answers
1.2k
1.2k views
Sukhbir Singh asked Apr 30, 2019
1,171 views
Deletion of Useless Symbols from a Grammar Self Doubt
S → AB/aA → BC/bB → aB/CC → aC/BHow do we remove useless symbols and productions from this grammar?While solving, i found that the useful symbols are {a,b,S,A}Hence, we ...
1 1 vote
0 0 answers
3.2k
3.2k views
Manu Thakur asked Oct 13, 2017
3,174 views
Automata: Number of Productions in the CFG
Consider the following context free grammar:$S \rightarrow ASA | aB$$A \rightarrow B | S$$B \rightarrow b | \epsilon$How many productions will be there in the modified g...
0 0 votes
1 1 answer
555
555 views
Sahil1994 asked Oct 9, 2017
555 views
Removing E productions
We need to remover E productions from the grammarVertices-{A,B,C,S} Terminals={a,b,c,E}S->ABACA->aA/EB->bB/EC->c
0 0 votes
0 0 answers
3.0k
3.0k views
Manu Thakur asked Sep 5, 2017
3,004 views
CFG: Removal of Unit Productions
Remove unit productions from the following CFG:S0 SS ASA | aB | a | SA | AS | SA >B | SB bSolution:if I replace S with its Right Side part, i getS0- ASA | aB | a | ...