Cheap and Secure Web Hosting Provider : See Now

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$

, ,
Problem Detail:

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

Answered By : 3yakuya

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/35268

3200 people like this