Мертвое состояние включено в минимизированный DFA или нет?

Question

Я искал в Google, и на многих страницах указано, что в свернутом DFA мертвое состояние или состояние ловушки удаляются. Мой вопрос заключается в том, как это все еще может быть DFA, если какой-то переход не определен. Так что вы говорите людям?

Answer 1

Даже минимальные DFA должны включать мертвые состояния; в противном случае они либо (а) не являются DFA, либо (б) не принимают тот же язык, что и их неминимальные аналоги. Например, минимальный DFA для языка {a} над алфавитом {a, b} должен иметь 3 состояния: начальное состояние, в котором вы можете увидеть a и принять; принимающее состояние, в котором вы отклоняете, если видите что-либо еще; и мертвое состояние, куда вы идете, если вы видите b или что-нибудь в состоянии принятия.

Никогда не слышал об исключении мертвых состояний из минимальных DFA. Богохульство!

Answer 2

@ PrashantBhardwaj: Я также думаю, что его (мертвое состояние и соответствующие мертвые ходы) следует включить, потому что включение его завершит DFA, т. Е. У нас не будет анонимных перемещений в конкретном состоянии в минимизированном DFA, учитывая его .

Тем не менее, вопрос остается без ответа? Наконец, мы должны включить это или нет? Может ли кто-нибудь это подтвердить?

Answer 3

Мертвые состояния не удаляются в «минимальных» версиях, но да, они теряются при «аннулировании» DFA (возможно, вы перепутали условия)