Co to jest lemat pompowania w kategoriach laika?

Widziałem to pytanie i byłem zaciekawiony, jaki był lemat o pompowaniu ( Wikipedia niewiele pomogła).

Rozumiem, że jest to w zasadzie teoretyczny dowód, który musi być prawdziwy, aby język był w określonej klasie, ale poza tym tak naprawdę go nie rozumiem.

Czy ktoś chciałby spróbować wyjaśnić to na dość szczegółowym poziomie w sposób zrozumiały dla nie-matematyków / doktorów nauk ścisłych?

Lemat o pompowaniu jest prostym dowodem na to, że język nie jest regularny, co oznacza, że ​​nie można dla niego zbudować maszyny skończonej. Przykładem kanonicznym jest język (a^n)(b^n). To jest prosty język, w którym występuje dowolna liczba as, po których następuje ta sama liczba bs. Więc struny

ab
aabb
aaabbb
aaaabbbb

itp. są w języku, ale

aab
bab
aaabbbbbb

itp. nie są.

Zbudowanie FSM jest dość proste dla tych przykładów:

Ten będzie działał aż do n = 4. Problem polega na tym, że nasz język nie nakładał żadnych ograniczeń na n, a maszyny skończone muszą być, cóż, skończone. Bez względu na to, ile stanów dodam do tej maszyny, ktoś może podać mi dane wejściowe, gdzie n równa się liczbie stanów plus jeden, a moja maszyna ulegnie awarii. Więc jeśli może być maszyna zbudowana do czytania tego języka, musi być gdzieś tam pętla, aby liczba stanów była ograniczona. Po dodaniu tych pętli:

wszystkie ciągi w naszym języku zostaną zaakceptowane, ale jest problem. Po pierwszych czterech asekundach maszyna traci liczbę awprowadzonych sekund, ponieważ pozostaje w tym samym stanie. Oznacza to, że po czterech mogę dodać dowolną liczbę as do ciągu, bez dodawania żadnych bs, i nadal otrzymuję tę samą wartość zwracaną. Oznacza to, że ciągi:

aaaa(a*)bbbb

z (a*)reprezentacją dowolnej liczby as, wszystkie zostaną zaakceptowane przez maszynę, mimo że oczywiście nie wszystkie są w języku. W tym kontekście powiedzielibyśmy, że część sznurka (a*)może być pompowana. Fakt, że maszyna skończona jest skończona, a n nie jest ograniczona, gwarantuje, że każda maszyna, która akceptuje wszystkie łańcuchy w języku, MUSI mieć tę właściwość. Maszyna musi w pewnym momencie zapętlić się, aw momencie zapętlenia język może być pompowany. Dlatego nie można zbudować żadnej maszyny skończonej dla tego języka, a język nie jest regularny.

Pamiętaj, że wyrażenia regularne i skończonej maszyny państwowe są równoważne , a następnie zastąpienie ai bz otwierania i zamykania znaczników HTML, które mogą być osadzone w siebie, i można zobaczyć, dlaczego nie można używać wyrażeń regularnych do parsowania HTML

To urządzenie, które ma udowodnić, że dany język nie może należeć do określonej klasy.

Rozważmy język zrównoważonych nawiasów (oznaczających symbole „(„ i ”)”, z uwzględnieniem wszystkich łańcuchów, które są zbalansowane w zwykłym znaczeniu, i żadnego, które nie jest). Możemy użyć lematu o pompowaniu, aby pokazać, że to nie jest normalne.

(Język jest zbiorem możliwych ciągów. Parser jest rodzajem mechanizmu, którego możemy użyć, aby sprawdzić, czy ciąg jest w języku, więc musi być w stanie odróżnić ciąg w języku lub ciąg na zewnątrz język. Język jest „zwykły” (lub „bezkontekstowy”, „kontekstowy” lub jakikolwiek inny), jeśli istnieje regularny (lub jakikolwiek) parser, który może go rozpoznać, rozróżniając ciągi w języku i ciągi nie w język.)

LFSR Consulting dostarczyło dobry opis. Możemy narysować parser dla języka regularnego jako skończony zbiór ramek i strzałek, ze strzałkami reprezentującymi znaki i łączącymi je prostokątami (działającymi jako „stany”). (Jeśli jest to bardziej skomplikowane, nie jest to zwykły język). Jeśli możemy uzyskać ciąg dłuższy niż liczba pól, oznacza to, że przeszliśmy przez jedno pole więcej niż raz. Oznacza to, że mieliśmy pętlę i możemy ją przeglądać tyle razy, ile chcemy.

