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, 2014 at 8:41
  • $\begingroup$ Try first to have a grammar that just generates all palindroms. $\endgroup$
    – babou
    Dec 14, 2014 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$ Dec 14, 2014 at 16:26
  • $\begingroup$ @DavidRicherby What if I want to just check my answer ? $\endgroup$
    – Altaïr
    Dec 14, 2014 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$ Dec 14, 2014 at 22:59

1 Answer 1


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).

  • 1
    $\begingroup$ But the empty string is a palindrome (reversing it doesn't change it)! I edited your answer. $\endgroup$ Dec 14, 2014 at 16:25
  • $\begingroup$ That's right, thought it depends on the definition, but still better like this. Thanks. $\endgroup$
    – 3yakuya
    Dec 14, 2014 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$ Dec 14, 2014 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, 2014 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, 2014 at 20:10

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