# What is the language L, generated by the grammar G?

Given the grammar $$G = (Ν, Σ, Π, S)$$, where $$Ν = \{S\}$$, $$Σ = \{0, 1\}$$, $$Π = \{S → ε, S → 0, S → 1, S → 0S0, S → 1S1\}$$, and $$S$$ is $$S$$. What is the language generated by the grammar?

• What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. – dkaeae Mar 13 '19 at 16:26
• Hint, can you generate at least 10 words? What is the pattern? 20 words? even more? If you are still stuck, edit the question to show all the words you have generated. – John L. Mar 13 '19 at 17:58

As grammar G is given G = (Ν, Σ, Π, S), where Ν = {S} and Σ = {0, 1} so using this Π = {S → ε, S → 0, S → 1, S → 0S0, S → 1S1} we evaluate a language L by putting non-terminal value and generating new strings that can be a part of language L and accepted by the grammar rule: so L={ ε, 0 , 1, 00,11,000,111,010,101,0000,1111,00100,00000,11111,11011,....} so on and so forth. we will just evaluate a non-terminal with a terminal value and get a resultant string.

• It looks like 0110 and 1010 are missing. Of course, you did not claim words were listed in the order of length. – John L. Mar 13 '19 at 21:47
• @Apass.Jack. 1010? really? – Rick Decker Mar 14 '19 at 15:46
• @RickDecker Thanks, my typo. I meant 0110 and 1001 are missing. – John L. Mar 14 '19 at 15:51

This is the general solution to your problem:

Depending on the syntax that you are used to, might be used instead of , but both symbols mean the same. In the case of the provided grammar, there is an infinite amount of words that can be generated, so you would rather not use a set of single, explicit words to represent the language. The kind of language created by your grammar is a non-deterministic context-free language (NCFL) and a common way of displaying it is: