1

Define the formal language UPDOWNUP as $L = \{ s(reverse(s))s,s \in (a+b)^* \} = \{aaa,bbb,aaaaaa,abbaab, baabba, bbbbbb, ... \}$

I want to show using the pumping-lemma for context free languages that this language is not context free.

My thoughts: By the pumping lemma if this was a context free language, then for any word which has length greater than $2^p$, where $p$ is the number of live productions of the grammar, then it must be of the form $w=uvxyz$ where $v,y$ cannot both be empty, and $x$ is not empty, and for any $n \in \Bbb N$

$ uv^nxy^nz$ must be in the language.

I have had the idea to try using either $a^na^na^n$ where $n > 2^p$ or $a^nb^nb^na^na^nb^n$ to find a contradiction.

In the former, it seems that If I decompose $a^{3n}$ then I notice that the new word formed by taking powers of $v,y$ must result with a word where the number of "a's" is divisible by 3 since $length((s)reverse(s)(s))=3length(s))$, but this is do-able if both $v,y$ are powers of $a$ that are divisible by 3, so I am not sure how to proceed.

If anything is unclear I will edit the post to make it more clear.

IntegrateThis
  • 3,778
  • @saulspatz yup sorry, that's a typo. – IntegrateThis Jul 11 '18 at 05:59
  • It's been a long time since I've looked at this stuff, but Wikipedia says $|vxy|\le p,$ which I guess would be $2^p$ in your formulation, and you don't seem to have stated this. Should it not apply? Also, I see that you say $x$ is not empty, which the wiki doesn't. – saulspatz Jul 11 '18 at 06:08
  • @saulspatz my description of the pumping lemma is accurate to my notes, which may differ from Wikipedia. Although I believe these definitions are equivalent as you have described. – IntegrateThis Jul 11 '18 at 06:13

1 Answers1

1

I think I can do this with the description in Wikipedia. I'll just outline my idea, and you can see if you can apply it with your definition. According to Wikipedia we must have $|vxy|\le n$ where $n$ is the pumping length. Consider the string $a^nb^nb^na^na^nb^n=a^nb^{2n}a^{2n}b^n$ The condition $|vxy|\le n$ make it clear that $v$ or $y$ (or both) can only contain one distinct symbol. Also, since every string in the language contains an equal number of $a\text{'s}$ and $b\text{'s},$ the string $vy$ must contain an equal number of $a\text{'s}$ and $b\text{'s}$ for the pumping to work.

Now you have to work though the cases. If $vxy$ overlaps the initial $a^nb^n,$ then after you pump, the first string of $a\text{'s}$ will be loner than the second string of $a\text{'s},$ and the resulting string won't be in the language. (This probably takes a bit of argument, but it seems clear.) The other cases should be similar.

I can't quite see how to proceed if we don't know that there's a bound on the length of $vxy,$ though. I notice that the formulation of the pumping lemma for context-free languages is given on Wikipedia is the same as Theorem 7.18 in the third edition of Hopcraft, Motwani, and Ullman.

saulspatz
  • 53,131