При преобразовании NFA в DFA иногда необходимо объединить состояния. Как в приведенном выше сценарии.
Но что на самом деле означает «объединение состояний в одно» в реальном сценарии?
И какова будет природа сочетания двух вышеуказанных состояний?
Значение комбинированных состояний в DFA
Ответы (1)
Фраза объединение состояний в одно означает, что вы
- Создайте новое состояние, которое помечено всеми метками из исходных состояний.
- Новое состояние получает все выходные данные и все конфликтующие (неоднозначные) входные переходы из исходных состояний.
- Каждая комбинация исходных меток может встречаться только в одном новом состоянии.
Примечание. Создание нового состояния с одной меткой в DFA можно рассматривать как частный случай вышеописанного.
Именование нового состояния с метками исходных состояний имеет смысл, что вы можете однозначно ссылаться на это новое состояние в последующем процессе генерации.
person
clemens
schedule
08.11.2017
