У меня есть один небольшой вопрос по поводу леммы о накачке для обычных языков - достаточно ли она хороша, чтобы показать, что если конкретная строка, принадлежащая языку L, не может быть прокачана, то язык является неправильным? Например, если я выберу язык L1, имеющий форму a ^ nb ^ n (ab, aabb, aaabbb ...), и я покажу, что строка aabb не может быть перекачана и по-прежнему является частью L1, тогда это Можно ли сразу сделать вывод, что L1 нерегулярен?
Ваше здоровье.
Недостаточно продемонстрировать, что одиночная колонна конечной длины не качает. В качестве строгого аргумента вам также нужно будет доказать, что длина вашей примерной строки больше, чем длина перекачки языка. Обычно вы предполагаете, что существует некоторая длина откачки p, а затем строите колонну длиной больше p, которую невозможно перекачивать.
Да, именно так работает лемма о накачке. Это полезно только для доказательства того, что языки не являются обычными. Удовлетворение леммы о накачке - это только необходимое, но не достаточное условие для того, чтобы язык был регулярным.
(Nota bene: аналогично для контекстно-свободных языков и соответствующей леммы о перекачке)
Да, вот как это работает, но будьте осторожны, показывая, как струна «не накачивается».
Для этого вам нужно разбить строку w в L на подстроки xyz и показать, что некоторые версии xy ^ 1z для int ii> = 0 приводят к строкам не в L, но по-прежнему принимаются DFA M (для M, построенного принять L), придя к противоречию.
Обратите внимание, что вы не можете выбрать местоположение y и поэтому должны учитывать 3 возможных его положения. На мой взгляд, это ключ.
