Как вы нормализуете конечный автомат?

Ответ 1

Некоторые неофициальные ответы, чтобы дать вам идеи, для подробных доказательств прочитайте хорошую книгу об Automata, например этот или те, которые упомянуты в другие ответы. И я уверен, что есть онлайн-материалы, на которые вы можете найти ответы на все ваши вопросы.

• Как вы находите минимальный детерминированный FSM?

Процедура заключается в устранении дублированных состояний (или для объединения эквивалентных состояний). Вы знаете, что состояние и переходы - это ключи для генерации строк. В принципе, дублированные состояния не вносят вклада в создание большего количества языков или меньше. Алгоритм начинается с конечных состояний, которые всегда обладают способностью генерировать lamda (пустая строка) и рекурсивно обновляют таблицу, которая указывает на генерирующую способность состояния, и, наконец, объединяют эти состояния, не делая различий.

• Есть ли способ нормализовать недетерминированные FSM?

Нормализованный DFA для NFA использует различные коллекции состояний NFA как состояния DFA, например {state0} - (1) → {state1, state2}, чтобы удалить недетерминированную часть, нет чтобы избежать государственного взрыва, поскольку DFA должен сделать это, чтобы представить язык.

• Существует ли линейный алгоритм с временным ограничением для поиска минимального FSM для данной машины?

Я помню, что лучший из них - O (NLogN), делая некоторые трюки для повторного использования информации в какой-то статье профессором Университета Западного Онтарио и сомневаюсь, что существуют лучшие. Я считаю, что классический - это O (N ^ 2).

• Есть ли способ увидеть, эквивалентны ли два FSM?

Да. Получите минимальный код, закодируйте состояние по своей строке доступа (строка, которая может достигать состояния из состояния начала, это в значительной степени настоящее "имя" состояния там) и проверьте карту перехода. Однако могут быть и более эффективные пути, но большая разница не будет.

Ответ 2

Поскольку все недетерминированные FSM имеют соответствующий детерминированный FSM, ответ на 1 и 2 должен быть одинаков.

Если вы хотите узнать больше, получите книгу "Введение в теорию вычислений" Майкла Сипсера, которая действительно отличная книга, чтобы узнать эти вещи. Sipser знает, о чем он говорит, и о том, как его очень хорошо сообщать.

Ответ 3

• Если вам задан некоторый детерминированный FSM, вы можете найти эквивалентный минимальный, используя довольно простой алгоритм в O (n ²); Алгоритм Хопкрофта делает это в O (n log n). Здесь вы найдете описание обоих. Вы можете проверить, эквивалентны ли A и B, минимизируя их и проверяя, совпадают ли они.
• Если вам дается некоторый недетерминированный FSM, то поиск эквивалентного минимального - PSPACE-complete. Другими словами, никакой хороший алгоритм не известен, и предполагается, что его не существует. Проверка эквивалентности двух недетерминированных автоматов также PSPACE-полна. Итак, если не будет очень невероятного прорыва, вы должны преобразовать автомат в детерминированный (это занимает много времени), а затем выполнить проверки.
• Вы можете преобразовать недетерминированный FSM в детерминированный с экспоненциальным числом состояний. Это неизбежно. Упражнение (не сложно!): Язык, состоящий из слов, в которых n-я буква с конца "a", может быть распознана с использованием недетерминированного FSM с n состояниями и не может быть распознана с использованием детерминированного FSM с менее чем 2 ⁿ. Экспоненциальная граница не может быть нарушена в общем случае.

Ответ 4

Отметьте "Основы проектирования компилятора", начиная с раздела 2.5. Доступно бесплатно онлайн. http://www.diku.dk/hjemmesider/ansatte/torbenm/Basics/basics_lulu.pdf

Он охватывает преобразование NFA в DFA и минимизацию DFA. NFA могут экспоненциально расширяться при преобразовании в DFA.

"... любой регулярный язык (язык который может быть выражен регулярным выражением, NFA или DFA) имеет уникальный минимальный DFA. Следовательно, мы можем решить эквивалентность регулярных выражений (или NFA или DFA) путем преобразования обоих в минимальные DFA и сравнения результатов.