Как вы нормализуете конечный автомат? - PullRequest
Новая
       32

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

18 голосов
/ 09 июля 2009
  1. Как вы находите минимальный детерминированный FSM?
  2. Есть ли способ нормализации недетерминированных автоматов?
  3. Существует ли линейный алгоритм с временной привязкой для нахождения минимального FSM для данной машины?
  4. Есть ли способ узнать, эквивалентны ли два FSM?

Это не домашнее задание. Я смотрел эту серию лекций и мне стало любопытно.

Ответы [ 4 ]

8 голосов
/ 09 июля 2009

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

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

6 голосов
/ 10 декабря 2009

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

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

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

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

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

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

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

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

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

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

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

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

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

...