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

Question

Я пытаюсь реализовать закрытие D FA. Я успешно реализовал союз, пересечение комплиментов, вычитание и объединение ДФ без использования N FA. Наш учитель не сказал нам, что алгоритм найдет закрытие. Я попытался сделать это, объединив D FA для себя, но совершенно очевидно, что это не сработало.

Мне просто нужны шаги, кстати, я представляю D FA, используя матрицу. Наряду с этим вы можете подробно рассказать о закрытии Klein, но я уверен, что смогу это сделать, как только я узнаю, как получить закрытие.

Answer 1

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

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

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