Я чувствую, что придурок публикует здесь такие простые вопросы, но база знаний этого сайта просто потрясающая.Спасибо за ваше понимание.
По вопросу о нахождении минимальной длины накачки (относительно леммы накачки для регулярных языков) регулярного выражения:
Регулярное выражение R = 1011 (по алфавиту {0,1})
Это не единственные совпадения с этой строкой ε (пустая строка) и 1011?
РЕДАКТИРОВАТЬ - я смотрел на слишком много звезд Клини.Пустая строка ε отсутствует в этом языке.
Свойства регулярных языков указывают, что если язык может быть представлен конечным автоматом (или регулярным выражением), то он является регулярным, и, конечно, этот можно представитьобоими.(И этот вопрос, очевидно, приводит меня к мысли, что язык регулярный)
Но с другой стороны, лемма прокачки (неофициально) гласит, что все регулярные языки имеют длину прокачки, благодаря чему все строки по крайней мере этой длины могутразделить на xyz, где y можно повторять, не влияя на результат.ε не может быть перекачено по определению, и 1011 не может быть перекачено (я не думаю, что это вопрос), потому что никакая другая строка не соответствует ему, поэтому удаление или добавление экземпляров y приведет к строке, которая не принимается /
Где ошибка в моей логике?
2-е РЕДАКТИРОВАНИЕ - Ответ для любого p> 4, язык можно прокачать, установив x или y или z равным ϕ (нулевой набор), который при объединении с чем-либо приводит к нулевому набору?