4
$\begingroup$

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?

$\endgroup$
3

2 Answers 2

9
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ OK and how about an infinite union/intersection of regular languages that is non-regular? that is what troubles me more. $\endgroup$
    – Yogzis
    Dec 13, 2016 at 2:39
  • 2
    $\begingroup$ @Yogzis. You misunderstand my answer. You can use the construction above to construct any language: regular, non-regular, undecidable, etc. You pick your $L$, and we can define it as an infinite union or intersection of regular languages. $\endgroup$ Dec 13, 2016 at 2:52
0
$\begingroup$

Every regular language can be described as a DFA. So assume you have a DFA that represents language one, and a DFA that represents language two. Now construct a third DFA that represents the union of the first two DFA. Construct another DFA that represents the intersection of the first two DFA.

$\endgroup$
2
  • $\begingroup$ Since the resulting DFAs exist, then so does the the regular languages that correspond to this $\endgroup$ Dec 13, 2016 at 8:59
  • 1
    $\begingroup$ This seems to half-answer half the question (why a finite union of regular languages is regular) but doesn't address the infinite part. $\endgroup$ Dec 13, 2016 at 13:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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