Warunek nieskończoności języka automatu skończonego

9

Istnieje twierdzenie, które mówi, że:

Biorąc pod uwagę automat skończony mający stanów, jeśli istnieje ciąg którego długość spełnia wówczas język akceptowany przez automat jest nieskończony.nwn≤|w|≤2n−1

Rozumiem ograniczenie , ale nie rozumiem, dlaczego ograniczenie jest tam.|w|≥n|w|≤2n−1

automata finite-automata Rahul Sharma
źródło

Odpowiedzi:

5

W najgorszym przypadku Twój NFA może wyglądać następująco:

Najmniejszy dla którego gwarantuje się zapętlenie (zmuszając go do zaakceptowania nieskończonego języka) ma rozmiar .w2n−1

André Souza Lemos
źródło
Kiedy zaczynam od q0, a potem, kiedy wróciłem do q0, oznacza to, że w maszynie jest cykl. Czy to nie wystarczy w najgorszym przypadku, dlaczego w tym przypadku wracamy do ostatniego etapu? O ile rozumiem na podstawie tej liczby, że przepompujemy tę pętlę raz, a następnie przejdziemy ponownie do końcowego etapu, co oznacza gdy wejdziemy w końcowy etap, zakładamy, że to nie jest mój ciąg znaków, ponieważ wrócił do innego stanu, ale gdy ponownie wróci do końcowego etapu, jesteśmy pewni, że to nasz ciąg, ponieważ istnieje pętla, która ma zostałeś napompowany?
rahul sharma
Próbujemy udowodnić coś o automacie, a mianowicie, że akceptuje on nieskończony język. W sposobie formułowania dowodu zakłada się ciąg , którego rozmiar przyjmuje się w pewnym przedziale. Oczywiście, jeśli automat ma pętlę, to łańcuch istnieje. To, co się dzieje, jest takie, że jeśli nie można znaleźć w tym przedziale czasu, maszyna nie może być taka jak na zdjęciu. Albo nie ma pętli, albo nie ma stanów końcowych. www
André Souza Lemos
Rozumiem twój punkt. Próbuję po prostu zrozumieć górną granicę przedziału, dlaczego jest to 2n-1 i dlaczego nie 2n-x (x może być czymkolwiek innym niż 1). Na powyższym rysunku możemy powiedzieć, że pętla to qo -q1 .... qn-q1 .... qn, prawda (maks. pętla)? Ale kiedy znów jestem q0 (q0 ... aq, q0), czy to nie oznacza, że ​​istnieje pętla, więc maksimum powinno wynosić n, dlaczego dodajemy n-1 do n (lub dlaczego ponownie osiągniemy stan końcowy). Mam trudności z uzyskaniem tego :(. maks. pętla może wynosić q0., q1, q2 ..qn, qn-1, qn-1..q0, coś takiego?
rahul sharma
Górna granica wynosi ponieważ nie pogarsza się. jest mniejszy niż , a ja właśnie pokazałem ci automat, który wymaga kroków . Nie ma takiej, która potrzebuje więcej (i wykonuje pracę), ale jest taka, która potrzebuje tej kwoty. 2n−12n−x2n−12n−1
André Souza Lemos
Rozumiem teraz. Tylko jedna mała wątpliwość. Załóżmy, że mam 4 stany w mojej maszynie. I przeczytałem ciąg znaków abc i osiągnąłem stan końcowy, a następnie przeczytałem d i wróciłem do stanu początkowego, a następnie ponownie przechodzi do stanu końcowego, więc mój ciąg stanie się abcdabc. Jak mogę to przełamać na pompowanie lematu i uzyskać y ^ i, gdzie i = 1, aby pokazać, że y zostało przepompowane raz?
rahul sharma
5

Dodatkowy warunek pozwala napisać prosty algorytm - sprawdzanie wszystkich ciągów o długościach w tym przedziale - do decydowania o (nie) skończoności akceptowanego języka. W ten sposób otrzymujesz dowód, że ta właściwość jest rozstrzygalna (czego nie ma w przypadku większości modeli automatów o super regularnej mocy).

Raphael
źródło
3

Pełne twierdzenie podaje raczej równoważność niż implikację :

Język akceptowany przez stanowy NFA jest nieskończony, jeśli i tylko jeśli zawiera słowo którego rozmiar spełnia .nwn≤|w|≤2n−1

Dodatkowy warunek czyni więc twierdzenie silniejszym .|w|≤2n−1

Yuval Filmus
źródło