3
$\begingroup$

Can someone explain to me if this is true or not?

$\endgroup$
2
$\begingroup$

No.

A counterexample is simply $E=\{a^nb^n\mid n\ge0\}$, the classic context-free language that is not regular.

For the sake of contradiction, suppose $E$ has an infinite regular subset $S$. So $S$ satisfies the pumping lemma for regular languages. Suppose $p\ge1$ is a pumping length of $S$. Since $S$ is infinite, $w=a^mb^m \in S$ for some $m\ge p$. Since $|w|=2m\gt p$, $w$ can be written as $w=xyz$, satisfying the following conditions:

  • $|y| \geq 1$
  • $|xy|\leq p$
  • $\forall n\geq 0$, $xy^{n}z\in S$

Since $|xy|\le p$ and $w$ starts with at least $p$ $a$'s, $y=a^k$ for some $k\ge1$. Since $xz=xy^0z$ has less $a$'s than $b$'s, $xz\not\in S$. This contradiction shows that $S$ is not regular. That is, no infinite subset of $E$ is regular.

What we just showed above is the fact that given any language, if every word in it cannot be pumped as in the pumping lemma for regular languages, then that language does not contain an infinite regular subset.


Here is a related exercise.

Exercise. A language is called prefix-closed if all prefixes of every string in the language are also in the language. Let $P$ be an infinite, prefix-closed, context-free language. Show that $P$ contains an infinite regular subset.

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