Let $L_4$ $\subseteq$ {0,1}$^*$ be the set of all palindromes whose first character is 1. Give a context-free grammar for $L_4$.

I just wanted to check if my grammar is correct or not.

$$A \rightarrow 1B1$$ $$B \rightarrow 0B0\;|\;1B\;|\;0B\;|\;A\;|\;\epsilon$$

  • $\begingroup$ your grammar generates 101001 $\endgroup$ – A.Schulz Dec 14 '14 at 8:41
  • $\begingroup$ Try first to have a grammar that just generates all palindroms. $\endgroup$ – babou Dec 14 '14 at 10:04
  • 2
    $\begingroup$ Your question already includes a complete answer to the original problem but no question about this answer. Thus, only "yes/no" answers may remain, helping neither you nor future visitors. Please read related meta discussions here and here and adjust your question accordingly, e.g. by formulating a specific question about a single element of your answer you are uncertain about. $\endgroup$ – David Richerby Dec 14 '14 at 16:26
  • $\begingroup$ @DavidRicherby What if I want to just check my answer ? $\endgroup$ – Altaïr Dec 14 '14 at 20:40
  • $\begingroup$ Then you should either ask somebody (e.g., a TA or professor) or find an appropriate forum; this is not that forum. $\endgroup$ – David Richerby Dec 14 '14 at 22:59

Not exactly, as your $1B$ and $0B$ productions might cause problems. You will accept 1101 for example. I believe just simplyfing it a bit, like this:

$A → 1B1\ |\ 1\ |\ \epsilon$

$B → 0B0\ |\ 1B1\ |\ 1\ |\ 0\ |\ \epsilon$

is enough (if we say that an empty string is a palindrome).

| cite | improve this answer | |
  • 1
    $\begingroup$ But the empty string is a palindrome (reversing it doesn't change it)! I edited your answer. $\endgroup$ – David Richerby Dec 14 '14 at 16:25
  • $\begingroup$ That's right, thought it depends on the definition, but still better like this. Thanks. $\endgroup$ – 3yakuya Dec 14 '14 at 16:27
  • 1
    $\begingroup$ However, we prefer not to have "check my answer" questions on the site, since they're only useful to the person whose answer is being checked, whereas our goal is to build up a repository of generally useful questions and answers (see the links in my comment to the question for more on this). Thus, although your answer is correct, I'd encourage you not to answer this kind of question. (Apart from anything else, why should people get the credit for you doing their homework?) Your answers are good so save them for good questions. :-) $\endgroup$ – David Richerby Dec 14 '14 at 16:28
  • $\begingroup$ The title should be easy to find for anyone else searching for the same thing, so I thought it would be OK to write a correct solution. I'll look more into that in the future. $\endgroup$ – 3yakuya Dec 14 '14 at 16:29
  • $\begingroup$ The epmty string is a palindrome. It doesn't have 1 as its first character, though. $\endgroup$ – Ran G. Dec 14 '14 at 20:10

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