Cheap and Secure Web Hosting Provider : See Now

[Solved]: Proving a language isn't regular using the pumping lemma

, , No Comments
Problem Detail: 

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?

Asked By : Elimination

Answered By : Rick Decker

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$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/42834

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback