Let the language $$ L = \{ a^nb^m : m,n \text{ has the same integer-quotient, (ignoring the remainder) } \} $$

Show that $L$ isn't regular using the pumping-lemma.

Let's assume by contradiction that $L$ is regular, then there's a constant $p$ which answers the conditions of the lemma for every $w\in L$.

Let's observe at the word $w = a^pb^p$. Obviously, $w\in L$ and since $\left|w\right| \gt p$, we may use the pumping lemma for $w$.

$w = xyz$. Let's assume that $xy$ has the form $a^k$ or $b^k$. WLOG, $xy \in a^p$. Then, $w = a^ka^jb^p$ where $k + j = p$.

Let's observe at $w' = xy^0z = xz = a^kb^p$. By the pumping lemma, $w' \in L$.

But, it is uncertain that $k$ and $p$ has the same quotient.

Question: Is that enough to claim that it is uncertain? If not, what should I do instead?


closed as unclear what you're asking by D.W., David Richerby, Luke Mathieson, Nicholas Mancuso, lPlant May 26 '15 at 0:29

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.

  • 2
    $\begingroup$ This question appears to be unsuited for this site because questions of the form: "This is the exercise problem, this is my solution. Please grade!" are not interesting for anyone but you. Please see this related meta discussion. If you want to ask a specific question about a specific part of your attempt, please edit the question accordingly and it may be reopened. Otherwise, you might want to visit Computer Science Chat and get some feedback there. $\endgroup$ – Raphael May 21 '15 at 16:06

This problem can be tidied up using the floor function, where $\lfloor x\rfloor$ denotes the smallest integer greater than or equal to $x$. For example, we have $\lfloor 3.14\rfloor=3$ and $\lfloor 6\rfloor=6$. In particular, if $n$ and $m$ are positive integers, then $\lfloor n/m\rfloor$ is the quotient you obtain when you divide $n$ by $m$ (i.e., throw away the remainder).

Then, for integers $q>0$ you have a family of languages $$ L_q=\{a^nb^m\mid \lfloor n/m\rfloor=q\} $$ We'll generalize your proof slightly to show that $L_q$ is not regular for any integer $q>0$. For a fixed $q$ assume that $L_q$ was regular. Then the Pumping Lemma implies that there is an integer $p$ such that any string $w\in L_q$ of length greater than or equal to $p$ can be written as $w=xyz$ with

  1. $xy^iz\in L_q$ for any $i\ge 0$
  2. $|y|>0$
  3. $|xy|\le p$

Choose the string $a^{pq}b^p\in L_q$ and write $a^{pq}b^p=xyz$ as above. Then, as you noted, we may say $xy=a^k$ without loss of generality (the case where $xy=b^k$ will be handled in the same way as below and the case where $xy=a^ib^j$ will produce an immediate contradiction for $xy^2z$, since it will be the wrong form to be in $L_q$).

Now we know that $y=a^j$ for some $0<j\le p$. The first inequality comes from condition (2) of the PL and the second comes from condition (3). As you noted, we'll then have $$ xyz=(a^r)(a^j)(a^{pq-r-j}b^p) $$ and so $$ xz=(a^r)(a^{pq-r-j}b^p)=a^{pq-j}b^p $$ Now we'll show that $xz\notin L_q$, contradicting condition (1) of the PL. If, to the contrary, $xz\in L_q$, we'd have to have $$ \left\lfloor\frac{pq-j}{p}\right\rfloor=q $$ but $$ \left\lfloor\frac{pq-j}{p}\right\rfloor=\left\lfloor q-\frac{j}{p}\right\rfloor $$ But now we came to the heart of your question: since $0<j\le p$ by (2) and (3) we'll have $q-1\le q-(j/p) < q$, so $$ \left\lfloor\frac{pq-j}{p}\right\rfloor=q-1 $$ and so $xz\notin L_q$, giving us the contradiction we needed, completing the proof that $L_q$ is not regular for any $q>0$.

  • 1
    $\begingroup$ Please consider not to encourage undesirable posting behaviour. In particular, you may want to consider the possibility that this user in particular is trying to crowdsource their homework. $\endgroup$ – Raphael May 21 '15 at 16:07
  • $\begingroup$ @Raphael. While it may have been obscured by my verbiage, I was answering the question in the last two lines of the OP, which I felt was a perfectly reasonable query. $\endgroup$ – Rick Decker May 21 '15 at 16:14
  • 2
    $\begingroup$ Well, it's your time; for me it has the feeling of "please make sure I get full credit" (also considering the user's other questions). $\endgroup$ – Raphael May 21 '15 at 16:15

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