1,035 views
1 votes
1 votes
S -> aAa|bBb|epsilon

A -> C|a

B -> C|b

C -> CDE|epsilon

D -> A|B|ab

new grammar after removing null, unit and useless productions is??

2 Answers

Best answer
1 votes
1 votes

Before removing null productions, i.e C-> epsilon.

Since C produces Ca and Cb, we add A-->a and B-->b before deleting epsilon.If we dont add,we might miss strings that include a and b. C-->CDE will become useless state,so we remove all C's. So the final grammer after adding A-->a and B-->B is

S-->aAa/bBb/EPSILON

A-->a

B-->b.

We will not delete Epsilon in S because it forms a part of language.

 

selected by
0 votes
0 votes
S -> aAa|bBb|aa|bb|$\varepsilon$
A -> a
B -> b

Please correct me if I'm wrong

Related questions

0 votes
0 votes
0 answers
2
baofbuiafbi asked Nov 14, 2023
151 views
Prove the language L={(G,H)|G is a CFG, H is a DFA, and L(G)∩L(H)=∅} is undecidable.