Вариант 1 кажется мне лучше, вероятно, потому что я не представляю, как реально выполнить Вариант 2. Я бы порекомендовал это:
- построить DFA M1 такой, что L (M1) =($ + b) a * (b + bba *) *
- построить DFA M2 так, чтобы L (M2) = b * (a + bb + bbb) b
- построить DFA M12 так, чтобы L (M12) = L (M1) \ L (M2)
- построить DFA M21 так, чтобы L (M21) = L (M2) \ L (M1)
- регулярные выражения описывают один и тот же язык, если только L (M12) и L (M21) пусты
Чтобы узнать, принимает ли DFA M пустой язык, вы можете:
- построить M 'путем минимизации M
- посмотреть, принимает ли M' пустой язык, проверяя, является ли начальное состояние пустым и имеет ли все переходы, инициирующие в начальном состоянии, заканчивающиеся в начальном состоянии
Чтобы свести к минимуму 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
Способ построения автомата изрегулярное выражение выглядит следующим образом:
- если r = x, где x - некоторая строка над алфавитом языка, то NFA для r можно построить, добавив одно начальное состояние и одно дополнительное состояние для каждогосимвол х;затем сделайте принятие последнего из этих состояний;
- , если r = st, а M и M 'являются NFA для s и t, тогда NFA для r можно построить, изменив все принимающие состояния M на не-принятие при добавлении лямбда-переходов в ранее начальное состояние M ', которое больше не является начальным.
- , если r = s + t и M и M' являются NFA для s и t, то NFA дляr можно построить, добавив новое начальное состояние с лямбда-переходами к ранее начальным состояниям M и M ', которые больше не являются начальными;
- , если 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' ввторая машина.Начальное состояние является тем, которое соответствует паре начальных состояний в машинах ввода;принимающие состояния - это те, которые (для разности) имеют х принимающих и у не принимающих (для симметричной разности, это те, которые имеют либо х принимающих, либо у принимающих, но не оба).