Строгое определение обычного языка из теоретической информатики может показаться абстрактным с небольшой практической пользой, но если вам когда-либо придется внедрять конечный автомат для распознавания определенных входных данных, вы можете сэкономить много бесполезных усилий. и прическа, если вы можете доказать, что это невозможно.
Неформальный способ выразить это - признание обычного языка не может требовать произвольного количества памяти. Лемма для регулярных языков полезна для доказательства того, что конкретный язык (, т. Е. , набор строк) не может быть распознан детерминированным конечным автоматом. * +1007 *
С Введение в формальные языки и автоматы от Питера Линца (стр. 115, 3-е изд.):
Теорема 4.8
Пусть L - бесконечный регулярный язык. Тогда существует некоторое положительное целое число m , такое что любое w ∈ L с | w | ≥ м можно разложить на
w = xyz ,
с
| ху | ≤ м ,
* * И тысяча сорок-девять
| у | ≥ 1,
такой, что
ш i = xy i z - уравнение (4,2)
также в L для всех i = 0, 1, 2,…
Чтобы распознать бесконечный язык, конечный автомат должен «прокачать» или повторить некоторую часть его состояний, и это функция y i (запись для некоторой строки у повторяется я раз).
Почти все доказательства, включающие лемму накачки, включают в себя доказательство от противного. На странице 117 автор доказывает, что язык L = { a n b n : n ≥ 0} - т.е. , строки вида aaa… bbb… , где подстроки all- a и all- b равны в длина - не является регулярной:
Предположим, что L регулярно, так что лемма прокачки должна выполняться. Мы не знаем значение m , но что бы это ни было, мы всегда можем выбрать n = m . Следовательно, подстрока y должна полностью состоять из a . Предположим, что | y | = k . Тогда строка, полученная с использованием i = 0 в уравнении (4.2), равна
ш 0 = а м-к б м
и явно не в L . Это противоречит лемме накачки и, следовательно, указывает на то, что предположение о регулярности L должно быть ложным.
Другие примеры языков, которые не являются регулярными:
- L = { ш. R : ш ∈ Σ *} - т.е. , палиндромы
- L = { ш ∈ Σ *: n a ( ш ) <<em> n b ( w )} - т.е. , число a s меньше, чем число б S
- L = { a n! : n ≥ 0}
- L = { a n b l : n ≠ l }
- L = { a n b l : n + l простое число}
Оказывается, что то, что мы обычно называем регулярными выражениями, значительно мощнее: сопоставление регулярных выражений с обратными ссылками NP-hard !