Kann ständige Mehrdeutigkeit die Zustandskomplexität einer regulären Sprache verringern?

Wir sagen , dass NFA ist ständig mehrdeutige Existieren , so dass jedes Wort durch entweder akzeptiert wird oder (exakt) Pfaden. $M$ $k\in \mathbb{N}$ $w\in \Sigma^*$ $0$ $k$

Wenn Automat für ständig mehrdeutig ist , dann heißt Eindeutiges FA (UFA). $M$ $k=1$ $M$

Sei eine reguläre Sprache. $L$

Kann ein konstant mehrdeutiger Automat für kleiner sein als der kleinste UFA, der akzeptiert ? Wie viel kleiner könnte es sein? $M_c$ $L$ $L$

Kann ein endlich mehrdeutiger Automat für dieselbe Sprache exponentiell kleiner sein als der kleinste CFA?

Es ist bekannt, dass es endlich mehrdeutige Automaten gibt (es gibt , so dass jedes Wort von bis zu Pfaden akzeptiert wird ), die exponentiell kleiner sind als die kleinste UFA für dieselbe Sprache, aber ich habe nichts über ständige Mehrdeutigkeit gesehen. $k$ $k$

Außerdem ist hier eine verwandte Frage, die ich vor ein paar Monaten hier gepostet habe.

BEARBEITEN:

Domotorps Antwort zeigt, dass polynomiell auf reduzierbar ist, geht jedoch nicht auf die Frage ein, ob wir diese polynomielle Raumreduktion durch s erreichen können. $CFA$ $UFA$ $CFA$

So ist die neue Frage wird: Wie viel kleiner (linear / quadratisch / etc.) Kann eine auf den minimal verglichen werden ? für die gleiche Sprache? $CFA$ $UFA$

sind

Übergänge erlaubt?

ϵ

$\epsilon$

Denis

Vielleicht kann dies hilfreich sein: In Kupke wird unter Trennen der Konstanten von der polynomischen Ambiguität endlicher Automaten die folgende Hierarchie dargestellt:

Ich habe das zugehörige Papier nicht überprüft , da es sich hinter der Paywall befindet.

dfa ≺_{2^{n}} unfa ≺_{2^{n}} cafa ≺_{2^{n}} ??? ≺_{2^{n}} pafa ≺_{2^{n}} n f a

$\text{dfa} \prec_{2^n} \text{unfa} \prec_{2^n} \text{cafa} \prec_{2^n} \text{???} \prec_{2^n} \text{pafa} \prec_{2^n} {nfa}$

Marzio De Biasi

Danke @MarzioDeBiasi, aber leider hilft das nicht (ich war auch hoffnungsvoll, als ich die Präsentation sah). Sie verwenden eine andere Schreibweise als die, die ich benutze (und die ich in verschiedenen Artikeln gesehen habe). Ihre "konstante Ambiguität" nannte ich endliche Ambiguität, daher war mir die Beziehung zwischen ihrer Cafa und der UFA bereits bekannt. Da meine Anwendung Lösungen für NPC-Probleme zählt, ist meine Sprache immer endlich, und als solches wird jedes Wort von

-Pfaden akzeptiert , die sie "konstant" nannten.

O (1)

$O(1)$

Ich frage mich, ob meine Definition dazu beiträgt, die Komplexität von Zuständen zu verringern, da ich einen CFA habe, der exponentiell kleiner ist als der kleinste UFA, den ich konstruieren kann, und ich habe mich gefragt, ob es möglich ist, dass es keinen kleinen UFA für die Sprache gibt.

@Denis, ja, aber würde es Ihnen helfen, die Komplexität des Staates zu reduzieren? Ich gehe davon aus, dass Sie durch solche Bewegungen nur die Anzahl der Kanten reduzieren können.

Antworten:

Ich beanspruche , dass für einige Sprache , wenn es eine mit CFA mit ist Staaten und oder Pfade für jedes Wort zu akzeptieren, dann gibt es eine UFA mit Staaten. Die Grundidee ist, dass die Zustände der UFA die (geordneten) c-Tupel der Zustände der CFA sind und sie genau dann akzeptieren, wenn alle c-Zustände akzeptieren. Natürlich müssen wir auch sicherstellen, dass es sich tatsächlich um unterschiedliche Berechnungen handelt und wir nicht alle Permutationen, so dass für diese müssen wir einige zusätzliche Speicherbits. $s$ $0$ $c$ $C_ss^c$ $c!$ $C_s$

Eine etwas detailliertere Beschreibung der Grundidee: Wenn ein Zustand der UFA ist, dann hat es einen Übergang von ihm (Lesen eines Buchstabens ) zu dem Zustand wenn und nur wenn der CFA einen Übergang hat (Lese Buchstaben ) von zu für jedes . Ein Zustand $(s_1,\ldots,s_c)$ $a$ $(s_1',\ldots,s_c')$ $a$ $s_i$ $s_i'$ $i$ $(s_1,\ldots,s_c)$ akzeptiert genau dann, wenn für jedes akzeptiert . Natürlich ist der Startzustand der UFA wobei der Startzustand der CFA ist. $s_i$ $i$ $(s_0,\ldots,s_0)$ $s_0$

Das Problem mit dem oben genannten ist, dass die simulierten Läufe des CFA möglicherweise identisch sind. Wir fügen also einige zusätzliche Informationen hinzu, die beispielsweise in einem Diagramm für Eckpunkte codiert sind , das eine Kante zwischen Eckpunkt und Eckpunkt wenn wir während des bisherigen Laufs mindestens einmal dieses . $c$ $c$ $i$ $j$ $c_i\ne c_j$

Jetzt haben wir noch ein Problem, dass wir alles gezählt haben mal wegen der möglichen permutationen. Wir können dies beheben , indem sie verlangen , dass , wenn die - ten und - ten Staaten das gleiche gewesen sein , bis jetzt und im nächsten Schritt würde sie sich unterscheidet, dann im nächsten Schritt des - ten Zustand sollte einen größeren Index hat. $c!$ $i$ $j$ $i$

domotorp
quelle

Danke, dass du @domotorp antwortest. Leider kann ich nicht sagen, dass ich es verstehe. Können Sie weitere Details angeben (z. B. Wie würde der Beweis der Ursprünglichkeit verschlüsselt?). Vielen Dank !

Mir ist auf jeden Fall klar geworden, dass es auch eine UFA für diese Sprache gibt, also vergiss es. Was ist mit dem restlichen Teil meiner Antwort?

Domotorp

M

$M$

k = c

$k=c$

c

$c$

w

$w$

c

$c$

Ich hoffe, jetzt ist es klar.

Domotorp