Є дві леми прокачування, які визначені для 1. Звичайних мов і 2. Контексту – вільних мов Лема прокачування для звичайних мов Для будь-якої звичайної мови L існує таке ціле число n, що для всіх x ? L з |x| ? n, існує u, v, w ? ?^*, такий, що x = uvw, і (1) |uv| ? n (2) |v| ? 1 (3) для всіх i ? 0: увⁱw ? L Простими словами, це означає, що якщо рядок v «викачується», тобто якщо v вставляється будь-яку кількість разів, результуючий рядок все ще залишається в L. Лема про викачування використовується як доказ нерегулярності мови. Таким чином, якщо мова регулярна, вона завжди задовольняє лему прокачування. Якщо існує принаймні один рядок, створений за допомогою накачування, який не входить до L, то L, безумовно, не є регулярним. Протилежне цьому не завжди може бути вірним. Тобто, якщо лема прокачування справедлива, це не означає, що мова регулярна.

прокручування мишею не працює

Наприклад, доведемо Л₀₁= n ? 0 є неправильним. Припустимо, що L є регулярним, тоді згідно з лемою про накачування слідують наведені вище правила. Тепер нехай x ? L і |x| ? п. Отже, згідно з лемою про накачування, існують такі u, v, w, що виконуються (1) – (3). Покажемо, що для всіх u, v, w (1) – (3) не виконується. Якщо виконуються (1) і (2), то x = 0^п1^п= uvw з |uv| ? n і |v| ? 1. Отже, u = 0^a, v = 0^b, w = 0^в1^пде : a + b ? n, b ? 1, c ? 0, a + b + c = n Але тоді (3) не виконується для i = 0 uv⁰w = uw = 0^a0^в1^п= 0^{a + c}1^п? L, оскільки a + c ? п.

Лема про накачування для контекстно-вільних мов (CFL) Лема про закачування для CFL стверджує, що для будь-якої вільної від контексту мови L можна знайти два підрядки, які можна «закачувати» будь-яку кількість разів і залишатися на тій самій мові. Для будь-якої мови L ми розбиваємо її рядки на п’ять частин і закачуємо другий і четвертий підрядки. Pumping Lemma тут також використовується як інструмент, щоб довести, що мова не є CFL. Тому що, якщо будь-який рядок не задовольняє його умови, то мова не є CFL. Таким чином, якщо L є CFL, існує таке ціле число n, що для всіх x ? L з |x| ? n, існує u, v, w, x, y ? ?^*, так що x = uvwxy, і (1) |vwx| ? n (2) |vx| ? 1 (3) для всіх i ? 0: увⁱwxⁱі ? л

немає вхідного сигналу

Для прикладу вище, 0^п1^пє CFL, оскільки будь-який рядок може бути результатом накачування в двох місцях, одне для 0, а інше для 1. Доведемо, L₀₁₂= n ? 0 не є контекстно-вільним. Припустимо, що L є безконтекстним, тоді згідно з лемою про накачування слідують наведені вище правила. Тепер нехай x ? L і |x| ? п. Отже, згідно з лемою про накачування, існують такі u, v, w, x, y, що виконуються (1) – (3). Покажемо, що для всіх u, v, w, x, y (1) – (3) не виконуються. Якщо виконуються (1) і (2), то x = 0^п1^п2^п= uvwxy з |vwx| ? n і |vx| ? 1. (1) говорить нам, що vwx не містить одночасно 0 і 2. Таким чином, або vwx не має 0, або vwx не має 2. Таким чином, ми маємо два випадки для розгляду. Припустимо, що vwx не має 0. Відповідно до (2), vx містить 1 або 2. Таким чином, uwy має «n» 0, а uwy або менше, ніж «n» 1, або менше, ніж «n» 2. Але (3) говорить нам, що uwy = uv⁰wx⁰y ? L. Отже, uwy має однакову кількість 0, 1 і 2, що дає нам протиріччя. Випадок, коли vwx не має двійок, подібний і також дає нам суперечність. Таким чином, L не є контекстно-вільним. Джерело: Джон Е. Хопкрофт, Раджив Мотвані, Джеффрі Д. Уллман (2003). Вступ до теорії автоматів, мов і обчислень.

Цю статтю надав Нірупам Сінгх .