10

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.

Jadyarun
  • 117
  • 1
  • 2
  • 6

1 Answers1

6

(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
ryuu9187
  • 1,162
  • 7
  • 15
  • Thanks a lot!! I understood the difference between them. Then the set (a U b)* contains the following strings.. , 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)* ? – Jadyarun Oct 17 '15 at 22:26
  • 1
    Well, a U b is just the set [a, b] so (a U b)* (a union b zero or more times) is , 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. – ryuu9187 Oct 19 '15 at 12:53