Czy automaty XOR (NXA) dla języków skończonych korzystają z cykli?

Niedeterministyczne automaty Xor (NXA) są składniowo NFA, ale mówi się, że słowo jest akceptowane przez NXA, jeśli ma nieparzystą liczbę ścieżek akceptacji (zamiast co najmniej jednej ścieżki akceptacji w przypadku NFA).

Łatwo zauważyć, że dla skończonego języka regularnego $L$ istnieje minimalny NFA, który nie zawiera żadnych cykli (jeśli cykl był osiągalny zarówno ze stanu początkowego, jak i przechodziłeś z niego do stanu akceptacji - twój język nie jest skończone).

Nie musi tak być w przypadku NXA.

Oznaczmy przez złożoność xor-state języka ,$xsc(L)$$L$

i do acyklicznego złożoności stanu XOR (czyli rozmiar najmniejszego acykliczny NXA przyjmujący ).$axsc(L)$$L$$L$

Czy to prawda, że ​​dla każdego skończonego języka :$L$

$$axsc(L)=xsc(L)\ ?$$

Myślę, że odpowiedź jest twierdząca. Być może istnieje prostszy dowód, ale oto szkic dowodu, który używa algebry liniowej.

Podobnie jak domotorp, zobaczymy konfigurację n- stanowego automatu XOR jako wektora w V = GF (2) ⁿ .

Niech L będzie skończonym językiem nad alfabetem Σ = {1,…, k } i rozważmy automat XOR dla L z minimalną liczbą stanów. Niech n będzie liczbą stanów. Zakładamy, że stany są oznaczone 1,…, n , a stan 1 jest stanem początkowym.

Najpierw ustalamy notację. Niech V ₀ = (1, 0, ... 0) ^T ∈ V jako podstawowy wektora odpowiadającego stanu początkowego i pozwolić s być wektorem rząd którego I th wpisu 1 tylko wtedy, gdy stan i jest stan odbioru. Podprzestrzeń R = { v : s v = 0} V odpowiada wektorom konfiguracji, które zostały odrzucone.

Dla każdego a ∈Σ, niech A _a będzie macierzą n × n nad GF (2), która reprezentuje przejście spowodowane literą a . Na przykład wektor konfiguracji po odczytaniu ciągu wejściowego a b to A _b A _a v ₀ . Dla ciągu σ = a ₁ … a _t oznaczamy iloczyn A _{a t} … A _{a 1} przez M ( σ ). Niech S = { A ₁,…, A _k }.

Podprzestrzeni W o V mówi się S - niezmienny kiedy W ⊆ W dla każdego ∈ S . W naszym kontekście oznacza to, że gdy wektor konfiguracji przejdzie w W , nie ma wyjścia z W poprzez czytanie większej liczby liter.

Ponieważ ten automat XOR ma minimalną liczbę stanów, mamy następujące właściwości.

• Jedyny S- niezmienną podprzestrzenią V zawierającą v ₀ jest sama V. Wynika to z faktu, że jeśli W jest poprawną podprzestrzenią S- zmienną zawierającą v ₀ , wówczas możemy użyć W zamiast V , co jest sprzeczne z minimalnością.
• Jedyną podprzestrzenią zmienną S zawartą w R jest {0}. Dzieje się tak, ponieważ jeśli W jest nietrywialną podprzestrzenią S- zmienną zawartą w R , wówczas możemy użyć ilorazowej przestrzeni wektorowej V / W zamiast V , ponownie zaprzeczając minimalności.

Ponieważ L jest skończony, niech m jest liczbą całkowitą większa niż długość każdego łańcucha w L .

Lemat 1 . Dla dowolnego ciągu σ o długości co najmniej m mamy taką M ( σ ) = 0.

Dowód. Najpierw udowodnimy, że dla dowolnego ciągu σ o długości co najmniej m mamy M ( σ ) v ₀ = 0. Niech W będzie podprzestrzenią V rozpiętą na { M ( σ ) v ₀ : σ jest łańcuchem o długości co najmniej m }. Z definicji W jest niezmiennikiem S. Ponieważ automat XOR na pytanie odrzuca te łańcuchy Ď , W jest zawarta w R . Dlatego W = {0}, co oznacza, żeM ( σ ) v ₀ = 0 dla wszystkich takich łańcuchów σ .

Teraz rozważmy dowolny wektor v ∈ V . Ponieważ jedyną podprzestrzenią zmienną S V, która zawiera v _0, jest sama V , v można zapisać jako liniową kombinację wektorów postaci M ( τ ) v ₀ dla niektórych łańcuchów τ . Ponieważ M ( σ ) M ( τ ) v ₀ = M ( τ σ ) v ₀= 0 (ta ostatnia równość wynika z poprzedniego akapitu, ponieważ długość τ σ wynosi co najmniej m ), utrzymuje, że M ( σ ) v = 0. ■

Potrzebujemy jeszcze jednego faktu z algebry liniowej.

Lemat 2 . Niech A ₁ ,…, A _k będą macierzami n × n nad polem i zdefiniuj M ( σ ) jak powyżej. Jeżeli istnieje m ≥0 tak, że M ( σ ) = 0 dla każdego strumienia Ď o długości co najmniej m , wtedy macierze A ₁ , ..., _K są jednocześnie podobny ściśle niższe trójkątne macierzy (to znaczy, że istnieje N × n macierzy niejednolitej P takiej, że macierze P ^-1 A₁ P ,…, P ⁻¹ A _k P są ściśle dolnymi trójkątnymi).

Przypadek k = 1 jest dobrze znaną charakterystyką macierzy nilpotentnych, a Lemma 2 można udowodnić w ten sam sposób.

Rozważmy teraz n- stanowy automat XOR, w którym macierz przejścia odpowiadającą symbolowi a ∈Σ jest podana przez P ^-1 A _a P , wektor konfiguracji początkowej jest podany przez P ^-1 v ₀ , a wektor charakterystyczny (wierszowy) stany akceptujące jest przez ów P . Z założenia ten automat XOR akceptuje ten sam język L.. Ponieważ macierze przejściowe są ściśle dolne trójkątne, każda krawędź przejściowa w tym automacie XOR przechodzi ze stanu o mniejszym indeksie do stanu o większym indeksie, a zatem ten automat XOR jest acykliczny. Chociaż wektor początkowej konfiguracji może mieć więcej niż jeden 1s, łatwo jest przekonwertować ten automat XOR na zwykły automat XOR z jednym stanem początkowym dla tego samego języka bez zwiększania liczby stanów lub rujnowania acykliczności.

Myślę, że mogę udowodnić, że cykle nie pomagają w jednomyślnym alfabecie.

$M$$F_2$$v_n$$F_2$$\mod 2$$n$$v_n=M^nv_0$$v_0=(1,0,..,0)$$t$$s\cdot v=0$$s$$M^n$jest przez chwilę ściśle monotoniczny, a następnie stały. Oznacza to, że musimy dotrzeć do subsapce$s\cdot v_n=0$