patternMinor
Use the pumping lemma to prove that {www} is not context-free
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.
$\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.
$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.