The family of regular languages

Question

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

If so prove it, If not give a counterexample.

score 1 · Answer 1 · answered Mar 22 '16 at 19:18

1

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

answered Mar 22 '16 at 19:18

Brian M. Scott

616,228

score 1 · Answer 2 · answered Mar 22 '16 at 19:20

1

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 \}$.

answered Mar 22 '16 at 19:20

Graffitics

1,508

score 0 · Answer 3 · answered Mar 23 '16 at 03:37

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.

The family of regular languages

3 Answers3