Пусть L обычный язык. Тогда существует постоянная ‘c’ такая, что для каждой строки w в L —
| ш | ≥ c
Мы можем разбить w на три строки, w = xyz , так что —
- | У | > 0
- | Х | ≤ c
- Для всех k ≥ 0 строка xy k z также находится в L.
Применение насосной леммы
Лемма накачки должна применяться, чтобы показать, что некоторые языки не являются регулярными. Это никогда не должно использоваться, чтобы показать, что язык является регулярным.
-
Если L регулярно, то оно удовлетворяет лемме о накачке.
-
Если L не удовлетворяет лемме накачки, она нерегулярна.
Если L регулярно, то оно удовлетворяет лемме о накачке.
Если L не удовлетворяет лемме накачки, она нерегулярна.
Способ доказать, что язык L не является регулярным
-
Сначала мы должны предположить, что L регулярно.
-
Таким образом, лемма прокачки должна выполняться для L.
-
Используйте лемму прокачки, чтобы получить противоречие —
-
Выберите w так , чтобы | w | ≥ c
-
Выберите y так , чтобы | y | ≥ 1
-
Выберите x так , чтобы | xy | ≤ c
-
Назначьте оставшуюся строку z.
-
Выберите k так, чтобы полученная строка не была в L.
-
Сначала мы должны предположить, что L регулярно.
Таким образом, лемма прокачки должна выполняться для L.
Используйте лемму прокачки, чтобы получить противоречие —
Выберите w так , чтобы | w | ≥ c
Выберите y так , чтобы | y | ≥ 1
Выберите x так , чтобы | xy | ≤ c
Назначьте оставшуюся строку z.
Выберите k так, чтобы полученная строка не была в L.
Следовательно, L не является регулярным.
проблема
Докажите, что L = {a i b i | i ≥ 0} не является регулярным.
Решение —
Сначала предположим, что L регулярно, а n — число состояний.
Пусть w = a n b n . Таким образом | w | = 2n ≥ n.
Прокачивая лемму, пусть w = xyz, где | xy | ≤ н.
Пусть x = a p , y = a q и z = a r b n , где p + q + r = n, p ≠ 0, q ≠ 0, r ≠ 0. Таким образом, | y | ≠ 0.
Пусть k = 2. Тогда xy 2 z = a p a 2q a r b n .
Номер as = (p + 2q + r) = (p + q + r) + q = n + q
Следовательно, xy 2 z = a n + q b n . Поскольку q ≠ 0, xy 2 z не имеет формы a n b n .
Таким образом, xy 2 z не входит в L. Следовательно, L не является регулярным.