Очевидно, что есть много способов сделать это - любой логический аргумент может служить веским доказательством. Однако поучительный метод ответа на этот вопрос заключается в использовании алгоритмов для вычисления ответа на общий вопрос.
Два языка равны, если каждый содержит другой. Если один язык содержит другой, разница между содержащимся языком и содержащим языком является пустым набором. Следовательно, если два языка A и B равны, то A \ B и B \ A оба пусты; и если A \ B и B \ A оба пусты, то A и B должны быть равны.
Учитывая регулярное выражение, существует по крайней мере один известный правильный алгоритм для преобразования его в эквивалентную NFA с лямбда / эпсилон-переходами. Такая конструкция используется в каноническом доказательстве эквивалентности регулярных выражений и конечных автоматов.
Учитывая NFA с лямбда / эпсилон-переходами, существует по крайней мере один известный правильный алгоритм для преобразования его в эквивалентный DFA. Конструкция подмножества - такой алгоритм.
Учитывая два DFA, существует по крайней мере один известный правильный алгоритм для создания DFA, который принимает разницу языков, принятых этими двумя DFA. Декартово произведение Машинная конструкция - такой алгоритм.
Для DFA существует алгоритм, позволяющий определить, принимает ли он пустой язык. Минимизация DFA с последующей проверкой любых принимающих состояний является таким алгоритмом.
Следовательно, чтобы алгоритмически определить, равны ли два регулярных выражения r1 и r2:
- генерирует NFA-лямбда N1 для r1
- генерирует NFA-лямбда N2 для r2
- создать DFA D1 для N1
- создать DFA D2 для N2
- создать DFA D12 для L (D1) \ L (D2)
- создать DFA D21 для L (D2) \ L (D1)
- генерировать DFA M12 путем минимизации D12
- генерировать DFA M21 путем минимизации D21
- L (r1) = L (r2) тогда и только тогда, когда M12 и M21 оба принимают пустой язык
Когда сомневаешься, разберись