-4
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – dkaeae Mar 13 at 16:26
  • 1
    $\begingroup$ 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. $\endgroup$ – Apass.Jack Mar 13 at 17:58
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ It looks like 0110 and 1010 are missing. Of course, you did not claim words were listed in the order of length. $\endgroup$ – Apass.Jack Mar 13 at 21:47
  • $\begingroup$ Yeah I am just giving the idea that so many strings can be generated. These strings could be of different length.... $\endgroup$ – Kiran Zahoor Mar 14 at 11:01
  • $\begingroup$ @Apass.Jack. 1010? really? $\endgroup$ – Rick Decker Mar 14 at 15:46
  • $\begingroup$ @RickDecker Thanks, my typo. I meant 0110 and 1001 are missing. $\endgroup$ – Apass.Jack Mar 14 at 15:51
0
$\begingroup$

This is the general solution to your problem:

enter image description here

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:

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.