Warunki dla uniwersalności NFA

28

Rozważ niedeterministyczny automat skończony A=(Q,Σ,δ,q0,F) i funkcję f(n) . Dodatkowo definiujemy Σk=ikΣi .

Teraz przeanalizujmy następujące oświadczenie:

Jeżeli Σf(|Q|)L(A) , to L(A)=Σ .

Łatwo jest wykazać, że dla f(n)=2n+1 jest to prawdą, dlatego jeśli automaty produkują każde słowo o długości do 2|Q|+1 , a następnie daje Σ .

Ale czy nadal tak jest, jeśli f jest wielomianem?

ApΣp(|Q|)L(A)Σ

Mike B.
źródło
Chciałbym dać nagrodę dowodowi lub dyskomfortowi, że za sprawę . A jeśli go nie ma, dam mu najlepszą konstrukcję, jaką można uzyskać. f(n)=2no(n)|Σ|2
Hsien-Chih Chang 之 之

Odpowiedzi:

22

Aby wypowiedź mogła się utrzymać, f musi rosnąć wykładniczo, nawet w przypadku jednoznacznego alfabetu.

[Edycja: Analiza została nieznacznie poprawiona w wersji 2.]

Oto szkic próbny. Załóżmy, że instrukcja posiada i niech f będzie funkcją taką, że każdy NFA z najwyżej n stanami, które akceptują wszystkie łańcuchy o długości co najwyżej f ( n ), akceptuje wszystkie łańcuchy. Udowodnimy, że dla każdego C > 0 i wystarczająco dużego n mamy f ( n )> 2 C ⋅√ n .

Liczba pierwsza twierdzenie oznacza, że dla każdego c <lg E i dla dostatecznie dużej k , istnieją co najmniej c ⋅2 k / k liczb pierwszych w zakresie [2 k 2 k + 1 ]. Bierzemy c = 1. Dla takiego k , niech N k = ⌈2 k / k ⌉ i zdefiniuj NFA M k w następujący sposób. Niech p 1 ,…, p N k będą różnymi liczbami pierwszymi w zakresie [2 k , 2 k +1]. NFA M K ma S k = 1 + s 1 + + ... p N k stanów. Niezależnie od stanu pierwotnego stany są podzielone na N k cykli gdzie i tym cyklu ma długość p ı . W każdym cyklu wszystkie stany oprócz jednego są stanami akceptowanymi. Początkowy stan ma N k wychodzące krawędzie, z których każdy przechodzi do stanu bezpośrednio po odrzuconej państwa w każdym cyklu. Wreszcie, stan początkowy jest również akceptowany.

Niech P k będzie iloczynem p 1p N k . Łatwo jest zauważyć, że M k akceptuje wszystkie ciągi o długości mniejszej niż P k ale odrzuca ciąg długość P k . Dlatego f ( S k ) ≥ P k .

Należy zauważyć, że S k ≤ 1 + N k ⋅2 k +1 = o (2 2 k ) i że P k ≥ (2 k ) N k ≥ 2 2 k . Reszta jest standardem.

Tsuyoshi Ito
źródło
Jakie jest twoje przypuszczenie o najlepszej wartości ? Powiedz , albo gdzieś pomiędzy a ? f ( n ) = 2 n + 1 2 n 2 c ff(n)=2n+12n2cn
Hsien-Chih Chang 張顯 之
@ Hsien-Chih: Zastanawiałem się nad tym samym i nie mam żadnych racjonalnych przypuszczeń. Po pierwsze, trywialne jest zobaczenie f (n) ≤2 ^ n (nie potrzebujemy +1) i chociaż oczekuję pewnej liniowej poprawy w stosunku do tej górnej granicy, nie mam pojęcia, czy jest ona ścisła do stałego współczynnika. (więcej)
Tsuyoshi Ito,
(kont.) Po drugie, jeśli chodzi o dolną granicę, jeśli się nie mylę, nieznaczne udoskonalenie powyższej analizy daje następującą dolną granicę: dla każdej stałej 0 <c < i wystarczająco dużego n mamy . Możliwe są dalsze udoskonalenia, ale nie możemy uzyskać dolnej granicy, takiej jak 2 ^ {n ^ p} dla p> 1/2, jeśli użyjemy tej samej konstrukcji NTM. Myślę, że interesujące jest pytanie, czy zastosowanie rozkładu liczb pierwszych (takich jak PNT) jest niezbędne do skonstruowania złych przykładów. (więcej) f(n)>e c 1/2f(n)>ecnlnn
Tsuyoshi Ito,
(kont.) Jeśli jednak jesteś zainteresowany i chcesz to zbadać dalej, prawdopodobnie lepiej jest najpierw poszukać literatury. Nie zdziwię się, jeśli ta odpowiedź lub coś lepszego pojawiło się już w literaturze.
Tsuyoshi Ito,
5
@Tsuyoshi: Chrobak pokazuje, że NFA stanu n dla języka jednoargumentowego może być symulowany przez NFA stanu dla . Zatem twoja konstrukcja jest ciasna, jeśli język jest jednolity. Patrz [Chr86]: cs.ust.hk/mjg_lib/Library/Chro86.pdfm=O(enlogn)
Hsien-Chih Chang 之 之
19

EDYCJA AT 10/12/06:

ok, to prawie najlepsza konstrukcja, jaką mogę uzyskać, zobacz, czy ktoś wpadnie na lepsze pomysły.

