Компилятор DFA (a + b) * vs (a | b) * любая разница между обоими?

Question

do (a + b) * и (a | B) * производят тот же DFA и тот же выход? В математике, где используется слово «или», мы используем оператор сложения. Значит ли это, что оба выражения эквивалентны?

Answer 1

Это зависит от контекста, из которого вы получаете 2 регулярных выражения.

Если вы интерпретируете оба регулярных выражения в синтаксисе двигателей регулярных выражений реального времени, они имеют разные значения, такие как Ed Cottrell explained in his answer. + означает повторение один или несколько раз. | означает чередование.

Однако они могут означать одно и то же, если вы интерпретируете + в (a+b)* как чередовании после обозначения в большинстве книг по теории автоматов и | в (a|b)* как чередовании, следуя обозначения наиболее реальными долговечные двигатели.

Answer 2

No.

(a+b)* матчи по меньшей мере, один a следуют через b, ноль или более раз. Таким образом, для соответствия непустой строке строка должна в какой-то момент содержать ab.

(a|B)*a или b, ноль или более раз. Он может соответствовать пустой строке, строку всех a с, строку всех b с и т.д.

Второе выражение совпадает со всей строкой в ​​следующих примерах: a, aa, aaa, b, bb, bbb и т. д. Первое выражение технически соответствует (потому что строка нулевой длины будет соответствовать), но не соответствует всей строке. Захваченные группы разные.

Таким образом, нет, они не эквивалентны.