Warunki dla uniwersalności NFA

Rozważ niedeterministyczny automat skończony $A = (Q, \Sigma, \delta, q_0, F)$ i funkcję $f(n)$ . Dodatkowo definiujemy $\Sigma^{\leq k} = \bigcup_{i \leq k} \Sigma^i$ .

Teraz przeanalizujmy następujące oświadczenie:

Jeżeli $\Sigma^{\leq f(|Q|)} \subseteq L(A)$ , to $L(A) = \Sigma^*$ .

Łatwo jest wykazać, że dla $f(n) = 2^n+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 $\Sigma^*$ .

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

$A$$p$$\Sigma^{\leq p(|Q|)} \subseteq L(A) \subsetneq \Sigma^*$

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 ₁ ,…, p _{N k} będą różnymi liczbami pierwszymi w zakresie [2 ^k , 2 ^{k +1}]. NFA M _K ma S _k = 1 + s ₁ + + ... 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 ₁ … p _{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.

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 ) + $n$$(5n+12)$$M$$\Sigma$$|\Sigma|=5$$L(M)$$(2^n-1)(n+1)+1$

To da nam .$f(n) = \Omega(2^{n/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ć

$\Sigma = \{{0 \brack 0},{0 \brack 1},{1 \brack 0},{1 \brack 1},\sharp\}$ .

Dla każdego zbudujemy język rozpoznający NFA , gdzie jest następującą sekwencją ( na przykład ):$n$$\Sigma^*-\{s_n\}$$s_n$$n=3$

$s_3 = \sharp{0 \brack 0}{0 \brack 0}{0 \brack 1}\sharp{0 \brack 0}{0 \brack 1}{1 \brack 0}\sharp \ldots \sharp{1 \brack 1}{1 \brack 1}{0 \brack 1}\sharp$ .

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 ;$\sharp{0 \brack 0}{0 \brack 0}{0 \brack 1}\sharp$
• terminator , który zapewnia końce ciągów ;$\sharp{1 \brack 1}{1 \brack 1}{0 \brack 1}\sharp$
• licznik , który utrzymuje liczbę symboli między dwoma „S, ;$\sharp$$n$
• dodatek jednego rejestratora , który gwarantuje, że tylko symbole z postaci pojawia; Wreszcie,$\sharp{x \atop x+1}\sharp$
• zgodne sprawdzania , co zapewnia, że tylko symbole z postaci mogą pojawić się równocześnie.$\sharp{x \atop y}\sharp{y \atop z}\sharp$

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 .$\Sigma^*-\{s_n\}$$\{s_n\}$$|s_n|$$|s_n|$$s_n$

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

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 .$n-1$$n-2$

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.$s_n$$(5n+12)$$|\Sigma|=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)$$|\Sigma|>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 .$n\geq N$$N$$n$$M$$L(M)$$\Omega(2^{cn})$$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)$$2^{n/75}$$2^n$