Twierdzenie. Dla każdego Istnieje NFA nad alfabetami z tak że najkrótszy ciąg nie w ma długość .( 5 n + 12 ) M Σ | Σ | = 5 L ( M ) ( 2 n - 1 ) ( n + 1 ) + 1n(5n+12)MΣ|Σ|=5L(M)(2n1)(n+1)+1

To da nam .f(n)=Ω(2n/5)

Konstrukcja jest prawie taka sama jak w Shallit , z tym wyjątkiem, że konstruujemy NFA bezpośrednio zamiast reprezentowania języka przez wyrażenie regularne. Pozwolić

Σ={[00],[01],[10],[11],} .

Dla każdego zbudujemy język rozpoznający NFA , gdzie jest następującą sekwencją ( na przykład ):nΣ{sn}snn=3

s3=[00][00][01][00][01][10][11][11][01] .

Chodzi o to, że możemy zbudować NFA składający się z pięciu części;

  • rozrusznik , który zapewnia rozpoczyna ciągów ;[00][00][01]
  • terminator , który zapewnia końce ciągów ;[11][11][01]
  • licznik , który utrzymuje liczbę symboli między dwoma „S, ;n
  • dodatek jednego rejestratora , który gwarantuje, że tylko symbole z postaci pojawia; Wreszcie,xx+1
  • zgodne sprawdzania , co zapewnia, że tylko symbole z postaci mogą pojawić się równocześnie.xyyz

Zauważ, że chcemy zaakceptować zamiast , więc gdy dowiemy się, że sekwencja wejściowa jest niezgodna z jednym z powyższych zachowań, natychmiast ją akceptujemy. W przeciwnym razie pokroki, NFA będzie w jedynym możliwym stanie odrzucenia. A jeśli sekwencja jest dłuższa niż, NFA również akceptuje. Tak więc każdy NFA spełnia powyższe pięć warunków tylko odrzuca .Σ{sn}{sn}|sn||sn|sn

Bezpośrednim sprawdzeniem poniższej figury zamiast rygorystycznego dowodu może być:

NFA za odrzucenie s_n

Zaczynamy w lewym górnym rogu. Pierwsza część to starter i licznik, następnie spójny kontroler, terminator, a na końcu kontroler add-one. Cały łuk bez węzłów końcowych wskazuje na dolny prawy stan, który jest akceptorem przez cały czas. Niektóre krawędzie nie są oznakowane z powodu braku spacji, ale można je łatwo odzyskać. Linia przerywana reprezentuje sekwencję stanów z krawędziami .n1n2

Możemy (z bólem) zweryfikować, czy NFA odrzuca tylko , ponieważ przestrzega wszystkich pięciu powyższych zasad. Tak więc zbudowano NFA z , co spełnia wymaganie twierdzenia.sn(5n+12)|Σ|=5

Jeśli jest jakaś niejasność / problem z konstrukcją, proszę zostawić komentarz, a ja postaram się wyjaśnić / naprawić.


To pytanie zostało zbadane przez Jeffreya O. Shallita i in., A faktycznie optymalna wartość jest wciąż otwarta dla . (Jeśli chodzi o język jednoargumentowy, zobacz komentarze w odpowiedzi Tsuyoshi )f(n)|Σ|>1

Na stronach 46-51 swojego wystąpienia na temat uniwersalności przedstawił konstrukcję, która:

Twierdzenie. Dla dla niektórych wystarczająco dużych, istnieje NFA nad binarnymi alfabetami, tak że najkrótszy ciąg nie w ma długość dla .nNNnML(M)Ω(2cn)c=1/75

Zatem optymalna wartość dla wynosi gdzieś między a . Nie jestem pewien, czy wynik Shallita poprawił się w ostatnich latach.f(n)2n/752n

Hsien-Chih Chang 張顯 之
źródło
Bawię się pracą Shallita, mam nadzieję, że uda mi się uzyskać lepszą granicę blisko . Ich konstrukcja wydaje się interesująca, podając pewną sekwencję długości której nie można przedstawić za pomocą „krótkiego” wyrażenia regularnego o długości i każdego wyrażenia regularnego o długości można opisać NFA o wielkości . Obecnie jestem w stanie pozwolić , ale mądrzejszy pomysł wymaga zbliżenia . 2nΩ^(2n)cn+o(n)f(n)f(n)+1c222n
Hsien-Chih Chang 之 之
2
Nie sądzę, że daje to więcej wglądu w badanie tego problemu, ale właściwym odniesieniem naukowym do wypowiedzi Shallita są: K. Ellul, B. Krawetz, J. Shallit, M. Wang: Wyrażenia regularne: nowe wyniki i otwarte problemy. Journal of Automata, Languages ​​and Combinatorics 10 (4): 407-437 (2005)
Hermann Gruber,
@Hermann: Dziękuję za referencje, obecnie nie mam dostępu do gazety, ale znajdę sposób.
Hsien-Chih Chang 張顯 之
Myślę, że używając licznika możemy zastąpić rozrusznik i terminator 2-stanową małą maszyną. To dodatkowo zmniejsza rozmiar NFA do . 3n+O(1)
Hsien-Chih Chang 張顯 之
1
Autorska wersja przedruku znanego papieru JALC znajduje się tutaj: cs.uwaterloo.ca/~shallit/Papers/re3.pdf Oprawa, a dowód w wersji drukowanej jest taki sam.
Hermann Gruber,