# 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)$. – Yuval Filmus Nov 8 '16 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. – m0meni Nov 8 '16 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. – m0meni Nov 8 '16 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 '16 at 16:42
• FWIW: I think the question is quite clear: AR7 lacks notation to express their result. – Raphael Nov 8 '16 at 16:47

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 \}$.
• 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 '16 at 16:46