Dlatego w przypadku zwykłego języka, jeśli możemy utworzyć dowolnie długi ciąg, możemy podzielić go na xyz, gdzie x to znaki, których potrzebujemy, aby dostać się na początek pętli, y to rzeczywista pętla, a z to cokolwiek trzeba sprawić, aby ciąg był ważny po pętli. Ważne jest to, że całkowite długości x i y są ograniczone. W końcu, jeśli długość jest większa niż liczba pudełek, oczywiście przeszliśmy przez inne pudełko, robiąc to, i tak jest pętla.

Tak więc w naszym zrównoważonym języku możemy zacząć od napisania dowolnej liczby lewych nawiasów. W szczególności dla danego parsera możemy napisać więcej lewych parenów niż jest pól, więc parser nie może powiedzieć, ile jest pozostałych parenów. Dlatego x to pewna ilość lewych parenów i to jest naprawione. y to także pewna liczba lewych parenów, która może rosnąć w nieskończoność. Można powiedzieć, że z to pewna liczba prawidłowych parenów.

Oznacza to, że możemy mieć ciąg 43 lewych i 43 prawych znaków rozpoznanych przez nasz parser, ale parser nie może tego stwierdzić z ciągu 44 lewych i 43 prawych, co nie jest w naszym języku, więc parser nie może przeanalizować naszego języka.

Ponieważ każdy możliwy regularny parser ma stałą liczbę pól, zawsze możemy napisać więcej lewych parenów niż to, a dzięki lematowi o pompowaniu możemy dodać więcej lewych parenów w sposób, którego parser nie może stwierdzić. Dlatego wyważony język nawiasów nie może być analizowany przez zwykły parser i dlatego nie jest wyrażeniem regularnym.

Trudno jest to uzyskać w kategoriach laika, ale w zasadzie wyrażenia regularne powinny zawierać niepusty podciąg, który można powtarzać tyle razy, ile chcesz, podczas gdy całe nowe słowo pozostaje ważne dla języka.

W praktyce lematy o pompowaniu nie wystarczą, aby udowodnić poprawność języka, ale raczej jako sposób na udowodnienie przez sprzeczność i pokazanie, że język nie pasuje do klasy języków (zwykłych lub bezkontekstowych), pokazując lemat o pompowaniu nie działa na to.

Zasadniczo masz definicję języka (na przykład XML), która jest sposobem na stwierdzenie, czy dany ciąg znaków („słowo”) należy do tego języka, czy nie.

Lemat o pompowaniu ustanawia metodę, za pomocą której można wybrać „słowo” z języka, a następnie wprowadzić w nim pewne zmiany. Twierdzenie stwierdza, że ​​jeśli język jest regularny, zmiany te powinny dawać „słowo”, które nadal pochodzi z tego samego języka. Jeśli słowo, które wymyśliłeś, nie jest w języku, to przede wszystkim język nie mógł być regularny.

Prosty lemat o pompowaniu dotyczy języków regularnych, które są między innymi zestawami łańcuchów opisywanymi przez automaty skończone. Główną cechą automatyzacji skończonej jest to, że ma ona tylko skończoną ilość pamięci opisaną przez jej stany.

Teraz przypuśćmy, że mamy ciąg, który jest rozpoznawany przez automat skończony i który jest dostatecznie długi, aby „przekroczyć” pamięć automatyki, czyli w którym stany muszą się powtarzać. Następnie istnieje podciąg, w którym stan automatu na początku podciągu jest taki sam, jak stan na końcu podciągu. Ponieważ odczyt podłańcucha nie zmienia stanu, może on zostać usunięty lub zduplikowany dowolną liczbę razy, bez automatyzmu. Zatem te zmodyfikowane ciągi również muszą zostać zaakceptowane.

Istnieje również nieco bardziej skomplikowany lemat o pompowaniu dla języków bezkontekstowych, w którym można usunąć / wstawić coś, co może być intuicyjnie postrzegane jako pasujące nawiasy w dwóch miejscach w ciągu.

Z definicji języki regularne to te, które są rozpoznawane przez automat skończony. Pomyśl o tym jak o labiryncie: stany to pokoje, przejścia to jednokierunkowe korytarze między pokojami, jest pokój początkowy i pokój wyjściowy (końcowy). Jak mówi nazwa „automat skończony”, istnieje skończona liczba pomieszczeń. Za każdym razem, gdy podróżujesz korytarzem, notujesz literę zapisaną na jego ścianie. Słowo można rozpoznać, jeśli znajdziesz ścieżkę z początkowego pokoju do ostatniego pokoju, przechodząc przez korytarze oznaczone jego literami, we właściwej kolejności.

