Лемма о расширении регулярных языков

следующий результат, известный как Лемма о расширении регулярных языков (Pumping Lemma) основан на том простом замечании, что в диаграмме переходов с n вершинами любой путь длины, большей или равной n, должен содержать цикл, т.е. повторяющуюся вершину.

Теорема 7.10.

Пусть L – бесконечный регулярный язык. Тогда существует целое число m > 0 такое, что для любой строки   L, длина которой   m, возможно представление

 = ,

где   0 и   m, такое, что для любого i = 0, 1, 2, ... строка

_i = ⁱ

также принадлежит L.

Доказательство.

Если язык L регулярный, тогда существует ДКА M, который распознает его. Пусть

q₀, q₁, ..., q_n

– множество всех состояний автомата M. Возьмем любую строку   L такую, что

 = k  m = n+1.

Так как по предположению L бесконечен, то такая достаточно длинная строка всегда найдется. Рассмотрим все те состояния автомата M, через которые он проходит, когда прочитывает строку ; пусть это будут состояния

q₀, q_i, q_j, ..., q_f.

Так как эта последовательность имеет k + 1 вершину и

k + 1 > n + 1,

то, как минимум, одна вершина должна повториться, по крайней мере, на n-м шаге. Таким образом, последовательность должна иметь следующий вид:

q₀, q_i, q_j, ..., q_r, ..., q_r, ..., q_f .

причем, очевидно, можно считать, что последовательность q₀, q_i, q_j, ..., q_r ,…, q_r уже не содержит других повторяющихся элементов, кроме последнего q_r .

Но тогда должны существовать подстроки , ,  строки  такие, что

*(q₀, ) = q_r,

*(q_r, ) = q_r,

*(q_r, ) = q_f,

причем   n+1 = m и   1. Отсюда непосредственно получаем, что

*(q₀, ) = q_f,

а также

*(q₀, ²) = q_f,

*(q₀, ³) = q_f,

и так далее, что и завершает доказательство.

Заметим, что Лемма о расширении применима только к бесконечным языкам, так как любая достаточно длинная строка языка сразу порождает бесконечное множество строк этого же языка.

Впрочем, это не является недостатком, так как все конечные языки заведомо регулярны, а Лемма о расширении главным образом применяется для доказательства того, что какой-то данный язык не является регулярным. Это доказательство всегда проводится по принципу "от противного", чтобы затем получить противоречие. Но, как и любое другое необходимое условие, Лемма о расширении не может использоваться для доказательства регулярности какого-то языка.

Пример 7.11.

Показать, используя Лемму о расширении, что язык

L = {aⁿ bⁿ  n  0}

не является регулярным.

Допустим противное, т.е. что язык L – регулярный. Тогда для L справедлива Лемма о расширении, а значит, и должно существовать такое m, что если  = n > m, где   L, то  можно представить в виде   .

Для строки  возможны три случая:

1)  = а^k,

2)  = b^t

3)  = a^kb^t.

В каждом из этих случаев мы получаем:

1) _i = a^{n - k} (a^k)ⁱ bⁿ,

2) _i = aⁿ (b^t)ⁱ b^{n - t},

3) _i = a^{n - k} (a^kb^t)ⁱ b^{n - t}.

Полагая i = 2, убеждаемся, что ни в одном из случаев ₂ не принадлежит L, что противоречит утверждению Леммы о расширении. Следовательно, наше первоначальное предположение о регулярности языка L неверно, т.е. язык {aⁿbⁿ  n  0} не является регулярным.

Пример 7.12.

Показать, что язык

L = {aⁿb^m  n  m, n  0, m  0}

не является регулярным.

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

L₁ =  L(a* b*).

Но L₁ = {aⁿ bⁿ  n  0} и, как уже было показано, не является регулярным. Следовательно, и L не может быть регулярным.