HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Infinite Intersection/Union of regular languages

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
infinitelanguagesunionregularintersection

Problem

Hello I'm having trouble understanding how an intersection/union of regular languages can be regular and in other case non-regular.

Can someone please give me some good examples?

Solution

For every word $w$, there's a language $\{ w\}$, which is regular, and $\Sigma^* \setminus \{ w\}$, which is also regular.

But, we can express every language (regular or not) $L$ as an infinite union: $L = \bigcup_{w \in L} \{ w \}$, which is an infinite union of regular languages.

For intersection, you do the opposite:

$L = \bigcap_{w \not \in L} (\Sigma^* \setminus \{w \})$.

So, we know that there are regular languages, and non-regular languages, and they can all be expressed as infinite unions or intersections of regular languages.

Context

StackExchange Computer Science Q#67316, answer score: 9

Revisions (0)

No revisions yet.