Почему число строк должно быть больше или равно числу состояний в лемме прокачки?
Если L регулярный язык, то существует постоянная n (который зависит от L) такой, что для каждой строки w на языке Lтакой, что длина w Больше или равно nмы можем разделить w на три строки, w = xyz,
w = length of string. n = Number of States.
Почему мы должны выбрать w больше или равно n? а что такое длина прокачки?
2 ответа
Если вы посмотрите на полное утверждение леммы ( http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages), вы увидите, что на самом деле говорится, что каждая строка образована префиксом xчасть, которая может повторяться любое количество раз y и суффикс z, Теперь очевидно, что в самом коротком случае (когда повторяющаяся часть берется только один раз) длина w равно количеству состояний, необходимых для языка. Это изображение из Википедии очень полезно:
Вы, кажется, неправильно понимаете лемму (которую вы также не сформулировали полностью) и смешиваете аспекты доказательства с тем, что вы указали. Лемма говорит, что для каждого обычного языка L есть константа p так, что каждая строка по крайней мере p символы, которые принадлежат L имеет непустую подстроку длиной не более p которые могут быть "накачаны", всегда давая другой элемент L, Постоянная p является (а) "длина накачки".
Это можно доказать, наблюдая, что если язык регулярен, то существует конечный автомат, который принимает его, и принимая p быть числом состояний в этом автомате (детали опущены).
Однако это не означает, что число состояний в наименьшем FSA, распознающем данный регулярный язык, является наименьшей возможной длиной прокачки для этого языка. Например, рассмотрим язык, состоящий из объединения { an } а также { bn } для всех n, Вам нужен FSA из четырех штатов для распознавания этого языка, но его минимальная длина прокачки равна 1.