4
$\begingroup$

Why are Regular sets not closed under infinite unions and intersections, with my flawled reasoning I came to a conclusion that since infinite unions can have no relationship between strings of a language hence it must be regular but the opposite is infact true, can you please help me understand why so, and under what conditions is generally a language considered regular then (apart from the obvious reasons, a Finite automata can be drawn, regex can be written, a set has to be finite)?

$\endgroup$
1
6
$\begingroup$

Look at $$\ell=\{a^p\mid p\text{ is prime}\}.$$

This language obtain from infinite union of $$\bigcup_{i\geq 2, i\text{ is prime}}^{\infty}L_i$$ Where each $L_i=\{a^i\mid i\text{ is prime}\}$ that have one word.

Another example is $\{a^nb^n\mid n\in\mathbb{N}\}$ That isn't regular and we can describe it by infinite union of regular languages $$\bigcup_{i\geq 1}^{\infty}a^ib^i=a^1b^1\cup\dots.$$ Each $a^ib^i$ is language that have one word.

For intersection, i recommend you read the following link.

$\endgroup$
4
$\begingroup$

You state: infinite unions can have no relationship between strings of a language. Can you explain what you mean by this?

Meanwhile, every language is the infinite union of the singleton languages that each contain one element of the language. Clearly, not every language is regular.

$\endgroup$
1
  • 1
    $\begingroup$ Likewise, every language is the infinite intersection of cofinite languages (complements of singleton languages), so by the same logic every language is an infinite intersection of regular languages. $\endgroup$ Jul 28 at 2:17

Not the answer you're looking for? Browse other questions tagged or ask your own question.