The family of regular languages

709 Views Asked by At

Is the family of regular languages closed under countable infinite unions?

If so prove it, If not give a counterexample.

3

There are 3 best solutions below

0
On

HINT: Every finite language is regular, and there are infinite languages that are not regular.

0
On

It isn't. Consider the language $L_n = \{a^nb^n\}$. For each $n$, $L_n$ is a regular language (duh, it's a finite language), yet the countable union of all such $L_n$ is the context-free language $\{a^nb^n \mid n \in \mathbb N \}$.

0
On

Given a language $L$, one has $$L = \bigcup_{u \in L}\ \{u\}.$$ Since every singleton is regular, it follows that any language is a countable union of regular languages. Thus, except if the alphabet is empty, the family of regular languages is not closed under countable unions.