Prove or Disprove: an infinite intersection of regular languages is a context-free language

Question

Let $L_1, L_2,...$ and $L=\cap_{k=1}^{\infty}L_k$ be languages over $\Sigma ^{*}$.
Prove /Disprove: if $\forall k\in \mathbb{N} $, $L_k$ is a regular language, then $L$ is a context-free language.

I know that statement is false, but couldn't find an example to disprove it. Would appreciate your help:)

Answer 1

"I know that this statement is false, but couldn't find an example to disprove it."

It might come as a surprise to you that, in fact, every non-context-free language can be a counterexample. We have the following fact, assuming any fixed alphabet $\Sigma$.

---

Let $L$ be a language. Then there exist regular languages $L_1, L_2,...$ such that $L=\cap_{k=1}^{\infty}L_k$.

Proof. The other answer indicates how to construct $L_i$. For clarity, here is the construction.

Let $L_i$ be the words in $L$ with length at most $i$ together with all the words with length greater than $i$. More formally, let $L_i=\{w\in\Sigma^*: w\in L\text{ and } |w|\le i\}\cup\{w\in\Sigma^*:|w|\gt i\}$. Then $L=\cap_{k=1}^{\infty}L_k$.

Each $L_i$ is regular since $L_i$ is the union of two regular languages.

• $\{w\in\Sigma^*: w\in L\text{ and } |w|\le i\}$, as a finite set, is regular.
• $\{w\in\Sigma^*:|w|\gt i\}$ is regular.

---

So, even if $\forall k\in \mathbb{N} $, $L_k$ is a regular language, $L=\cap_{k=1}^{\infty}L_k$ can be non-regular, non-context-free, non-context-sensitive, etc.

Answer 2

To add to John L.'s answer, for some intuition: the operations of infinite intersection and infinite union typically do not preserve any properties of languages. In particular, no nontrivial class of languages is closed under infinite union or infinite intersection: not regular languages, not context free languages, not P, not NP, not Turing computable, not recursively enumerable (Turing recognizable), etc. The list goes on.

This is because infinite union and infinite intersection are just too powerful, so you can usually get every language this way. In particular,

1. Every language can be written as the infinite union of finite languages.

2. Every language can be written as the infinite intersection of "co-finite" languages, where the term "co-finite" means the complement of a finite language. (That is, the language contains every string except for finitely many of them.) This is what John L.'s answer shows.

Now, finite languages and co-finite languages are the very simplest of languages -- they are in particular regular. So every language can be written as the infinite union or infinite intersection of regular languages.

Answer 3

Consider $L_n = \{a^2, a^3, a^5 \ldots a^n, a^{n+1} \ldots \} $ (only prime length strings over $a$ till the length $n$, and all strings over $a$ of length greater than $n$) if $n$ is prime, else $L_n = \Sigma^*$. Note that each of these $L_n$ is regular (Why?).

It’s easy to see that the infinite intersection language would contain the strings over $a$ of prime length, i.e., $L = \{a^p | p \text{ is prime} \}$.

It can be proved easily using pumping lemma that this language isn’t context free.