Consider the following grammar G

Question

Consider the following grammar G:

S → ε|01S|10S|0S1|1S0|S01|S10|1S|S1

a) Let L(G) be the language of the above context-free grammar. Consider the language L = {x ∈ {0, 1} ∗ |n0(x) ≤ n1(x)} where n0(x) and n1(x) are the number of 0’s and 1’s in x, respectively. Show that L(G) is not equal to L.

b) Give context-free grammar for L.

Summary

Here the language L(G) generate the string which has a number is equal to 0’s or bigger than 1’s. But some patterns such as s1s are missing because all the strings are not generated by the language. Therefore we find that the language L(G) and L are not equal/same.
For the language L, we have an equivalent CFG.

Explanation

a] Given Grammar is S -> ε|01S|10S|0S1|1S0|S01|S10|1S|S1

L(G) is a language for the above grammar

This is another language

L={X∈{0,1}* | n0 (x)≤ n1(x)}

Here a number of 0’s less than equal to no of 1’s.

But

L(G)={∈.01,10,…………}

L(G) does not contain strings containing 1 as middle element.

“s1s” -> Pattern not peresent but it is present in language L.

Therefore L(G)m≠ L

b]  CFG for L

L={X∈{0,1}* | n0 (x)≤ n1(x)}

CFG: