Лемма о накачке

Лемма о накачке (pumping lemma) – это важный теоретический результат, позволяющий во многих случаях проверить, является ли язык автоматным. Поскольку все конечные языки являются автоматными, эту проверку имеет смысл делать только для бесконечных языков.

Теорема 4. (Лемма о накачке) Пусть L – автоматный язык. Тогда существует константа n (зависящая от L), для которой каждую цепочку w из языка L, удовлетворяющую неравенству |w|≥ n, можно разбить на три цепочки w=xyz так, что выполняются следующие условия:

1. y≠ ε.

2. |xy|≤ n.

3. Для любого k≥ 0 цепочка xykz также принадлежит L.

Это значит, что всегда можно найти такую цепочку y недалеко от начала цепочки w, которую можно «накачать». Таким образом, если цепочку y повторить любое число раз или удалить (при k=0), то результирующая цепочка всё равно будет принадлежать языку L.

Идея доказательства леммы о накачке аналогична рассуждениям, приведённым при доказательстве того, что язык L4={an bcn |n≥ 0} не является автоматным.

Используем лемму о накачке для доказательства неавтоматности некоторых языков.

1. V={0, 1}; Leq=α ∈ V* в α количества вхождений 0 и 1 равны}.

Предположим, что язык Leq автоматный. Согласно лемме о накачке существует некая константа n, при которой выполняются все условия леммы. Рассмотрим цепочку w=0n1n. Пусть w=xyz – разбиение цепочки w по условиям леммы. Так как |xy|≤ n, то xy состоит из одних нулей. Цепочка xz должна принадлежать Leq. Но в цепочке xz единиц больше, чем нулей. Получили противоречие. Следовательно, гипотеза об автоматности Leq ошибочна.

2. Докажем неавтоматность языка Lpr, образованного всеми цепочками из единиц, длины которых – простые числа. Предположим, что язык Lpr автоматный. Тогда должна существовать константа n, удовлетворяющая условиям леммы о накачке. Рассмотрим любое простое число p≥ (n+2). Пусть w=1p.

Согласно лемме о накачке можно разбить цепочку w=xyz так, что y≠ ε и |xy|≤ n. Пусть |y|=m. Тогда |xz|=p-m. Рассмотрим цепочку xyp-mz, которая по лемме о накачке должна принадлежать языку Lpr, если он действительно является автоматным. Однако

|xyp-mz|=|xz|+(p-m)|y|=p-m+(p-m)m=(m+1)(p-m).

Так как y≠ ε, то m+1> 1. Кроме того, m=|y|≤ |xy|≤ n, а p≥ n+2, поэтому p-m≥ 2. Значит число |xyp-mz| не простое, так как имеет два сомножителя, больших единицы.

Мы начали с предположения, что предлагаемый язык является автоматным, и пришли к противоречию, доказав, что существует некоторая цепочка, которая не принадлежит этому языку, тогда как по лемме о накачке она должна ему принадлежать. Таким образом, язык Lpr не является автоматным.

Вопросы и упражнения.

Докажите, что следующие языки не являются автоматными:

а) множество цепочек, состоящих из «сбалансированных» скобок «(«и «)», которые встречаются в правильно построенном арифметическом выражении;

б) {0n1m2n | n, m ≥ 0};

в) {0n1m | n≤ m};

г) {0n12n | n≥ 1}.