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^*$

automata-theory fl.formal-languages nondeterminism

— 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) = 2^{n - o (n)}

$f(n)=2^{n−o(n)}$

| Σ | \geq 2

$|\Sigma|\geq 2$

— Hsien-Chih Chang 之之

Odpowiedzi:

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.

— Tsuyoshi Ito
źródło

Jakie jest twoje przypuszczenie o najlepszej wartości ? Powiedz , albo gdzieś pomiędzy a ?

f

$f$

f (n) = 2^{n} + 1

$f(n) = 2^n+1$

2^{n}

$2^n$

2^{c \cdot \sqrt{n}}

$2^{c\cdot\sqrt{n}}$

— 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)

1 / \sqrt{2}

$1/\sqrt2$

f (n) > e^{c \sqrt{n \ln n}}

$f(n) > e^{c\sqrt{n \ln n}}$

— 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,

@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.pdf

m = O (e^{\sqrt{n \log n}})

$m=O(e^{\sqrt{n\log n}})$

— Hsien-Chih Chang 之之

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ść . $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ć:

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 . $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$

— 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 .

2^{n}

$2^n$

\hat{Ω} (2^{n})

$\hat{\Omega}(2^n)$

c n + o (n)

$cn+o(n)$

f (n)

$f(n)$

f (n) + 1

$f(n)+1$

c \leq 22

$c \leq 22$

2^{n}

$2^n$

— Hsien-Chih Chang 之之

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 .

3 n + O (1)

$3n+O(1)$

— Hsien-Chih Chang 張顯之

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,