Пампинг лема за регуларни јазици

Во теоријата за формални јазици, пампинг лемата за регуларните јазици е лема која ја дава областа која ја имаат регуларните изрази. Нејзината примарна употреба е да докаже кои јазици не се регуларни.

Формален изказ

Ако јазикот L e регуларен тогаш постои некој број p>0 така што секој стринг w во L и за кои важи |w| ≥ p можат да се напишат во следнава форма каде што p е големината на напумпаноста:

w = xyz

каде што низите x,y и z се такви што ги задоволуваат усливите |xy| ≤ p, |y| > 0 и xy i z е елемент на L за секој цел број i ≥ 0.

Користење на лемата

Со користење на лемата за да докажеме дека некој јазик не е регуларен, обично тоа го правиме со контрадикторност. Ако претпоставиме дека јазикот L е регуларен, тогаш пампинг лемата мора да биде точна за секоја низа во тој јазик. Со покажување дека постои барем еден елемент кој не ја поддржува лемата покажуваме дека тој јазик не е регуларен.

Со користење на лемата ќе докажеме дека јазикот L = {0^{n 1} : n ≥ 0} не е регуларен над азбуката Σ = {0,1} .

Да претпоставиме дека јазикот е регуларен, тогаш тој мора да биде препознаен од некој Детерминистички Конечен Автомат A кој има конечен број на состојби k. Ако A прочита k нули, тогаш треба да помине низ следнава секвенца на состојби:

Тоа се вкупно к+1 претставки кои ќе предизвикаат к+1 промена на состојбата. Бидејќи тоа се само к состојби, значи дека , автоматот мора да е повторно во некоја состојба во која претходно бил. Ова значи дека дава различни претставки за 0ⁱ и 0^j автоматот ќе биде во иста состојба p.

Нека автоматот прима 1 како влез. Ако прочита i тој треба да го прифати зборот ако преткодно прочитал i₀, односно да го одби ако прочитал ј₀. Тоа значи дека во состојбата р автоматот не знае колку 0 прочитал, па и не може да донесе јасна одлука дали да го прифати зборот или да го одбие.

Доказ

Доказот за лемата е поткрепен од тоа дека секој регуларен јазик е проследен со конечен автомат кој го прифаќа јазикот. Ако регуларниот јазик е конечен, тогаш според лемата тривијално нема да постои стринг кој ќе ја надмине напумпаната должина. Ако регуларниот јаизик е бескончен , тогаш мора да постои некој минимален ДКА кој ќе го прифати овој јазик. Бројот на состојбите на автоматот се бројат и тие треба да се еднакви по број со напумпаната должина р. Ако стрингот е подолг од р, тогаш мора да постои барем една состојба која се повторува (ќе претпоставиме дека тоа е состојбата S). Преодните состојби кои ја го носат автоматот од состојба Ѕ повторно назад во состојва Ѕ всушност треба да биде истиот тој стринг. Тој стринг е наречен y во лемата, кога автоматот ќе дојде до состојба кога ќе ја достигне истата таа состојба без y поминувања, или кога y се повторува тогаш лемата е задоволена.

Полесно се гледа со пример.

Автоматот го прифаќа стрингот abcbcd. Овој стринг е подолг од бројот на состојби кои ги има автоматот, повторените состојби се q₁ и q₂. Бидејќи подстрингот bcbc од стрингот abcbcd го носи автоматот низ премин кој започнува од состојбата q₁ и завршува во состојбата q₁, то доколку тој подстринг се повторува многупати како на пример во abcbcbcbcd, или ако целосно се одстрани ДКА секако ќе го прифати стрингот ad. Според правилата на лемата стрингот abcbcd е поделен на делови x кој всушност е а, y кој всушност е делот кој се повторува и z кој е bcd. (Забелешка: може да се подели и вака x=a, y=bcbc, z=d на овој начин сите услови се исполнети освен |xy| ≤ p ) . Генерална верзија на pumping lemma-та за регуларните јазици

Ако јазикот L e регуларен, тогаш постои број р>0 така што за секој стринг uwv во L и |w| ≥ p може да биде напишано во формата , каде што р е големината на пумпањето.

uwv = uxyzv

со стринговите x,y, и z, така што |xy| ≤ p, |y| > 0 и uxyizv припаѓа на L за секое i ≥ 0.

Со оваа верзија може да се докаже дека многу повеќе јазици не се регуларни.