2
$\begingroup$

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:)

$\endgroup$
  • $\begingroup$ See the answer of jmite showing the infinite unions or infinite intersections of regular languages can build any language: cs.stackexchange.com/a/67317/4287 Hint: add or erase one word at the time. $\endgroup$ – Hendrik Jan Jun 25 at 21:11
  • $\begingroup$ Consider the case where the $L_i$ are singleton languages (of one element). $\endgroup$ – reinierpost Jun 26 at 9:49
15
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Here is a simpler formula. $L=\cap_{w\in L} L_w$, where $L_w$ is the set of all words except $w$. $\endgroup$ – John L. Aug 31 at 7:17
8
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

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.

| cite | improve this answer | |
$\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.