Search code examples
regexcompiler-constructiondfa

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?


Solution

  • 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.