Automata Regular expression - difference between concatenation & union

Question

What is the difference between the following regular expressions? (a U b)* and (ab)*

Difference between union and concatenation ? which of the above regex accepts strings in which 'a' is always before 'b' ?

Please clarify.. Thanks in advance.

Natant

Did the answer provided clarify things for you? Or, did you still have questions? – Excommunicatory

@jason9187 yes. your answers did clarify things for me. I got it now. Thanks! – Natant

Answer 1

(ab)* means zero of more instances of the sequence ab. For example,

<empty>, ab, abab, ababab

Consider a* and b*:

a*: <empty>, a, aa, aaa, aaa, ...
b*: <empty>, b, bb, bbb, bbb, ...

Concatenation is to add one set onto another. a* concat b* would be concatenating the sequence resulting from a* with the one resulting from b*, so:

<empty>, ab, aab, abb, aaaabbbb, bbbbb

Union is to combine two sets and results in the distinct results.So, a* U b* would be the regular expressions of zero or more instances of a and zero or more instances of b:

<empty>, a, aa, aaa, aaaa, b, bb, bbb, bbbb

Excommunicatory

Thanks a lot!! I understood the difference between them. Then the set (a U b)* contains the following strings.. <empty>, a,aa,aaa,b,b,bbb,... It cannot have 'ab'. Am I right? Is there a difference between (a* U b*) and (a U b)* ? – Natant

Well, a U b is just the set [a, b] so (a U b)* (a union b zero or more times) is <empty>, a, b, ab, abaa, abbbaa, etc. The parentheses make a big difference. The Kleene star indicates zero or more instances, and the the parentheses are a grouping. But to answer your last question, yes, there is a difference b/c of how you are grouping w/ parens. Try to think about the sets created from a* or b* then apply the Union logic. – Excommunicatory