Given following question:

Let $G$ be a context-free grammar, $G=(V, \Sigma, R, S)$, that has start variable $S$, set of variables $V = \{S\}$, set of terminals $\Sigma = \{0, 1\}$, and set of rules $R = \{S \rightarrow \epsilon , S \rightarrow 0 , S \rightarrow 1 , S → 0S0 , S \rightarrow 1S1\}$. Describe $L(G)$, the language of the grammar $G$.

I know that $\epsilon, 0, 1, 00, 11, 010, 101, 01010, 10101, 10001, 01110$ all fit the grammar, but I can't find a formal way to express what I want to say. Perhaps I don't know the symbols or something, but I would express it as

$L(G) = \{(0\ or\ 1)^n(0\ or\ 1)^{(0\ or\ 1)}(0\ or\ 1)^n,\ n \ge 0\}$

Is this right? Is there a more formal way to express this?

  • $\begingroup$ The word $01010$, generated by your grammar, doesn't belong to your guess at $L(G)$. $\endgroup$ – Yuval Filmus Nov 8 '16 at 15:32
  • $\begingroup$ @YuvalFilmus a palindrome always has an even number of digits except for a possibly odd one in the middle, and is the same forwards and backwards. Given the CFA the outer layers of {0, 1} have to always be matching pairs, and the middle number doesn't really matter so it's always the same forwards and backwards. How I would formally represent this? All the previous questions I've had to answer I had to write in a form like $L(G) = \{0^n1^n, n \ge 0 \}$ for example. I don't want to be so dogmatic about it being in this form, but I'm not sure if everything has to be in that form for this hw. $\endgroup$ – m0meni Nov 8 '16 at 15:36
  • $\begingroup$ @YuvalFilmus thank you very much. If you could please put all that as an answer I would like to accept it. I didn't know the palindrome notation, and now it all makes sense. $\endgroup$ – m0meni Nov 8 '16 at 15:40
  • $\begingroup$ @Evil $L=L^R$ only says that the language is closed against reversal. All kinds of languages have that property, including $\Sigma^*$. $\endgroup$ – Raphael Nov 8 '16 at 16:42
  • $\begingroup$ FWIW: I think the question is quite clear: AR7 lacks notation to express their result. $\endgroup$ – Raphael Nov 8 '16 at 16:47

Your grammar generates the language of all palindromes. It can be described in the following ways:

  1. $L(G)$ is the language of all palindromes over $\{0,1\}$.
  2. $L(G) = \{ x \in \{0,1\}^* : x \text{ is a palindrome} \}$.
  3. $L(G) = \{ x \in \{0,1\}^* : x^R = x \}$.

The first option is really the best, but unfortunately your TAs are expecting the third option.

  • 1
    $\begingroup$ One common way you'll find is $\{ ww^R \mid w \in \{0,1\}^* \}$ for even-length palindromes, which extends to $\{ wxw^R \mid w \in \{0,1\}^*, a \in \{\varepsilon, 0, 1\} \}$. (cc @AR7) $\endgroup$ – Raphael Nov 8 '16 at 16:46
  • $\begingroup$ @AR7 See here on how to show that this claim is indeed correct. $\endgroup$ – Raphael Nov 8 '16 at 16:48

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.