HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Use the pumping lemma to prove that {www} is not context-free

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
thewwwfreeprovepumpingthatlemmacontextusenot

Problem

Use the pumping lemma to prove that the following language is not context-free.

$\qquad L = \{ w w w \mid w \in \{a,b\}^*\}$

I am studying for an exam and really trying to understand this question. For some reason the third w is throwing me off.

I first tried using the string $a^p b^p a^p b^p a^p b^p$ but didn't get very far.

The other string I tried to work through it with was $a^p b^p b^p$

Having a hard time figuring out how exactly to split it up.

Any guidance and explanation would be greatly appreciated.

Solution

You could take $w = a^m b a^m$, then you have that $uvxyz = a^m b a^m a^m b a^m a^m b a^m$
$vy = a^l$ with $1\le l\le m$ since there can't be more than one $b$, so you can't pump the $b$.
Since $vy$ can only contain $a^m$ without any $b$'s, it will obstruct the balance between the other $a^m$'s.

We've found a contradiction while applying the pumping lemma so the language is not Context-Free.

Context

StackExchange Computer Science Q#50749, answer score: 2

Revisions (0)

No revisions yet.