4
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • $\begingroup$ The word $01010$, generated by your grammar, doesn't belong to your guess at $L(G)$. $\endgroup$
    – Yuval Filmus
    Commented Nov 8, 2016 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
    Commented Nov 8, 2016 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
    Commented Nov 8, 2016 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
    Commented Nov 8, 2016 at 16:42
  • $\begingroup$ FWIW: I think the question is quite clear: AR7 lacks notation to express their result. $\endgroup$
    – Raphael
    Commented Nov 8, 2016 at 16:47

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 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
    Commented Nov 8, 2016 at 16:46
  • $\begingroup$ @AR7 See here on how to show that this claim is indeed correct. $\endgroup$
    – Raphael
    Commented Nov 8, 2016 at 16:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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