Можно ли удалить недостижимое состояние в этом свернутом DFA? - PullRequest
1 голос
/ 17 октября 2019

Так что это DFA в вопросе нужно свести к минимуму

So this is the DFA to be minimized

Ответ на этот вопрос таков и как вы можете видеть DFAсейчас свернут.

enter image description here

Мой вопрос : как вы можете видеть, свернутый DFA имеет состояние q7 , который недоступен из начального или начального состояния. Итак, почему они показывают состояние q7 в окончательном ответе, если нельзя удалить недоступное состояние, чтобы сделать этот dfa еще более минимизированным.

1 Ответ

0 голосов
/ 21 октября 2019

Давайте будем практичными на мгновение. Помимо определений и конструкций, минимальный DFA, соответствующий данному DFA, должен быть DFA, который принимает тот же язык и имеет как можно меньше состояний. Любое другое определение минимизации DFA не так полезно, как это. Учитывая это, ответ на ваши вопросы однозначно состоит в том, что q7 НЕ ДОЛЖЕН находиться в минимизированном DFA, поскольку DFA без q7 принимает тот же язык и имеет меньше состояний. Мы можем спорить о том, удалит ли конкретная процедура минимизации ее или что-то до бесконечности, но на самом деле это состояние должно исчезнуть. Другая причина, по которой это должно произойти, состоит в том, что теорема Майхилла-Нерода говорит нам, что минимальный DFA для этого языка должен иметь такое же количество состояний в минимальном DFA для этого языка, как и классы эквивалентности по отношению неразличимости. Поскольку ни одна строка не приводит к q7, для нее вообще нет класса эквивалентности, и, конечно, не может быть добавлен новый класс.

TL; DR - q7 не является состоянием в минимальном DFA, соответствующемк данному DFA. Делай из того, что хочешь.

...