Profitieren XOR-Automaten (NXA) für endliche Sprachen von Zyklen?

Eine nicht deterministische Xor-Automate (NXA) ist syntaktisch eine NFA, aber ein Wort wird von NXA akzeptiert, wenn es eine ungerade Anzahl von Akzeptanzpfaden aufweist (anstelle von mindestens einem Akzeptanzpfad im NFA-Fall).

Es ist leicht zu erkennen, dass es für eine endliche reguläre Sprache eine minimale NFA gibt, die keine Zyklen enthält (wenn ein Zyklus sowohl vom Anfangszustand aus erreichbar war als auch Sie von diesem in einen akzeptierenden Zustand gelangen - Ihre Sprache ist es nicht) endlich).$L$

Dies ist bei NXAs nicht unbedingt der Fall.

Bezeichne mit die xor-Zustandskomplexität einer Sprache L ,$xsc(L)$$L$

und durch die Komplexität des azyklischen x oder Zustands von L (dh die Größe eines kleinsten azyklischen NXA, das L akzeptiert ).$axsc(L)$$L$$L$

Stimmt es, dass für jede endliche Sprache : a x s c ( L ) = x s c ( L ) $L$

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

Ich denke, dass die Antwort bejahend ist. Vielleicht gibt es einen einfacheren Beweis, aber hier ist eine Skizze eines Beweises, der lineare Algebra verwendet.

Wie bei domotorp betrachten wir eine Konfiguration eines XOR-Automaten mit n Zuständen als Vektor in V = GF (2) ⁿ .

Sei L eine endliche Sprache über einem Alphabet Σ = {1,…, k } und betrachte einen XOR-Automaten für L mit der minimalen Anzahl von Zuständen. Sei n die Anzahl der Zustände. Wir nehmen an, dass die Zustände mit 1,…, n bezeichnet sind und Zustand 1 der Anfangszustand ist.

Zuerst richten wir die Notation ein. Sei v ₀ = (1, 0,…, 0) ^T ∈ V der dem Anfangszustand entsprechende Elementarvektor, und sei s der Zeilenvektor, dessen i- ter Eintrag genau dann 1 ist, wenn der Zustand i ein akzeptierender Zustand ist. Der Unterraum R = { v : s v = 0} von V entspricht den Konfigurationsvektoren, die zurückgewiesen werden.

Für jedes a a sei A _a die n × n- Matrix über GF (2), die den durch den Buchstaben a verursachten Übergang darstellt . Zum Beispiel kann die Konfigurationsvektor nach dem Eingabestring zu lesen a b ist A _B A _a v ₀ . Für einen String σ = a ₁ … a _t bezeichnen wir das Produkt A _{a t} … A _{a 1} mit M ( σ ). Sei S = { A ₁ ,…, A _k }.

Ein Unterraum W von V gilt als S - invariant, wenn A W ⊆ W für jedes A ∈ S ist . In unserem Kontext bedeutet dies, dass, sobald der Konfigurationsvektor in W geht , es keinen Ausweg aus W gibt, indem mehr Buchstaben gelesen werden.

Da dieser XOR-Automat die minimale Anzahl von Zuständen hat, haben wir die folgenden Eigenschaften.

• Der einzige S- Varianten-Unterraum von V , der v ₀ enthält, ist V selbst. Dies liegt daran , dass wir W verwenden können, wenn W ein echter S- Invarianten-Unterraum mit v ₀ ist anstelle von V verwenden können , was der Minimalität widerspricht.
• Der einzige in R enthaltene S- Varianten-Unterraum ist {0}. Dies liegt daran, dass, wenn W ein in R enthaltener nichttrivialer S- varianter Unterraum ist , wir den Quotientenvektorraum V / W anstelle von V verwenden können , was wiederum der Minimalität widerspricht.

Da L endlich ist, lassen m eine ganze Zahl größer ist als die Länge jeder Zeichenfolge in sein L .

Lemma 1 . Für jeden String σ mit einer Länge von mindestens m gilt M ( σ ) = 0.

