Эквивалентность между двумя автоматами - PullRequest
Новая
       30

Эквивалентность между двумя автоматами

7 голосов
/ 02 августа 2011

Какой самый лучший или самый простой метод определения эквивалентности между двумя автоматами?

Т.е., если заданы два конечных автомата A и B, как я могу определить, распознают ли оба языка один и тот же язык?

Они оба детерминированные или оба недетерминированные.

Ответы [ 3 ]

13 голосов
/ 27 сентября 2012

Другой, более простой подход состоит в том, чтобы дополнять и пересекать автоматы.Автомат A эквивалентен B, если * L(A) содержится в L(B), и наоборот, если пересечение между дополнением L(B) и L(A) пусто и наоборот.

Вот алгоритм проверки, содержится ли L(A) в L(B):

  1. Дополнение: Сначала определите B с использованием конструкции подмножества.Затем сделайте каждое принимающее состояние отклоняющим и каждое отклоняющее состояние принимающим.Вы получаете автомат, который распознает дополнение L(B).
  2. Пересечение: Создайте автомат, который распознает язык, который является пересечением дополнения L(B) и L(A).Т.е. построить автомат для пересечения автомата из шага 1 и A.Чтобы пересечь два автомата U и V, вы строите автомат с состояниями U x V.Автомат переходит из состояния (u,v) в (u',v') с буквой a, если есть переходы u --a--> u' в U и v --a--> v' в V.Принимающими состояниями являются состояния (u,v), где u принимает в U, а v принимает в V.
  3. После построения автомата на шаге 2 все, что нужно, это проверитьпустота.Т.е. есть ли слово, которое принимает автомат?Это самая простая часть - найти путь в автомате из исходного состояния в принимающее состояние с помощью алгоритма BFS.

Если L(A) содержится в L(B), нам нужно запустить то же самоеалгоритм проверки, если L(B) содержится в L(A).

10 голосов
/ 02 августа 2011

Два недетерминированных конечных автомата (NFA) эквивалентны, если они принимают один и тот же язык.

Чтобы определить, принимают ли они один и тот же язык, мы смотрим на тот факт, что каждый NFA имеет минимальный DFA, где нет двухсостояния идентичны.Минимальный DFA также уникален.Таким образом, с учетом двух NFA, если вы обнаружите, что их соответствующие минимальные DFA эквивалентны, то два NFA также должны быть эквивалентными.

Для углубленного изучения этой темы я настоятельно рекомендую вам прочитать Введение в формальный язык и автоматы .

0 голосов
/ 11 февраля 2017

Я просто перефразирую ответ: @Guy.

Чтобы сравнить языки, принятые обоими, мы должны выяснить, L(A) is equal to L(B) или нет.

Таким образом,Вы должны узнать, является ли L(A)-L(B) and L(B)-L(A) нулевым или нет.(Причина 1)

Часть 1:

Чтобы выяснить это, мы строим NFA X из NFA A и NFA B, .

ЕслиX - пустое множество, тогда L(A) = L(B) иначе L(A) != L(B).(Причина 2)

Часть 2:

Теперь нам нужно найти эффективный способ доказательства или опровержения X is empty set.Когда X будет пустым как DFA или NFA?Ответ: X будет пустым, если нет пути, ведущего от начального состояния к какому-либо из конечных состояний X. Для этого мы можем использовать BFS или DFS.

Причина 1: если оба значения равны нулю, тоL(A) = L(B).

Причина 2: Мы можем доказать, что множество регулярных языков замкнуто на пересечении и объединении.Таким образом, мы сможем эффективно создавать NFA X.

и для наборов:

...