Consider the problem

Show $L = \{ a^{n}b^{m}\mid m \text{ es múltiplo de } n \}$ is not regular.

I attempted the following.

Assume $L$ is regular. Then there is a natural number $p \geq 1$ such that any $w \in L$ of length greater or equal to $p$ can be written as $w = xyz$ , with $|xy| \leq p$ and $|y| \geq 1$, and such that $xy^{j}z$ is in $L$ for all $j \in \mathbb{N}$.

In particular, consider $w = a^{p}n^{pq}$ with $q \in \mathbb{Z}$. Then $w = xyz$. Because $|xy| \leq p$, we have $xy$, and hence $y$ as well, consists only of a repetition of $a$s. Let $k$ the number of $a$s in $y$ and $k'$ the number of $a$s in $x$, so that $k + k' = |xy|$.

Here is where I have trouble. I am not finding a way to raise $y$ to a certain power $j$ and show that the resulting number of $a$s, which is $k' +k(j-1)$, does not divide $pq$. Any ideas on how to follow? If this was not the correct approach, what would be a solution?

  • $\begingroup$ You can simply fix a value for $q$. $\endgroup$
    – Russel
    Commented Aug 4, 2023 at 1:10
  • $\begingroup$ $a^nb^n$ is a (well-known) non-regular example and $n$ is a multiple of $n$. $\endgroup$
    – user16034
    Commented Aug 4, 2023 at 8:16


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.