Установка алгоритма, который определяет, если l = l*, учитывая какой -либо обычный язык l

Question

Я изучаю алгоритмы членства и работаю над этой конкретной проблемой, которая говорит следующую:

Выставьте алгоритм, который, учитывая какой -либо обычный язык L, определяет, L = L*

Итак, моя первая мысль была, у нас есть L*, которая является звездой L -Kleen Семья обычных языков закрыта под звездным звеном. Поэтому L всегда будет равен L*?

Я чувствую, что это определенно намного больше, наверное, мне не хватает чего -то. Любая помощь будет оценена. Спасибо еще раз.

Answer 1

Поскольку L регулярно, мы знаем, что L* является по определению, в котором говорится, что семья обычных языков закрыта под звездами. Поэтому L всегда будет равен L*?

Нет. Regular(L) --> Regular(L*), но это не значит, что L == L*. Анкет То, что два языка оба регулярно не означают, что они такой же обычный язык. Например, a* и b* оба являются обычными языками, но это не делает их одинаковыми языками.

Пример L != L* был бы язык L = a*b*, и поэтому L* = (a*b*)*. Анкет Строка abab это часть L* но не часть L.

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

Answer 2

Смысл, который вы заявили, неверно. Закрытость под звездой Kleene означает только то, что L* снова регулярно, если L регулярно. Одна возможность проверить, должен ли L = L* для вычисления минимального автомата для обоих, а затем проверить на эквивалентность.