Рубрики

Насосная лемма в теории вычислений

Есть две насосные леммы, которые определены для
1. Обычные языки и
2. Контекст — бесплатные языки

Насосная лемма для регулярных языков
Для любого регулярного языка L существует целое число n, такое что для всех x ∈ L с | x | ≥ n, существует u, v, w ∈ Σ ∗, такое что x = uvw, и
(1) | Уф | ≤ n
(2) | v | ≥ 1
(3) для всех i ≥ 0: uv i w ∈ L

Проще говоря, это означает, что если строка v «прокачана», т. Е. Если v вставлено любое количество раз, результирующая строка все еще остается в L.

Насосная лемма используется как доказательство неправильности языка. Таким образом, если язык регулярен, он всегда удовлетворяет лемме прокачки. Если существует хотя бы одна цепочка, созданная из закачки, которой нет в L, то L, безусловно, не является регулярной.
Противоположность этому не всегда может быть правдой. То есть, если лемма прокачки справедлива, это не значит, что язык регулярен.

Например, докажем, что L 01 = {0 n 1 n | n ≥ 0} нерегулярно.
Предположим, что L регулярно, тогда по лемме накачки приведенные выше правила следуют.
Теперь пусть x ∈ L и | x | ≥ п. Итак, по лемме накачки существует такое u, v, w, что выполняется (1) — (3).

Покажем, что для всех u, v, w (1) — (3) не выполняется.
Если (1) и (2) выполнены, то x = 0 n 1 n = uvw с | uv | ≤ n и | v | ≥ 1.
Итак, u = 0 a , v = 0 b , w = 0 c 1 n, где: a + b ≤ n, b ≥ 1, c ≥ 0, a + b + c = n
Но тогда (3) не выполняется при i = 0
uv 0 w = uw = 0 a 0 c 1 n = 0 a + c 1 n ∉ L, поскольку a + c ≠ n.

Насосная лемма для контекстно-свободных языков (КЛЛ)
Лемма прокачки для CFL гласит, что для любого языка без контекста L можно найти две подстроки, которые можно «перекачивать» любое количество раз и при этом использовать один и тот же язык. Для любого языка L мы разбиваем его строки на пять частей и перекачиваем вторую и четвертую подстроку.
Лемма прокачки здесь также используется в качестве инструмента для доказательства того, что язык не является КЛЛ. Потому что, если какая-либо одна строка не удовлетворяет ее условиям, то язык не является CFL.
Таким образом, если L — КЛЛ, существует целое число n, такое что для всех x ∈ L с | x | ≥ n, существует u, v, w, x, y ∈ Σ ∗, такое что x = uvwxy, и
(1) | vwx | ≤ n
(2) | vx | ≥ 1
(3) для всех i ≥ 0: uv i wx i y ∈ L

Для приведенного выше примера 0 n 1 n — это CFL, поскольку любая строка может быть результатом перекачки в двух местах: одно для 0 и другое для 1.
Докажем, что L 012 = {0 n 1 n 2 n | n ≥ 0} не является контекстно-свободным.
Предположим, что L не зависит от контекста. Тогда по лемме накачки будут следовать приведенные выше правила.
Теперь пусть x ∈ L и | x | ≥ п. Таким образом, по лемме накачки существуют такие u, v, w, x, y, что (1) — (3) выполнено.
Покажем, что для всех u, v, w, x, y (1) — (3) не выполнено.

Если (1) и (2) выполнены, то x = 0 n 1 n 2 n = uvwxy с | vwx | ≤ n и | vx | ≥ 1.
(1) говорит нам, что vwx не содержит ни 0, ни 2. Таким образом, либо vwx не имеет 0, либо vwx не имеет 2. Таким образом, у нас есть два случая для рассмотрения.
Предположим, у vwx нет нулей. Согласно (2), vx содержит 1 или 2. Таким образом, у uwy есть «n» 0, и у uwy либо меньше, чем «n» 1, либо меньше, чем «n» 2.
Но (3) говорит нам, что uwy = uv 0 wx 0 y ∈ L.
Таким образом, uwy имеет равное число 0, 1 и 2, что дает нам противоречие. Случай, когда vwx не имеет 2, аналогичен и также дает нам противоречие. Таким образом, L не является контекстно-свободным.

Источник: Джон Э. Хопкрофт, Раджив Мотвани, Джеффри Д. Уллман (2003). Введение в теорию автоматов, языков и вычислений.

Эта статья предоставлена Нирупамом Сингхом .

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Насосная лемма в теории вычислений

0.00 (0%) 0 votes