patternMinor
Infinite Intersection/Union of regular languages
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?
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.
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.