Is union is regular expression different from union in set?

Question

In mathematical set we have

A={1,2,3} B={4,5,6}

A U B = B U A = {1,2,3,4,5,6} ={6,5,2,3,4,1} //order does not matter

But in theory of computation we get

a u b is either a or b but not both

also in a* u b* we get aaa or bbb but not aaabbb or bbbaaa as order does not matter in union.

why is that?

Thanks Rahman

why?

Answer 1

No. In formal language theory, there is a correspondence between regular expressions and regular sets over an alphabet Σ. The function L maps a regular expression u to the corresponding regular set L(u); conversely, every every regular set A corresponds to a regular expression in L-1(A):

L(∅)   = ∅
L(λ)   = {λ}
L(a)   = {a}              (for all a ∈ Σ)
L(uv)  = L(u)L(v)       = {xy ∈ Σ* : x ∈ L(u) ∧ x ∈ L(v)}
L(u|v) = L(u) ∪ L(v)    = {x ∈ Σ* : x ∈ L(u) ∨ x ∈ L(v)}
L(u*)  = ∪[i ∈ ℕ] L(u)i = ∪[i ∈ ℕ] {xi ∈ Σ* : x ∈ L(u)}

The union of regular expressions corresponds to the union of regular sets, which is the familiar union operation from set theory. A regular expression u matches a string x iff x is a member of the corresponding set L(u). Therefore, u|v matches x iff x is a member of L(u) ∪ L(v).