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