Question

Simplify the grammar G. Does L(G) contain ε ?

S -> A B C | B a B

A -> a A | B a C | a a a

B -> b B b | a | D

C -> C A | A C

D -> ε

Answer 1

Solution:

Given grammar G,

S -> ABC | BaB

A -> aA | BaC | aaa

B -> bBb | a | D

C -> CA | AC

D ->

The answer will be "No"

Explanation:

Simplification of grammar G:

Step 1:

=>Remove useless symbols

=>Production rule C -> CA | AC , as AC and CA never terminates so never generate any string hence symbol C is useless hence remove all productions where symbol C appears. A is also useless as it is not reachable from start symbol S.

S -> BaB

B -> bBb | a | D

D ->

Step 2:

=>Remove null productions.

=>Production D -> is a null production so remove D ->

S -> a | BaB | aB | Ba

B -> bBb | a

Step 3:

=>Remove unit productions, as here there is no unit production of type X -> Y where X is single non terminal and Y is also single terminal.

S -> a | BaB | aB | Ba

B -> bBb | a

=>So the simplified grammar is:

S -> a | BaB | aB | Ba

B -> bBb | a

Finding language of grammar G:

=>Smallest strings generated by the given grammar G = a using S -> a

=>Strings of length 2 generated by the grammar G = aa using S -> aB or S -> Ba, B -> a

and so on.

=>L(G) means the language generated by given grammar G.

=>L(G) is set of all the strings generated by the given grammar G, L(G) = {a, aa, aaa,.....}

=>We can see that the smallest string generated by the grammar G is "a" and there is no way to generate the string of length 0 means .

=>On the basis of above statements we can say that L(G) does not contain .

I have explained each and every part with the help of statements attached to it.

We were unable to transcribe this image

We were unable to transcribe this image

We were unable to transcribe this image

We were unable to transcribe this image

We were unable to transcribe this image

We were unable to transcribe this image