DFA - Union and Intersection

Question

Please explain the UNION and the INTERSECTION of two DFAs with suitable examples. I looked over the internet and I'm not satisfied with any of the explanations I came across.

Answer 1

A Regular Language is closed under Union and Intersection. And every Regular Language has a DFA.

Here's what I mean:

Union:

Two Languages are said to be closed under Union if the language produced by both the languages (when combined) is still accepted by some DFA.

Example: Let L1 be a language producing w = aⁿb^m  and n,m>=0

                Let L2 be a language producing w = {a,b}* where no. of a and  b is even 

               So, L1 = {aaabbb,abbb,aaaaaab,.....}

                     L2 = {aabb,ab,...}

                     What will be the union of the above languages? Notice L1 can produce almost any combination of 'a followed by b'                         which includes some 'even number of a followed by even number of b'. Thus we can say L2 is a subset of L1.                             Thus the union of L1 and L2 = L1, which we already know has a DFA. Thus Regular grammars are closed under                             Union.

Intersection:

Please refer to the same languages introduced above.

What will be the intersection? Those languages that are common in both L1 and L2. Since we already know L2 is a subset of L1, thus we know that their intersection will result in L2 (since it exists both in L1 and L2), which is why regular grammars are also closed under Intersection

You could try with other examples and see if the final language will also be accepted by some DFA. 

Comments

@Warlock lord,

You took examples of two languages where one language is a subset of another. What if that's not the case?

Suppose this example -
L1 = Set of all strings over {a, b} where each string starts with 'a' and ends with 'b'
L2 = Set of all strings over {a, b} where each string has even length

How would you find the union or intersection of these two languages?

Also, suppose you know the minimal DFAs for both L1 and L2. How would you construct union and intersection of both DFAs?

---

Yeah I just wanted to make a point that's why I took a simple example. The set of string that you will achieve by union or intersection of two regular languages will always give you another regular language. As far as the Regular Languages are concerned, they are always closed under Union and Intersection. A more formal proof can be found in text books. 

L1 = {ab,aabb,abababab......}      (language that starts from 'a' and ends in 'b')

L2 = {ab,aabb,abababab,bbaaaa,aabbbb....}    (language that has string of even length)

Union of this language can be defined as "A language that has even no. of string or starts with a and ends with b". Create minimal DFA for both separate scenarios and join them to form the dfa.

Intersection will give a language with set of words that is "even in length and starts with a and ends in b" for which a DFA can be created very easily.

For your last question, Union can be done by joining two DFA's, which is also mentioned in peter linz if I remember clearly. Intersection on the other hand, as far my knowledge goes you just have to create another DFA, not sure if you can derive from the two dfa's.

---

also sir what would be the concatenation of the above two languages .... i want to know the difference between concatenation and intersection