Prove this language is not context-free

64 Views Asked by At

Let $L = \{ww^Rw|w \in \{ a, b, c\}^*\}$

I am using the pumping lemma for CF languages. [...]

I split the string into 4 regions, which we'll call 1, 2, 3, & 4.

aaaa...aabb..bbbaaa...aaabbb....bbb

|.....1.....||.....2.....||....3....||.....4.....|

This part of the proof is where I am not sure what to do, I need to list the possible cases but I am not exactly sure what they would be. v, y could overlap I suppose, and be in each region, would that be conclusive? I guess I am not sure how many cases I should be covering here and what regions they should involve.

Edit: I should also mention that maybe it would be more suitable if my sample string contained some c's.

1

There are 1 best solutions below

3
On

HINT: If $p$ is the pumping length, try starting with $a^pb^pc^{2p}b^pa^{2p}b^pc^p$; this is in $L$ with $w=a^pb^pc^p$.