Проблема упрощения регулярных выражений

Question

Я пытаюсь понять эквивалентность между регулярными выражениями α и β, определенными ниже, но я схожу с ума из-за противоречивой информации.

a+b:   a or b
ab:    concatenation of a and b
$:     empty string

α = (1 * + 0) + (1 * + 0) (0 + 1) * ($ + 0 + 1)

β = (1 * + 0) (0 + 1) * ($ + 0 + 1)

https://ivanzuzak.info/noam/webapps/regex_simplifier/ говорит, что α эквивалентно β .

Однако моя школа учит, что сцепление имеет более сильную привязку, чем объединение, что означает:

11 * + 0 = / = 1 (1 * + 0)

, чтобудет означать, что мой α выглядит так с круглыми скобками:

α = (1 * + 0) + ((1 * + 0) (0+1) * ($ + 0 + 1))

и что

α = / = ((1 * + 0) +(1 * + 0)) (0 + 1) * ($ + 0 + 1)

Надеюсь, понятно, в чем моя проблема, я быценим любую помощь.Спасибо.

Answer 1

Хорошо, получается, что я неправильно понял, почему b + b <=> b.

Это L1∪L2 <=> L2, если L1 является подмножеством L2.

Answer 2

Обычно два регулярных выражения считаются эквивалентными, когда они соответствуют одному и тому же набору слов.

То, как они соответствуют, не имеет значения.Поэтому не имеет значения, какой из операторов имеет больший приоритет.

Обратите внимание на тонкую разницу между тем, чтобы быть равным (в письменной форме) и эквивалентным (имеющим тот же эффект).