Let G V R S be a CFG that generates A ie LG A Prove or di

Solution

There are two parts of this proof.

First it is to be shown that every string generated by G’ are in A*

Secondly show that every string in A* can be generated by G’

------------------------------------------------------------------------------------------------------

Proof that every string generated by G’ belongs to A*

When S->SS is not used, A is obtained which belongs to A*.

Now consider S->SS

Substitute S on the right side with A:

            S -> AA

Since AA belongs to A*, therefore, whether S-> SS is used or not, the strings that are generated belong to A*.

------------------------------------------------------------------------------------------------------

Proof that every string that belongs to A* can be generated by G’:

Notice that the empty string (epsilon) belongs to A*. However, it may not belong to the language G. If it doesn’t belong to the language G, then adding the production S -> SS doesn’t make any difference.

------------------------------------------------------------------------------------------------------

So, every string in A* can’t be generated by G’.

Hence, it is disproved that adding the rule S -> SS generates A*.

------------------------------------------------------------------------------------------------------

Infact, to generate A*, we have to add two rules: S-> SS and S -> epsilon

If you have any queries regarding this proof, please ask in the comments and I will make sure to help you with it.