3
$\begingroup$

How can I prove that this language isn't regular using the pumping lemma for regular language?

$$L = \{a^nb^m| n,m > 0, \gcd(n,m)=1\}$$

I've already checked this answer: Proof that a language involving $gcd$ is not context-free but don't understand this part.

"Let s' be $a^{(n+ik)}b^m \ with \ k \geq 1$. Then s' e L if $gcd(n + ik, m) =$ , however the modular equation $n+ik = 0(m)$ have a solution $i = nk^{(-1)(m)}$ ..."

I don't understand how he proved, $gcd(n+ik, m) \gt 1$, could someone explain me more clearly the answer please.

Thank you.

$\endgroup$

closed as unclear what you're asking by Evil, David Richerby, jmite, Juho, Thomas Klimpel Dec 22 '16 at 18:44

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 3
    $\begingroup$ What part do you not understand? Please ask a more specific question. This one is an exact duplicate of the question you linked. $\endgroup$ – adrianN Dec 15 '16 at 16:14
  • 2
    $\begingroup$ Please edit the question to clarify why you don't understand the explanation in that answer of the first case. What's the first step you don't understand? Otherwise, I worry someone will write a different explanation but then you might say "I didn't understand that one, either". The more you can tell us about what you did and didn't understand -- the more you give us to work with -- will make it more likely we can help you. $\endgroup$ – D.W. Dec 15 '16 at 18:15
3
$\begingroup$

As you know, the Pumping Lemma for regular languages states that if $L$ is a regular language, then there is an integer $p$ such that is $s$ is any string in $L$ with length $|s|\ge p$ then we can write $s=xyz$ with

  1. $|y|>0$,
  2. $|xy|\le p$, and
  3. $xy^iz\in L$ for all $i\ge 0$.

If we let $s=a^nb^m$ for distinct primes $n,m\ge p$ then certainly $s\in L$ since $\gcd(n,m)=1$. Now we know that in this case $y=a^k$ with $0<k\le p$ and so if we pump $y$ we'll have $xy^{i+1}z=a^{n+ik}b^m$. Now we'll try to get a contradiction by showing that there is some $i$ for which $\gcd(n+ik,m)\ne 1$. We can get this if we can find an $i$ such that $m$ divides $n+ik$, since then we'll have $\gcd(n+ik,m)=m$.

In other words, we want an $i$ such that $n+ik\equiv 0\pmod m$. In modular arithmetic land we'll then have the following chain of equivalences:

$$\begin{align} n+ik &\equiv 0\pmod m\\ ik &\equiv -n\pmod m\\ i &\equiv -n(k^{-1})\pmod m \end{align}$$ The last step follows from the fact that when the modulus is prime, any nonzero value has a multiplicative inverse.

Here's an example: Suppose $p=6$, then we could pick $n=11,m=7$ and pump the string $a^{11}b^7\in L$. If it happened that $k=4$ then we could use $i=-11\cdot 2$, where the $2$ came from the fact that $4\cdot 2\equiv 1\pmod 7$. In other words, we'd have

$$ i=-11\cdot 2\equiv -22\equiv -1\equiv 6\pmod 7 $$ and then the pumped string would be $a^{11+6\cdot 4}b^7=a^{35}b^7$ and this is clearly not in $L$, since $\gcd(35,7)=7\ne 1$ $$ $$

$\endgroup$
2
$\begingroup$

An easy way to prove that this language isn't regular is using the Myhill–Nerode theorem. Let $p_i$ be an enumeration of all primes. The words $a^{p_i}$ are pairwise inequivalent, since $a^{p_i} b^{p_i} \notin L$ whereas $a^{p_j} b^{p_i} \in L$ when $i \neq j$. Since we found infinitely many pairwise inequivalent words, it follows that $L$ is not regular.

$\endgroup$

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