Automata Regular expression - difference between concatenation & union

regex kleene-star
Jadyarun picture Jadyarun · Oct 16, 2015 · Viewed 11.4k times · Source

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.

Answer

ryuu9187 picture ryuu9187 · Oct 16, 2015

(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

Related questions

Regular expression to match a line that doesn't contain a word

I know it's possible to match a word and then reverse the matches using other tools (e.g. grep -v). However, is it possible to match lines that do not contain a specific word, e.g. hede, using a regular …

Read More
How to validate an email address in JavaScript

Is there a regular expression to validate an email address in JavaScript?

Read More
RegEx match open tags except XHTML self-contained tags

I need to match all of these opening tags: <p> <a href="foo"> But not these: <br /> <hr class="foo" /> I came up with this and wanted to make sure I've got …

Read More