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

Question

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

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

.

Итак, моя первая мысль состояла в том, что у нас есть L *, которая является звездой Клини из L, и чтобы определить, является ли L = L *, мы не могли бы просто сказать, что, поскольку L регулярна, мы знаем, что L * по определению утверждает, что семейство регулярных языков закрыто при закрытии по звездам. Следовательно, 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

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