Beweis. Zunächst beweisen wir , dass für jeden String σ der Länge mindestens m , haben wir , dass M ( σ ) v ₀ = 0. Lass W der von { M ( σ ) v ₀ aufgespannte Unterraum von V : σ ist eine Kette mit einer Länge von mindestens m }. Per Definition ist W eine S- Variable. Da der betreffende XOR-Automat diese Zeichenketten & sgr ; ablehnt , ist W in R M ( & sgr; ) v _{0 enthalten} . Also W = {0}, was das bedeutet= 0 für alle diese Zeichenfolgen σ .

Betrachten wir nun jeden Vektor v ∈ V . Da der einzige S -invariant Unterraum von V , die enthält v ₀ ist , V selbst, v kann als eine lineare Kombination von Vektoren der Form geschrieben werden M ( τ ) v ₀ für einige Zeichenketten & tgr; . Weil M ( σ ) M ( τ ) v ₀ = M ( τ σ ) v _{0 ist}= 0 (die letztere Gleichheit folgt aus dem vorhergehenden Absatz, weil die Länge von v = 0. ■τ σ ist mindestens m ), es gilt, dass M ( σ )

Wir brauchen noch eine Tatsache aus der linearen Algebra.

Lemma 2 . Lassen A ₁ , ..., A _k ist n × n Matrizen über ein Feld und definieren M ( σ ) wie oben. Wenn es m ≥ 0 gibt, so dass M ( σ ) = 0 für jeden String σ ist einer Länge von mindestens m ist , dann sind die Matrizen A ₁ ,…, A _k gleichzeitig den streng unteren Dreiecksmatrizen ähnlich es gibt ein n) × n nicht-singuläre Matrix P, so dass die Matrizen P ^–1 A₁ P ,…, P ⁻¹ A _k P sind streng unteres Dreieck).

Der Fall von k = 1 ist eine bekannte Charakterisierung von nilpotenten Matrizen, und Lemma 2 kann auf die gleiche Weise bewiesen werden.

Betrachten wir nun den n- Zustand-XOR-Automaten, in dem die dem Symbol a ∈Σ entsprechende Übergangsmatrix durch P ^{−1 gegeben ist} A _a P gegeben ist , der Anfangskonfigurationsvektor durch P ⁻¹ v _{0 gegeben} ist und der charakteristische (Zeilen-) Vektor von die akzeptierenden Zustände sind durch s P gegeben . Konstruktionsbedingt akzeptiert dieser XOR-Automat die gleiche Sprache L. Da die Übergangsmatrizen streng dreieckig sind, wechselt jede Übergangsflanke in diesem XOR-Automaten von einem Zustand mit kleinerem Index zu einem Zustand mit größerem Index, und daher ist dieser XOR-Automat azyklisch. Obwohl der anfängliche Konfigurationsvektor mehr als eine 1 haben kann, ist es einfach, diesen XOR-Automaten in einen üblichen XOR-Automaten mit einem einzigen Anfangszustand für dieselbe Sprache umzuwandeln, ohne die Anzahl der Zustände zu erhöhen oder die Azyklizität zu ruinieren.

Ich denke, ich kann beweisen, dass Zyklen nicht über das unäre Alphabet helfen.

$M$$F_2$ Beschreiben, aus welchem ​​Zustand in welchen Zustand wir in einem Schritt und den Vektor gelangen können $v_n$ Über $F_2$ Beschreibung der möglichen Zustände des Automaten $\mod 2$ nach $n$ Schritte, so $v_n=M^nv_0$, wo $v_0=(1,0,..,0)$beschreibt den Ausgangszustand. Wenn wir das nach einiger Zeit wissen$t$ Schritte $s\cdot v=0$ (wo $s$ist der charakteristische Vektor der akzeptierenden Zustände), dh wir befinden uns in einem bestimmten Unterraum. Die Dimension von$M^n$ist streng monoton abnehmend für eine Weile, dann konstant. Das heißt, wir müssen das Subsapce erreichen$s\cdot v_n=0$nach höchstens so vielen schritten, wie viele zustände der automat hat. Aber dann gibt es einen zyklenfreien Automaten, der nur die Länge des Wortes zählt.