Lemat o pompowaniu mówi, że istnieje maksymalna długość (długość pompowania), dla której możesz wędrować przez labirynt bez konieczności powrotu do pomieszczenia, przez który przeszedłeś wcześniej. Chodzi o to, że ponieważ jest tylko tyle różnych pokoi, do których możesz wejść, po przekroczeniu określonego punktu musisz albo wyjść z labiryntu, albo przejść przez tory. Jeśli uda Ci się przejść dłuższą ścieżką niż ta długość pompowania w labiryncie, to wybierasz objazd: wstawiasz (co najmniej jeden) cykl na swojej ścieżce, który można usunąć (jeśli chcesz, aby przejście przez labirynt rozpoznać mniejsze słowo) lub powtarzać (pompowane) w nieskończoność (pozwalając na rozpoznanie bardzo długiego słowa).

Istnieje podobny lemat dla języków bezkontekstowych. Języki te można przedstawić jako słowo akceptowane przez automaty przesuwające w dół, które są automatami skończonymi, które mogą korzystać ze stosu, aby zdecydować, które przejścia wykonać. Niemniej jednak, ponieważ nadal istnieje skończona liczba stanów, intuicja wyjaśniona powyżej przenosi się, nawet poprzez formalne wyrażenie własności może być nieco bardziej złożone .

Mówiąc językiem laików, myślę, że masz prawie rację. Jest to technika dowodowa (właściwie dwie) do udowodnienia, że ​​język NIE jest w określonej klasie.

Na przykład rozważmy język regularny (wyrażenia regularne, automaty itp.) Z nieskończoną liczbą ciągów. W pewnym momencie, jak powiedział starblue, zabrakło pamięci, ponieważ sznurek jest za długi dla automatu. Oznacza to, że musi istnieć kawałek łańcucha, którego automat nie może określić, ile masz jego kopii (jesteś w pętli). Tak więc dowolna liczba kopii tego podciągu w środku łańcucha i nadal jesteś w języku.

Oznacza to, że jeśli masz język, który nie posiada tej własności, to znaczy, nie jest wystarczająco długi łańcuch z NO podciąg, które można powtarzać dowolną ilość razy i nadal być w języku, to język nie jest regularny.

Na przykład weźmy ten język L = a ⁿ b ⁿ .

Teraz spróbuj wyobrazić sobie automat skończony dla powyższego języka przez kilka n .

jeśli n = 1, ciąg w = ab . Tutaj możemy zrobić automat skończony bez zapętlenia, jeśli n = 2, łańcuch w = a ² b ² . Tutaj możemy zrobić automat skończony bez zapętlenia

jeśli n = p , łańcuch w = a ^p b ^p . Zasadniczo można założyć automat skończony z 3 stopniami. Pierwszy etap wymaga serii wejść i przejścia do drugiego etapu. Podobnie od etapu 2 do etapu 3. Nazwijmy te etapy jako x , y i z .

Jest kilka spostrzeżeń

1. Zdecydowanie x będzie zawierać „A” i oo będzie zawierać „B”.
2. Teraz musimy mieć jasność co do y :
   • przypadek a : y może zawierać tylko „a”
   • przypadek b : y może zawierać tylko „b”
   • Przypadek c : y może zawierać kombinację „a” i „b”

Zatem stany automatu skończonego dla etapu y powinny być w stanie przyjmować dane wejściowe „a” i „b”, a także nie powinny przyjmować więcej a i b, których nie można policzyć.

1. Jeśli etap y przyjmuje tylko jeden „a” i jeden „b”, wymagane są dwa stany
2. Jeśli przyjmuje dwa „a” i jeden „b”, wymagane są trzy stany bez pętli i tak dalej ....

Zatem projekt etapu y jest całkowicie nieskończony. Możemy uczynić to skończonym tylko przez umieszczenie pewnych pętli, a jeśli umieścimy pętle, automat skończony może zaakceptować języki poza L = a ⁿ b ⁿ . Więc dla tego języka nie możemy skonstruować automatu skończonego. Dlatego nie jest regularne.

Nie jest to wyjaśnienie jako takie, ale jest proste. Dla a ^ nb ^ n nasz FSM powinien być zbudowany w taki sposób, że b musi znać liczbę a już przeanalizowanych i akceptuje taką samą liczbę b. FSM nie może po prostu robić takich rzeczy.