2
$\begingroup$

How to prove that every regular subset of $L=\{a^nb^n \mid n\ge0 \}$ is finite?

I know that every finite language is regular, and it's not true that every regular language is finite.

I also know that $a^n b^n$ is non-regular language.

I can find examples of finite regular subsets of $L$, for example $\{\epsilon, ab, aabb\}$, but how do I prove that all regular subsets of $T$ are finite?

$\endgroup$
2
  • $\begingroup$ Your question doesn’t make sense. What is “a regular language in language L” supposed to mean? $\endgroup$
    – gnasher729
    Jun 26 '20 at 10:06
  • 1
    $\begingroup$ (If something looks too obvious to prove, try contradiction.) $\endgroup$
    – greybeard
    Jun 26 '20 at 22:28
3
$\begingroup$

This is a simple application of the pumping lemma. Suppose that $L'$ is an infinite subset of $L$. Given $p$, since $L'$ is infinite, there exists some $n \geq p$ such that $w = a^nb^n \in L'$. Let $w = xyz$ be a decomposition of $w$ such that $|xy| \leq p$ and $y \neq \epsilon$. Then $y = a^t$ for some $t \neq 0$, and so $xy^0z = a^{n-t}b^n \notin L'$. Therefore $L'$ is not regular.

One might be tempted to think that this argument generalizes to every $L$ whose non-regularity can be proved using the pumping lemma. However, this is incorrect, as the example of $L \cup c^*$ shows.

This raises the following intriguing question:

For which infinite languages $L$ is it the case that all regular subsets of $L$ are finite?

$\endgroup$
1
  • 1
    $\begingroup$ My guess to answer your question: if none of the strings are pumpable, so if each string of $L$ can be used with the pumping lemma to show $L$ irregular. If any string of $L$ is pumpable, then all its pumps form a regular subset. $\endgroup$ Jun 26 '20 at 12:01
1
$\begingroup$

Prove that if your language contains $a^nb^n$ and $a^mb^m$ for n <> m then after parsing $a^n$ and parsing $a^m$ you end up in different states. (Proof is trivial).

If there are infinitely many different n, m then the number of states cannot be finite.

$\endgroup$

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.