0

$B$ - set of palindroms such that number of $1s$ is equal to number of $0s$. Every palindrom $\in \{0,1\}^*$
And my task let me that $B$ is not CFG. But I don't agree with it.
Because of the fact that $\#_0(w)=\#_1(w)$ I conlude that $B$ is set of palindroms such that their length is even, so:
$B=\{ww^r|w\in \{0,1\}^*\}$
A show CFG for this language $B$:
$S\rightarrow 1S1|0S0|\epsilon$
What's up my dear friends ?

user220688
  • 509

2 Answers2

1

Hint:

  • For example $10111101$ is a palindrome of even length with different number of zeros and ones.
  • Intersecting $B$ with regular language $1^*0^*1^*$ gives you $\{1^n0^{2n}1^n\mid n\in \mathbb{N}\}$.
  • The above is quite similar to $\{a^nb^nc^n\mid n\in \mathbb{N}\}$ which is not context-free.

I hope thos helps $\ddot\smile$

dtldarek
  • 37,381
  • Yeah, I get it. We have a fact that $L_1\in CFG$ and $L_2\in Reg$ then $L_1\cap L_2 \in CFG$. And now if $L_1\cap L_2$ is irregular then assuming that $L_2\in Reg$ $L_2\notin CFG$. The only thing that we should to show is ${1^n0^{2n}1^n}\notin CFG$ It should be shown with pumping lemma. Is there different solution ?/ – user220688 Apr 20 '15 at 11:10
  • @user220688 Perhaps there is, but this seems by far the simplest one. – dtldarek Apr 20 '15 at 12:01
1

The context free grammar you're given does not correspond to the definition of $B$ because $11$ is generated by grammar but it's not an element of $B$. Actually the definition meant by the question is : $$B=\{ww^r|w\in \{0,1\}^*,|w|_1=|w|_0\}$$ which is more complicated but can be done using the pumping Lemma, the idea behind the proof:

We choose a palindrome with $2p$ $1$’s and $2p$ $0$’s such that the $1$’s are all at the middle. We pump it by deleting the repeated strings. Because there are so many $1$s, the deleted strings cannot have $0$s from both side, so they either take $0$s from one side and leave the string asymmetric or take only $1$s and leave the string with an unequal amount of $0$s and $1$s.

Elaqqad
  • 13,725
  • I'm missing something here. Observe that $|ww^r|_0 = 2\cdot |w|_0$ and same for $1$'s, so $|ww^r|_0 = |ww^r|_1$ implies $|w|_0=|w|_1$ (and the other implication does hold as well). – dtldarek Apr 20 '15 at 12:00
  • you're right i'm mistaken – Elaqqad Apr 20 '15 at 13:32