Как я могу найти закрытие D FA

Пытаюсь реализовать закрытие D FA. Я успешно реализовал Union, Compliment Intersection, Subtraction и Concatenate D FA без использования N FA. Наш учитель не рассказал нам алгоритм поиска замыкания. Я попытался сделать это, объединив DFA сам с собой, но совершенно очевидно, что это не сработало.

Мне просто нужны шаги, как я представляю DFA с помощью матрицы. Кроме того, не могли бы вы рассказать подробнее о закрытии Кляйна, но я уверен, что смогу это сделать, как только узнаю, как получить закрытие.


person Sayam Qazi    schedule 15.05.2016    source источник


Ответы (1)


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

Конечно, получившийся автомат уже не является детерминированным. Но есть стандартные процедуры для его определения снова.

Для прямого построения: посмотрите на все переходы, которые входят в конечное состояние, например (q,a) -> f. Из исходящего состояния добавляем еще один переход, читающий тот же символ и идущий в начальное состояние: (q,a) -> s. Так что у автомата есть возможность дочитать слово и сразу после этого начать заново.

person Peter Leupold    schedule 18.05.2016
comment
Для второго варианта: новый переход тоже сделает автомат недетерминированным: два перехода на одну и ту же букву. Так что и здесь вам нужна детерминация. Я проглядел это. - person Peter Leupold; 19.05.2016