CODEWITHSUNDEEP
regexcompiler-constructiondfa
user3001571
user3001571

Reputation: 5

Compiler- DFA (a+b)* vs (a|b)* any difference between both?

do (a+b)* and (a|B)* produce the same DFA and same output? In mathematics, wherever the word 'or' is involved, we use addition operator. So does that mean that both expressions are equivalent?

Upvotes: 0

Views: 3409

Answers (3)

Szczerski
Szczerski

Reputation: 1001

(a|b)* denotes {ε, "a", "b", "aa", "ab", "ba", "bb", "aaa", aab, abb, aba, baa ...}

(a+b)* denotes {ε, ab, aab, aaab, abab, aabab,...}

ε denote empty

Upvotes: 0

nhahtdh
nhahtdh

Reputation: 56809

It depends on the context where you get the 2 regular expressions from.

If you interpret both regex in the syntax of real life regex engines, they have different meanings, as Ed Cottrell explained in his answer. + means repeating once or more. | means alternation.

However, they can mean the exact same thing, if you interpret + in (a+b)* as alternation, following the notation in most books on automata theory, and | in (a|b)* as alternation, following the notation in most real life regex engines.

Upvotes: 1

elixenide
elixenide

Reputation: 44833

No.

(a+b)* matches at least one a followed by a b, zero or more times. So, for it to match a non-empty string, the string must, at some point, contain ab.

(a|B)* requires a or b, zero or more times. It can match the empty string, a string of all as, a string of all bs, etc.

The second expression matches the entire string in the following examples: a, aa, aaa, b, bb, bbb, etc. The first expression technically matches (because a zero-length string would match), but doesn't match the entire string. The captured groups are different.

So, no, they are not equivalent.

Upvotes: 1

Related Questions