Условие бесконечности языка конечного автомата

9

Существует теорема, которая гласит:

Дан конечный автомат, имеющий n указывает, существует ли строка w длина которого удовлетворяет n≤|w|≤2n−1 тогда язык, принятый автоматом, бесконечен.

Я понимаю ограничение |w|≥n, но я не понимаю, почему ограничение |w|≤2n−1 есть.

automata finite-automata рахул шарма
источник

Ответы:

5

В худшем случае ваш NFA может выглядеть так:

Наименьший w для которого он гарантированно зацикливается (заставляя его принимать бесконечный язык) имеет размер 2n−1,

Андре Соуза Лемос
источник
Когда я начинаю с q0 и после этого, когда я возвращаюсь в q0, это означает, что в машине есть цикл. Разве этого недостаточно в худшем случае, почему мы снова возвращаемся к финальной стадии в этом случае? Насколько я понимаю из этого рисунка, мы прокачаем этот цикл один раз, а затем снова перейдем к финальной стадии, так что это означает как только мы войдем в финальную стадию, мы предполагаем, что это не моя строка, так как она вернулась в какое-то другое состояние, но как только она вернется к финальной стадии, мы уверены, что это наша строка, так как есть некоторый цикл, который имеет был накачан?
Рахул Шарма
Мы пытаемся доказать что-то об автомате, а именно, что он принимает бесконечный язык. В способе доказательства сформулирована строкаwпредположительно, размер которого предполагается в пределах определенного интервала. Очевидно, что если у автомата есть петля, то строкаwсуществует. Что происходит, есливесневозможно найти внутри этого интервала, тогда машина не может быть такой, как на картинке. Либо у него нет петель, либо нет конечных состояний.
Андре Соуза Лемос
Я понимаю вашу точку зрения. Я просто пытаюсь понять верхнюю границу интервала, почему он равен 2n-1 и почему нет 2n-x (x может быть чем угодно, кроме 1). На рисунке выше мы можем сказать, что цикл равен qo -q1 .... qn-q1 .... qn, верно (макс. цикл)? Но если я снова q0 (q0 ... aq, q0), разве это не означает, что есть цикл, поэтому максимум должен быть n, почему мы добавляем n-1 к n (или почему мы снова собираемся в конечное состояние). У меня возникают некоторые трудности с получением этого :(. Может ли max. loop быть q0., q1, q2 ..qn, qn-1, qn-1..q0, что-то в этом роде?
Рахул Шарма
Верхняя граница 2n−1 потому что это не становится хуже, чем это. 2n−x меньше чем 2n−1и я только что показал вам автомат, который нуждается 2n−1шаги. Нет такого, который нуждается в большем (и выполняет свою работу), но есть тот, которому нужно это количество.
Андре Соуза Лемос
Получил это сейчас. Просто одно небольшое сомнение. Предположим, у меня есть 4 состояния на моей машине. И я прочитал строку abc, и я достиг конечного состояния, а затем я прочитал d там и вернулся в исходное состояние, а затем снова перешел в конечное состояние, так что моя строка станет abcdabc. Как я могу разбить это на лемму накачки, и получить y ^ i, где i = 1, чтобы показать, что у был накачан один раз.?
Рахул Шарма
5

Дополнительное условие позволяет вам написать простой алгоритм - проверить все строки с длинами в этом интервале - для определения (не) конечности принятого языка. Таким образом, вы получаете доказательство того, что это свойство разрешимо (что не для большинства моделей автоматов со сверхрегулярной мощностью).

Рафаэль
источник
3

Полная теорема утверждает эквивалентность, а не следствие :

Язык, принятый nсостояние NFA бесконечно тогда и только тогда, когда оно содержит слово w чей размер удовлетворяет n≤|w|≤2n−1,

Дополнительное условие |w|≤2n−1тем самым усиливает теорему .

Юваль Фильмус
источник