World's most popular travel blog for travel bloggers.

[Solved]: Showing that $\mathscr{L}$ is not context-free-grammar language

, , No Comments
Problem Detail: 

Let $"t"$ and $"s"$ be a words we will say that two words are "completly different" if for all $1\leq i\leq |t|$ the $i$ letter in $t$ diffrent from the $i$ letter in $s$.

Prove that the language $\mathscr{L}=\{ts|t,s\in \{0,1\}^*,|t|=|s|,t,s \text{ completly different} \}$ is not a free-context-language

My attempt:

Applaying the pumping lemma for free-contex-language

Suppose that $\mathscr L$ is regular so $\exists$ a word '$z=uxvyw$' with length of at least $n$ such that:

$(1)\,\,\,|xvy|\leq n$

$(2)\,\,\,|xy|\geq 1$

$(3)\,\,\,ux^ivy^iw \in \mathscr L\,\,\,\,\,\,\,\,\,i\geq 0$

Now, let us choose the word $\color{blue}{z=0^n1^n}$ it is obvious that $|z|\geq n$ so we can use $(1)-(3)$


So $\alpha+\beta+\gamma+\lambda=n$

I am stuck here.

EDIT: After using @Renato's hint:

Consider $z=0^p1^p0^p1^p0^p1^p\in \mathscr{L}$ since $|z|>p$, there are $u,v,w,x,y$ such that $z=uvwxy,|vwx|\leq p, |vx|>0$ and $uv^iwx^iy\in \mathscr{L}$

$vwx$ must straddle the midpoint of $z$ there are fore possibilities:

  • $vwx$ is in $0^p$ part.

  • $vwx$ is in $1^p$ part.

  • $vwx$ is in $1^p0^p$ part.

  • $vwx$ is in $0^p1^p$ part.

Thus, it is not of the form that we want

For $i=2$ $z\notin \mathscr{L}$


Asked By : Nehorai

Answered By : Renato Sanhueza

You are wrong because you can pump in the middle of the word. A guy has commited the same mistake as you yesterday. Check this answer:

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback