Я учусь конвертировать NFA в DFA и хочу убедиться, что все делаю правильно. Очевидно, что возвращение в другом направлении - это не вещь. Кто-нибудь знает алгоритм проверки, что DFA эквивалентен NFA?
automata
finite-automata
proof-techniques
nondeterminism
IAmOnStackExchange
источник
источник
Ответы:
Это проблемный вопрос. Есть способ проверить эквивалентность автоматов, который я сейчас объясню, но, боюсь, это вам не поможет, как вы увидите в конце.
Напомним, что два множества и B равны тогда и только тогда, когда A ⊆ B и B ⊆ A (это определение равенства множеств). Таким образом, вам достаточно проверить, что L (A В A ⊆ B B ⊆ A и L ( N ) ⊆ L ( D ) , где D и N являются ваш DFA и NFA, соответственно.L ( D ) ⊆ L ( N) L ( N) ⊆ L ( D ) D N
Но как вы проверяете содержание языков, вы можете спросить. Ну, теперь понаблюдайте тогда и только тогда, когда A ∩ ¯ B = ∅ (где ¯ B - дополнение к B ).A ⊆ B A ∩ B¯¯¯¯= ∅ В¯¯¯¯ В
Давайте рассмотрим сначала проверку, является ли . Для этого вам нужно дополнить D (очень просто - поменять принимающие отклоняющие состояния), затем построить автомат пересечения (например, с конструкцией продукта) с помощью N и проверить на пустоту, найдя путь к принимающему состоянию.L ( N) ⊆ L ( D ) D N
Однако обратное направление покажет, почему это вам не поможет. Чтобы проверить, является ли , необходимо дополнить NL ( D ) ⊆ L ( N) N . Но чтобы дополнить NFA, сначала нужно преобразовать его в DFA, что делает бессмысленной саму идею.
По сути, проблема с вашим вопросом гораздо глубже: вы хотите убедиться, что вы (неопределенная вычислительная модель) правильно выполнили четко определенный алгоритм. Так что это не проблема компьютерной науки.
Скажу так: следуя предложенным мною конструкциям, нетрудно сделать вывод, что если существует слово длины не более 2 2 n ( n - число состояний N ), которое принимается одним, а не другим. Таким образом, вы можете попробовать все слова до этой длины.L ( D ) ≠ L ( N) 22 н N N
источник
Один из способов - преобразовать NFA в DFA, а затем проверить эквивалентность двух DFA, для которых существует линейный алгоритм [1].
Следующая статья рассматривает более общий случай эквивалентности двух NFA (который, конечно, также относится к вашему случаю).
Филиппо Бончи, Дэмиен Поус, Проверка эквивалентности NFA с помощью бисимуляции до конгруэнтности принципам языков программирования (POPL), январь 2013 г., Рим, Италия. ACM, стр.457-468, 2013.
Аннотация . Мы вводим бисимуляцию с точностью до конгруэнции как метод доказательства языковой эквивалентности недетерминированных конечных автоматов. Используя эту технику, мы разработали оптимизацию классического алгоритма Хопкрофта и Карпа [1]. Мы сравниваем наш подход с недавно введенными антицепочечными алгоритмами, анализируя и связывая два основных метода коиндуктивного доказательства. Мы даем конкретные примеры, где мы экспоненциально улучшаем по сравнению с антицепями; кроме того, экспериментальные результаты показывают незначительные улучшения.
[1] Дж. Э. Хопкрофт и Р. М. Карп. Линейный алгоритм проверки эквивалентности конечных автоматов. TR 114, Cornell Univ., Декабрь 1971.
См. Также веб-приложение к этому документу , которое содержит сценарии Coq для проверки результатов, ссылку на реализацию и интерактивный апплет.
источник
Этот вопрос больше касается прикладного тестирования программного обеспечения и проверки правильности на практике, а не теоретического вопроса.
Вы можете положиться на ранее протестированное программное обеспечение, которое было проверено для подтверждения ваших результатов. например библиотека AT & T FSM
Другая идея: рандомизированное тестирование. выбрать случайные строки на вашем языке. определить, приняты или не приняты строки DFA / NFA. если два не равны, с большой вероятностью вы найдете строки, которые не соответствуют.
Еще одна идея: вы можете написать код для обхода всех ветвей DFA и NFA до определенной глубины и искать несоответствия. это эквивалентно перечислению всех потенциально принятых строк заданной длины.
источник