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

16

Wir sagen , dass NFA ist ständig mehrdeutige Existieren k N , so dass jedes Wort w & Sigma; * durch entweder akzeptiert wird 0 oder (exakt) k Pfaden.MkNwΣ0k

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

Sei eine reguläre Sprache.L

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

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 k 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 U F A reduzierbar ist, geht jedoch nicht auf die Frage ein, ob wir diese polynomielle Raumreduktion durch C F A s erreichen können.CFAUFACFA

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

RB
quelle
sind Übergänge erlaubt? ϵ
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. dfa2nunfa2ncafa2n???2npafa2nnfa
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)
RB
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.
RB
1
@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.
RB

Antworten:

4

Ich beanspruche , dass für einige Sprache , wenn es eine mit CFA mit ist Staaten und 0 oder c Pfade für jedes Wort zu akzeptieren, dann gibt es eine UFA mit C s s c 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 c zählen ! Permutationen, so dass für diese müssen wir einige zusätzliche C s Speicherbits.s0cCsscc!Cs

Eine etwas detailliertere Beschreibung der Grundidee: Wenn ein Zustand der UFA ist, dann hat es einen Übergang von ihm (Lesen eines Buchstabens a ) zu dem Zustand ( s 1 , , s ' c ) wenn und nur wenn der CFA einen Übergang hat (Lese Buchstaben a ) von s i zu s ' i für jedes i . Ein Zustand ( s 1 , , s c )(s1,,sc)a(s1,,sc)asisii(s1,,sc)akzeptiert genau dann, wenn für jedes i akzeptiert . Natürlich ist der Startzustand der UFA ( s 0 , ... , s 0 ), wobei s 0 der Startzustand der CFA ist.sii(s0,,s0)s0

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 c Eckpunkte codiert sind , das eine Kante zwischen Eckpunkt i und Eckpunkt j hat, wenn wir während des bisherigen Laufs mindestens einmal dieses c ic j hatten .ccijcicj

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 i - ten und j - ten Staaten das gleiche gewesen sein , bis jetzt und im nächsten Schritt würde sie sich unterscheidet, dann im nächsten Schritt des i - ten Zustand sollte einen größeren Index hat.c!iji

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 !
RB
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
Mk=ccwc
Ich hoffe, jetzt ist es klar.
Domotorp