Is every formal language not closed under infinite union operation ? I know that Regual Languages are not closed under infinite union operation and I have counter-example for it but I don't have any counter-example for other languages. Intuitively , I think it should not be closed but intuition could be wrong also. So please clarify whether every language (like DCFLs,CFLs , Recursive , Recursively Enumerable) is closed or not under infinite union operation.
3 Answers
$\begingroup$
$\endgroup$
0
Virtually every standard language class contains singleton languages, e.g. those languages containing exactly one word ($L_w = \{w\}$).
If a class containing every $L_w$ were closed under infinite union then it would contain any arbitrary infinite language $L$ since
$$ L = \bigcup_{w\in L} L_w $$
More in general, we can write any language (finite or infinite) using an infinite union of singletons or empty languages.
$$ L = \bigcup_{w \in \Sigma^*} \{w\ |\ w\in L\} $$
where $\{w\ |\ w\in L\}$ is $\{w\}$ when $w\in L$ and the empty language otherwise. (I wish set comprehensions had a standard notation for free and bound variables! Here, $w$ is free.)
$\begingroup$
$\endgroup$
0
To add a more concrete example to chi's answer, in the case of CFL's, think about the following infinite union: $$\bigcup_{i=1}^\infty\{0^i1^i2^i\} = \{0^n1^n 2^n|n>0\}$$ which is a known example of a non context-free language.
$\begingroup$
$\endgroup$
0
Languages aren't closed under operations; sets of languages can be.
The set of all languages is closed under infinite union. So, the answer to your question at the start of your post is "no".
The set of DCFLs is not closed under union, so not closed under infinite union, either. For the rest, see Infinite Union of Recursive language, Is an infinite union of context-free languages always context-free?, and Infinite union of recursive languages.
