Преобразование NFA в DFA
Когда мы конвертируем из nfa в dfa, может быть результат, подобный изображенному ниже... Мой вопрос: нужно ли писать, что из состояния {4} он переходит в нулевое состояние? Я имею в виду, что без отображения входной символ 1 из {4} совпадает с изображением ниже, верно? или нет?
3 ответа
Это вопрос соглашения. Лично я предпочитаю не загромождать свой DFA ненужными состояниями, тем более что DFA, полученные с помощью преобразования из NFA, в любом случае имеют тенденцию становиться достаточно сложными, и, поскольку они детерминированы, мы знаем, что любой не отображаемый переход должен быть недействительным.
Тем не менее, я видел, что многие люди в академических кругах преподают / используют другое соглашение и требуют, чтобы все переходы были явно показаны. Когда я работал в качестве ТА (тьютора), у меня фактически была дискуссия с профессором по этому поводу - он хотел, чтобы мы, репетиторы, вычитали баллы на итоговых тестах для пропущенных переходов в DFA, но я убедил его, что вычитать баллы за это несправедливо.
Нет необходимости записывать переход {4}-> 0, потому что автомат уже принимает слово. этот переход означает только то, что это "ничего" не имеет значения для нашего решения. но для подробностей полезно дать его, показать весь автомат.
Это имеет значение, только если вы пытаетесь нарисовать MinimalFA (MFA).
На самом деле вы можете генерировать бесконечное количество DFA из одного NFA, каждый из которых отличается по количеству состояний.
Если вы удалите "Мертвые состояния" на рисунке, вы получите MFA. С цифрой все в порядке, если вы просто хотите DFA