0
$\begingroup$

I came across the following statement which is supposedly true:

There exists an infinite set of regular languages, such that their union is not a CFL

it is explained this way: we'll define $L_k = \{ 0^k1^k0^k \}$

$\bigcup_{i=1}^{\infty} $ $ L_i = \left\{ 0^k1^k0^k \mid k \geq 1 \right\} $

so that each language in the union only contains one string and therefore - regular, but their union is equivalent to: $0^n1^n0^n$ which is not CF.

on the other hand regular languages are closed under union, which means it'd be easy to prove inductively that the above union = regular language, since it consists only of regular languages.

and all regular languages are CF.

isn't that a contradiction?

$\endgroup$
0

2 Answers 2

Reset to default
3
$\begingroup$

No it’s not a contradiction, by induction you can only prove a finite union of regular languages is regular, it tells you nothing about whether or not an infinite union is always regular.

$\endgroup$
1
  • $\begingroup$ @Skynet No. Induction is used to prove statements on every element of one specific infinite set: $\Bbb N$ $\endgroup$
    – Hagen von Eitzen
    Jan 29 at 18:24
1
$\begingroup$

Actually, every language $L$ on a finite alphabet is a countable union of regular languages. Just observe that all finite languages are regular and that $$ L = \bigcup_{u \in L}\ \{u\} $$ Now, you can choose for $L$ not only a non-context-free language, but a non-context-sensitive or a non-recursively enumerable one if you wish.

$\endgroup$

You must log in to answer this question.