Ответ 1
Как вы говорите в вопросе:
Я знаю, что для преобразования DFA, M в дополнение, M`, мне просто нужно поменять начальные принимающие состояния и конечные принимающие состояния.
Это не дополнение, но вы делаете что-то вроде обратного языка и обычные языки закрываются при развороте.. a >
Сторнирование DFA
Что такое язык реверса?
Обращение к языку L (обозначается L R) - это язык, состоящий из обращение всех строк в L.
Учитывая, что L является L (A) для некоторого FA A, мы можем построить автомат для L R:
отмените все ребра (дуги) на диаграмме перехода
принимающее состояние для автомата L R является начальным состоянием для A
создать новое начальное состояние для нового автомата с переходами epsilon в каждое из состояний принятия для A
Примечание. Отменив все свои стрелки и обменяв роли начального и принимающего состояний DFA, вы можете получить NFA. , почему я написал FA (не DFA)
Дополнение DFA
Поиск дополнения DFA?
Defination: Дополнение языка определяется в терминах заданной разницы от Σ * (сигма-звезда). то есть L '= Σ * - L.
И язык дополнения (L ) L имеет все строки из Σ * (сигма-звезда), за исключением строк в L. Σ * - все возможные строки над алфавит Σ.
Σ = Набор языковых символов
Чтобы построить DFA D, который принимает дополнение к L, просто преобразуйте каждое принимающее состояние в в не принимающее состояние в D и преобразование каждое не принимающее состояние в в состоянии принятия в D.
(Предупреждение! Это неверно для NFA)
A является DFA L, D для дополнения
Примечание. Чтобы построить дополнение DFA, старый DFA должен быть полным средством, чтобы все возможные переходы из каждого состояния (или, другими словами, δ должна быть полной функцией).
Дополнение DFA для регулярного выражения
(00+1)*
ниже DFA с именем A:
Но не этот DFA не является полным DFA. функция перехода δ частично определена, но не для полной области Q×Σ (отсутствует выходное ребро из q1 для lable 1).
Его полный DFA может быть следующим (A):
В приведенном выше DFA все возможные транзакции определены (* для каждой пары Q,Σ *), а δ - полная функция в этом случае.
Reff: узнать, что такое Частичная функция.
Новое дополнение DFA D может быть построено путем изменения всех конечных состояний q0 до не конечных состояний и наоборот.
Таким образом, в дополнении q0 становятся не финальными, а q1, q2 - конечными состояниями.
Теперь вы можете написать Regular выражение для языка дополнений, используя ARDEN THEOREM и DFA.
Здесь я пишу регулярное выражение для дополнения непосредственно:
(00 + 1)* 0 (^ + 1(1 + 0)*)
где ^ - пустой символ.
некоторые полезные ссылки:
Из здесь, и по моему профилю вы можете найти более полезные ответы на FA. Кроме того, две хорошие ссылки на свойства обычного языка: one, второй