# Finding the language of a context-free grammar?

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?

• The word $01010$, generated by your grammar, doesn't belong to your guess at $L(G)$. Nov 8, 2016 at 15:32
• @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. Nov 8, 2016 at 15:36
• @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. Nov 8, 2016 at 15:40
• @Evil $L=L^R$ only says that the language is closed against reversal. All kinds of languages have that property, including $\Sigma^*$.
– Raphael
Nov 8, 2016 at 16:42
• FWIW: I think the question is quite clear: AR7 lacks notation to express their result.
– Raphael
Nov 8, 2016 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.

• 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)
– Raphael
Nov 8, 2016 at 16:46
• @AR7 See here on how to show that this claim is indeed correct.
– Raphael
Nov 8, 2016 at 16:48