Is the infinite union of regular languages context free?

323 Views Asked by At

I realize that the infinite union of regular languages is not regular, but is it context free?

1

There are 1 best solutions below

0
On

No. Every language consisting of a single word is regular. However, it is also true that for any language $L$ (or, generally, any set): $$L = \bigcup_{w\in L}\{w\}.$$ Thus, every language is an infinite union of regular languages - so cannot be guaranteed to have any special properties at all.

The fact that every set is a union of singletons is often a useful thing to have in mind when you come across statements like this. A bit more generally, asking

Is $S$ an infinite union of sets $T$ satisfying property $P$?

is equivalent to asking

Is there, for every $x\in S$, some subset $T\subseteq S$ with property $P$ such that $x\in T$?

and this is often useful in a wider context - even if here, we are just applying it by noticing that $\{x\}$ has the property of being regular that we are interested in.