If i have a language like $L = \{a^n b^m c^n b^m a^n \mid m,n\ge0\}$

when i pick a word for the language, would it be correct if i pick any of

these words: $w = a^k c^k$, $w = a^k b^m c^k $, $w = b^m b^m$, $w = b^m c^n b^m$.


If you want to apply the pumping lemma for regular languages, you can pick any word in the language whose length is no less than the pumping length. The same applies to the pumping lemma for context-free languages.

However, some of the words in your list may not be in the language.

$a^k c^k$ is in the language if and only if $k=0$.
$a^k b^m c^k $ is in the language if and only if $k=0$ and $m$ is even.
$b^mb^m$ is always in the language.
$b^m c^n b^m$ is in the language if and only if $n=0$.

Yes, a general approach is to check the balance between different symbols. Had the language been $\{a^nc^n\mid n\ge0\}$ or $\{a^n b^m c^n b^m\mid m,n\ge0\}$, you could select $a^kc^k$ towards a contradiction. You cannot if the language is $\{a^n b^m c^n b^m a^n \mid m,n\ge0\}$, since $a^kb^k$ is not a word in the language in the first place. For that language, you can choose $a^kc^ka^k$.

Specifically, here are all the words in $\{a^n b^m c^n b^m a^n \mid m,n\ge0\}$. Note that all of them start and end with the same symbol.

$$\begin{align} &\epsilon,\\ &aca,\ a^2c^2a^2,\ a^3c^3a^3,\ a^4c^4a^4,\ \cdots\\ &bb,\ a^1bc^1ba^1,\ a^2bc^2ba^2,\ a^3bc^3ba^3,\ a^4bc^4ba^4, \cdots\\ &b^2b^2,\ a^1b^2c^1b^2a^1,\ a^2b^2c^2b^2a^2,\ a^3b^2c^3b^2a^3,\ a^4b^2c^4b^2a^4,\ \cdots\\ &b^3b^3,\ a^1b^3c^1b^3a^1,\ a^2b^3c^2b^3a^2,\ a^3b^3c^3b^3a^3,\ a^4b^3c^4b^3a^4,\ \cdots\\ &\vdots \end{align}$$

  • $\begingroup$ @Apass.JackThanks for your answer, i've been told that the contradiction, by the way, is that balance between different symbols, . so if "k" is the number from the pumping lemma , and select $w=a^k c^k $ as the word to work with, and then say w=xyz where $|xy| \leq k$ , |$y| \gt 0$ . then $ y=a^j$ when i pump into the "a" part , $xyyz= a^{k+j} c^k $ that gives more a's than c's which is not in the language, which contradicts the assumption that L is regular. would this be a right approach to prove when i select that as my word $\endgroup$ – chelseablue Dec 22 '18 at 12:08
  • $\begingroup$ i see , what if i chose $ a^k c^k a^k$ instead . or $ a^k b^k c^k$ ? , and finally to be fully sure that the word picked is in the language , do you need to give n and m different input to generate those words ? if i ask this differently ,how would you know that a word is or not in the language? $\endgroup$ – chelseablue Dec 22 '18 at 14:26
  • $\begingroup$ it is ok , Could you please explain how can you determine word $ a^k c^k b^k $ is in the language but Not $ a^k b^k c^k $ its not clear to me. or how can you check in general if the word is in the language or not. $\endgroup$ – chelseablue Dec 22 '18 at 15:04
  • $\begingroup$ You select any values for $m$ and $n$ and then use them. For example, selecting $m=2$ and $n=3$, you get $a^3b^2c^3b^2a^3$. Selecting $m=k$ and $n=0$, you get $a^kc^ka^k$. Selecting $m=0$ and $n=2k$, you get $b^{2k}b^{2k}$. Now, take a moment to think, how can select $m$ and $n$ so that you can get words like $a^kb^kc^k$? You cannot; unless you select $m=0$ and $n=0$, you can get $a^0b^0c^0b^0a^0$, which is $\epsilon$. $\endgroup$ – Apass.Jack Dec 22 '18 at 15:23
  • $\begingroup$ Words like $a^kb^kc^k$ end with $c$ unless $k=0$. Words like $a^n b^m c^n b^m a^n$ end with $a$ unless $n=0$. To make them the same, $k$ must be 0 and $n$ must be 0. That is, both words are the empty word. $\endgroup$ – Apass.Jack Dec 22 '18 at 15:33

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.