Как мне проверить, что DFA эквивалентен NFA?

10

Я учусь конвертировать NFA в DFA и хочу убедиться, что все делаю правильно. Очевидно, что возвращение в другом направлении - это не вещь. Кто-нибудь знает алгоритм проверки, что DFA эквивалентен NFA?

IAmOnStackExchange
источник
Одно из возможных объяснений: существует ли «проверка результатов» (в смысле Вассермана и Блума ) для проблемы преобразования NFA в DFA? Другими словами, существует ли алгоритм, который асимптотически быстрее, чем само преобразование, который, учитывая предполагаемую (входную, выходную) пару для алгоритма преобразования, проверяет, является ли вывод правильным?
DW

Ответы:

7

Это проблемный вопрос. Есть способ проверить эквивалентность автоматов, который я сейчас объясню, но, боюсь, это вам не поможет, как вы увидите в конце.

Напомним, что два множества и B равны тогда и только тогда, когда A B и B A (это определение равенства множеств). Таким образом, вам достаточно проверить, что L (AВAВВA и L ( N ) L ( D ) , где D и N являются ваш DFA и NFA, соответственно.L(D)L(N)L(N)L(D)DN

Но как вы проверяете содержание языков, вы можете спросить. Ну, теперь понаблюдайте тогда и только тогда, когда A ¯ B = (где ¯ B - дополнение к B ).AВAВ¯знак равноВ¯В

Давайте рассмотрим сначала проверку, является ли . Для этого вам нужно дополнить D (очень просто - поменять принимающие отклоняющие состояния), затем построить автомат пересечения (например, с конструкцией продукта) с помощью N и проверить на пустоту, найдя путь к принимающему состоянию.L(N)L(D)DN

Однако обратное направление покажет, почему это вам не поможет. Чтобы проверить, является ли , необходимо дополнить NL(D)L(N)N . Но чтобы дополнить NFA, сначала нужно преобразовать его в DFA, что делает бессмысленной саму идею.

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

Скажу так: следуя предложенным мною конструкциям, нетрудно сделать вывод, что если существует слово длины не более 2 2 n ( n - число состояний N ), которое принимается одним, а не другим. Таким образом, вы можете попробовать все слова до этой длины.L(D)L(N)22NNN

Shaull
источник
Спасибо за хорошо продуманный ответ. Я узнал что-то новое сегодня. Похоже, лучше всего сравнить мою работу с JFLAP.
IAmOnStackExchange
2
Если у вас большой NFA (например, с более чем 7-8 штатами), ваш лучший вариант - просто проверить себя внимательно. Как правило, после удаления недостижимых состояний вы получаете небольшой DFA, и проверка вручную не является слишком сложной.
Шал
1
Разве вы не можете определить и минимизировать обе машины и проверить, являются ли эти две машины изоморфными?
saadtaame
5

Один из способов - преобразовать NFA в DFA, а затем проверить эквивалентность двух DFA, для которых существует линейный алгоритм [1].

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

Филиппо Бончи, Дэмиен Поус, Проверка эквивалентности NFA с помощью бисимуляции до конгруэнтности принципам языков программирования (POPL), январь 2013 г., Рим, Италия. ACM, стр.457-468, 2013.

Аннотация . Мы вводим бисимуляцию с точностью до конгруэнции как метод доказательства языковой эквивалентности недетерминированных конечных автоматов. Используя эту технику, мы разработали оптимизацию классического алгоритма Хопкрофта и Карпа [1]. Мы сравниваем наш подход с недавно введенными антицепочечными алгоритмами, анализируя и связывая два основных метода коиндуктивного доказательства. Мы даем конкретные примеры, где мы экспоненциально улучшаем по сравнению с антицепями; кроме того, экспериментальные результаты показывают незначительные улучшения.

[1] Дж. Э. Хопкрофт и Р. М. Карп. Линейный алгоритм проверки эквивалентности конечных автоматов. TR 114, Cornell Univ., Декабрь 1971.

См. Также веб-приложение к этому документу , которое содержит сценарии Coq для проверки результатов, ссылку на реализацию и интерактивный апплет.

J.-E. Штырь
источник
Один из способов - преобразовать NFA в DFA , цель постера - проверить результат этого алгоритма. Применение дважды действительно один способ, но не застрахован от неправильного понимания алгоритма. Наверное, поэтому и был задан метод проверки.
AProgrammer
2
@aprogrammer Основная часть моего ответа - ссылка на алгоритм, для которого доступен сценарий доказательства Coq, который, безусловно, является самым безопасным методом проверки, который я могу придумать.
Ж.-Е.
1
Я не уверен, что кто-то неуверенный в своем понимании простого алгоритма, такого как NFA - DFA, который будет делать со скриптом Coq proof. Это похоже на использование алгебры для решения математической задачи третьего класса.
AProgrammer
0

Этот вопрос больше касается прикладного тестирования программного обеспечения и проверки правильности на практике, а не теоретического вопроса.

  • D1D2¯D2D1¯D¯

  • Вы можете положиться на ранее протестированное программное обеспечение, которое было проверено для подтверждения ваших результатов. например библиотека AT & T FSM

  • Другая идея: рандомизированное тестирование. выбрать случайные строки на вашем языке. определить, приняты или не приняты строки DFA / NFA. если два не равны, с большой вероятностью вы найдете строки, которые не соответствуют.

  • Еще одна идея: вы можете написать код для обхода всех ветвей DFA и NFA до определенной глубины и искать несоответствия. это эквивалентно перечислению всех потенциально принятых строк заданной длины.

ВЗН
источник