what happens when we take union of two languages and then take its reversal ?

Question

If I have two languages then according to me

(L1 UNION L2 )^r =L1^r UNION L2^r  this equality must hold true ,but I read somewhere so this equality wasn't true , so what is the conclusion ?

 

e.g . (01+11)^r = 10+11  (LHS)

now RHS will be (10+11)

So I guess equality must hold true .

Answer 1

I believe you are correct, the equality should be true in every case.

---

L1 and L2 are sets containing strings.

In (L1 U L2)^r we are firstly combining sets and then taking each string from the combined set and reversing it.

In case of L1^r U L2^r we are firstly reversing each string and then combining the sets of reversed strings.

---

Clearly Union is an operation on sets & Reversal is an operation on strings of the set.

Since ultimately you are going to reverse all the strings in L1 & L2 it does not matters whether you reverse them before Union or after.

Also finiteness of sets should not affect this equality.

Answer 2

take any two dfa .. with end with (a+b)*..

now try to apply logic u get nfa.

ur logic is true untill language is finite... check plz

Comments

I think there is no problem if we get NFA after reversal ( most of the time it happens).  We can convert it to DFA. I think the equality always holds.