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

Од Википедија — слободната енциклопедија
Прејди на прегледникот Прејди на пребарувањето

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

Формален изказ[уреди | уреди извор]

Ако јазикот 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 = {0n 1 : n ≥ 0} не е регуларен над азбуката Σ = {0,1} .

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


Sostojbi.jpg

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

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

Доказ[уреди | уреди извор]

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

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

Pumping lemma.jpg

Автоматот го прифаќа стрингот abcbcd. Овој стринг е подолг од бројот на состојби кои ги има автоматот, повторените состојби се q1 и q2. Бидејќи подстрингот bcbc од стрингот abcbcd го носи автоматот низ премин кој започнува од состојбата q1 и завршува во состојбата q1, то доколку тој подстринг се повторува многу пати како на пример во 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.

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