2
$\begingroup$

Lets say that we have the language L = { $a^n$$b^m$$c^{m+n}$ $|$ $m$,$n$ $>=0$ } What is the way that i should follow to prove

that the language is not regular?

  • Assume that the language is regular.
  • So,there is a string $w\in L$ such that $w = xyz$ , $|xy|\leq n, y\neqε $, n is the pumping length

Lets say that the string that i choose( w string) is $w = a^nb^mc^{m+n}$

Is this choice correct ? Can someone explain me the best choice of $y$ ?

Should be $y = a^{n-r} $ and $x = a^n $ ? Because of $|xy|\leq n$ ?

Thank you and sorry for my english.

$\endgroup$
1
$\begingroup$

Pumping Lemma for regular languages (by Wikipedia):
Let $\displaystyle L$ be a regular language. Then there exists an integer $\displaystyle p\geq 1$ depending only on $\displaystyle $ such that every string $\displaystyle w$ in $\displaystyle L$ of length at least $\displaystyle p$ ($\displaystyle p$ is called the "pumping length") can be written as $\displaystyle w=xyz$ (i.e., $\displaystyle w$ can be divided into three substrings), satisfying the following conditions:

  1. $\displaystyle |y|\geq 1$
  2. $\displaystyle |xy|\leq p$
  3. $\displaystyle (\forall k\geq 0)(xy^{k}z\in L)$

Task
The given Language is $L = \{a^nb^mc^{n+m}|m,n\geq 0\}$. We want to show that L is not regular through proof by contradiction using the pumping lemma.

First we assume that $L$ is regular as you wrote. This implies the existence of the pumping length $p$. You called the pumping length $n$ which might lead to confusion cause $n$ appears in the definition of the language; so I called it $p$. Since we make a proof by contradiction we need to choose a word $|w| \geq p, w\in L$ and show for every possible partition into $w = xyz, |xy|\leq p, |y|\geq 1$ that there is a $k$ such that $xy^kz\notin L$.

Now what $w$ could you choose? I think $a^pb^pc^{2p}$ is a good choice. Because $w = xyz = a^pb^pc^{2p}, |xy|\leq p, |y| \geq 1$ implies that $x = a^{i}, y = a^j, i+j \leq p, j\geq1$ thus $xy^pz \notin L$ because the the string would look like $a^{i+p\cdot j}b^pc^{2\cdot p}$ and $i+p\cdot j + p \neq 2p$, so the property of the language is violated. That's how proof using the pumping lemma usually looks like.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ So, you choose the word $a^pb^pc^2p$ because the sum of the powers of a,b must be on the power of c. After this, cause of $|xy| < p$ , x and y must contain only a's and not b's or c's So the $z$ part of the word is something like -> $z = a^{p -i -j}b^pc^{2p}$ ? $\endgroup$ – TuMama Jul 7 at 13:06
  • $\begingroup$ yes exactly. the word $w$ you choose must be in the language $w\in L$. and your equation for $z$ is right. $\endgroup$ – plshelp Jul 7 at 13:14
  • $\begingroup$ Ok thank you for the explanation! $\endgroup$ – TuMama Jul 7 at 13:15
  • $\begingroup$ This works, but a trifle easier is to pump $a^pc^p$. $\endgroup$ – Rick Decker Jul 7 at 18:40
  • $\begingroup$ right i didn't notice that.. $\endgroup$ – plshelp Jul 7 at 20:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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