Эквивалентность между регулярными выражениями

(2) требуется много правил переписывания и эквивалентности, чтобы вы могли гарантировать это в общем случае. Конечно, если вы просто пытаетесь сделать это для этих двух конкретных регулярных выражений, то вы можете работать ad hoc.

(1), однако, «реальный» способ сделать это. Я удивлен, что вы знаете, как использовать лемму Ардена, но не обратное направление, которое гораздо более распространено (в учебниках и на практике) и проще. Буквально любая книга формальных языков или любая книга компиляторов даст вам по крайней мере один алгоритм для сопоставления регулярного выражения с DFA, а также для минимизации DFA. Если у вас нет доступа к таким книгам, я укажу вам на две статьи, которые я написал несколько лет назад, каждая из которых представляет таксономию (в то время всеобъемлющую) алгоритмов, одну для отображения регулярного выражения в DFA, а другую для минимизации. DFA: http://www.kornai.com/EFS/OnlineSupportMaterial/Watson/Papers/constax.600dpi.ps https://www.researchgate.net/publication/2247379_A_Taxonomy_of_Finite_Automata_im ]

Вариант 1 кажется мне лучше, вероятно, потому, что я понятия не имел, как реально выполнить Вариант 2. Я бы порекомендовал это:

1. построить DFA M1 такой, что L (M1) = ($ + b) a * (b + bba *) *
2. построить DFA M2 так, чтобы L (M2) = b * (a + bb + bbb) b
3. построить DFA M12 так, чтобы L (M12) = L (M1) \ L (M2)
4. построить DFA M21 так, чтобы L (M21) = L (M2) \ L (M1) [ 119]
5. регулярные выражения описывают один и тот же язык, если только L (M12) и L (M21) пусты

Чтобы узнать, принимает ли DFA M пустой язык, вы можете: [1121 ]

1. построить M 'путем минимизации M
2. посмотреть, принимает ли M' пустой язык, проверяя, является ли начальное состояние пустым и имеет ли все переходы, инициирующие в начальном состоянии, заканчивающиеся в начальном состоянии [ 1112]

Чтобы минимизировать DFA, вы можете начать с перечисления каждой пары состояний DFA. Затем вычеркните любую пару, где одно состояние в паре принимает, а другое - нет. Затем, итеративно, вычеркните любую пару (q, q '), где q переходит в некоторое состояние p на символе s, q' переходит в какое-то состояние p 'на символе s, а (q, q') уже вычеркнуто. Продолжайте до тех пор, пока больше не будут перечеркнуты пары состояний. В этот момент любые не вычеркнутые пары представляют эквивалентные состояния во входном автомате и могут быть объединены в минимальный автомат. Это всего лишь один метод. Другие методы доступны.

q    s    q'
q0   a    q1
q0   b    q2
q1   a    q1
q1   b    q3
q2   a    q2
q2   b    q3
q3   a    q3
q3   b    q0

Здесь, q0 является начальным и q3 принимает. Мы попробуем первый алгоритм:

    q0    q0    q0    q1    q1    q2
    q1    q2    q3    q2    q3    q3
#   --    --    --    --    --    --
1               XX          XX    XX   // q0,q1,q2 are not accepting; q3 is
2   XX    XX                           // on input b these go to q2,q3
3                                      // can't cross out q1,q2 by any rule

Мы находим, что q1 и q2 эквивалентны и могут быть объединены, чтобы дать следующий эквивалентный DFA:

q    s    q'
q0   a    q12
q0   b    q12
q12  a    q12
q12  b    q3
q3   a    q3
q3   b    q0

Способ построения автомата из регулярное выражение выглядит следующим образом:

1. если r = x, где x - некоторая строка над алфавитом языка, то NFA для r можно построить, добавив одно начальное состояние и одно дополнительное состояние для каждого символ х; затем сделайте принятие последнего из этих состояний;
2. если r = st, а M и M 'являются NFA для s и t, то NFA для r можно построить, изменив все принимающие состояния M на не -принятие при добавлении лямбда-переходов в ранее начальное состояние M ', которое больше не является начальным.
3. Если r = s + t и M и M 'являются NFA для s и t, то NFA для r можно построить, добавив новое начальное состояние с лямбда-переходами к ранее начальным состояниям M и M', что больше не являются начальными;
4. если r = s * и M является NFA для s, тогда NFA для r можно построить, добавив новое принимающее начальное состояние с лямбда-переходом к ранее начальному состоянию M, в то время как добавление лямбда-переходов из ранее принимающих состояний M в это новое начальное состояние.

Когда у вас есть NFA для регулярного выражения, вы можете определить его, используя конструкцию powerset или subset. Для этого создайте DFA, который имеет одно состояние для каждого подмножества набора состояний NFA. Затем добавьте переход из подмножества X в подмножество Y, если входной символ s переводит NFA из состояния x в состояние y, где x находится в X, а y находится в Y. Примечание. Сначала можно удалить лямбда-переходы, если это поможет вам Подумайте об этом или воспользуйтесь соглашением, что если s принимает NFA от q до q 'и имеет место лямбда-переход от q' к q '', то s также принимает NFA от q к q ''. Начальное состояние - это состояние, содержащее только начальное состояние NFA; все состояния, содержащие принимающее состояние, принимают.

Это поможет вам выполнить шаги 1 и 2. На этом этапе может быть полезно свести к минимуму согласно предложению, приведенному для шага 5. Затем, используйте конструкцию машины декартовых продуктов, чтобы найти DFA для различий (или просто построить один машина для симметричной разности и сохранения шага). Каждое состояние в продукте продукта будет соответствовать паре состояний, одно из которых берется из первого устройства ввода, а другое - из второго устройства ввода. Затем добавьте переходы в машине продукта, которые переводят DFA из состояния (x, y) в состояние (x ', y') везде, где одновременно происходят переходы от x к x 'на первой машине и от y к y' в вторая машина. Начальное состояние является тем, которое соответствует паре начальных состояний в машинах ввода; Принимающие состояния - это те, которые (для разности) имеют x принимающий и y не принимающий (для симметричной разности, это те, которые имеют либо x принимающий, либо y принимающий, но не оба).