Поиск дополнения DFA?

Мне предлагается показать диаграмму DFA и RegEx для дополнения RegEx (00 + 1)*. В предыдущей задаче я должен был доказать, что дополнение DFA закрыто и также является регулярным выражением, поэтому я знаю, что для преобразования DFA, M в дополнение, M`, мне просто нужно поменять начальные принимающие состояния и конечные принимающие состояния.

Однако, похоже, что начальные принимающие состояния для RegEx равны {00, 1, ^}, а конечные принимающие состояния - {00, 1, ^}. Таким образом, их замена приведет к тому же самому RegEx и DFA, которые кажутся противоречивыми.

Я делаю что-то неправильно или это RegEx, как предполагается, не имеет реального дополнения?

Спасибо

Ответ 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, второй

Ответ 2

Я не нашел времени, чтобы прочитать все ответы Гриджеша, но здесь простой способ получить DFA, принимающий дополнение к языку, учитывая, что DFA принимает язык: используйте тот же DFA, но меняете принимающие состояния на непринятия и наоборот.

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

Чтобы получить DFA для разворота, вы можете сначала построить NFA, добавив новое начальное состояние, которое не детерминируется для всех принимающих состояний исходного DFA. Переверните все переходы исходного DFA и сделайте единственным принимающим состоянием исходное состояние исходного DFA.