# 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$ [closed]

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$$

• your grammar generates 101001 Dec 14, 2014 at 8:41
• Try first to have a grammar that just generates all palindroms. Dec 14, 2014 at 10:04
• @DavidRicherby What if I want to just check my answer ? Dec 14, 2014 at 20:40
• Then you should either ask somebody (e.g., a TA or professor) or find an appropriate forum; this is not that forum. Dec 14, 2014 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).

• But the empty string is a palindrome (reversing it doesn't change it)! I edited your answer. Dec 14, 2014 at 16:25
• That's right, thought it depends on the definition, but still better like this. Thanks. Dec 14, 2014 at 16:27
• 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. :-) Dec 14, 2014 at 16:28
• 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. Dec 14, 2014 at 16:29
• The epmty string is a palindrome. It doesn't have 1 as its first character, though. Dec 14, 2014 at 20:10