Mehrsprachige DFA-Minimierung

10

Ich interessiere mich für eine leichte Verallgemeinerung von DFA. Wie üblich wir state-Satz haben , finite Alphabet Σ , a Σ * -action definiert auf Q durch δ : Q × Σ Q und Anfangszustand q 0 ; aber statt der üblichen Endapparat, nehmen wir eine Familie ( T i ) i 1 .. n von Teilmengen von Q . Ein mehrsprachiges DFA M ist dann das TupelQΣΣQδ:Q×ΣQq0(Ti)i1..nQM

(Q,Σ,δ,q0,(Ti))

und ist anerkannt von M genau dann , wenn L = { s & egr ; & Sgr; * | q 0 s T i } für einige i 1 .. n . Definieren Sie ( L i ( M ) ) i 1 .. n als die von M erkannte Sprachfamilie, wenn Sie möchten.LΣML={sΣ|q0sTi}i1..n(Li(M))i1..n

Okay, jetzt zu meiner Frage: Bei einer Familie regulärer Sprachen möchte ich das minimale mehrsprachige DFA M wie oben beschrieben so finden, dass L i = L i ( M ) für alle ist i 1 .. n , das heißt, dass | Q | wird über alle diese Maschinen minimiert. Meine Frage ist, gibt es bekannte effiziente Möglichkeiten, dies zu tun, möglicherweise analog zur Standard-DFA-Minimierungstheorie? Gibt es umgekehrt Hinweise darauf, dass dieses Problem schwierig sein könnte?(Li)i1..nMLi=Li(M)i1..n|Q|

gdmclellan
quelle
7
Es scheint mir, dass der Standardalgorithmus auf der Basis der Partitionsverfeinerung, der nur so modifiziert wurde, dass zunächst die anfängliche Menge von Zuständen partitioniert wird, indem sie für jede der gegebenen Teilmengen und nicht für eine einzelne Menge T akzeptiert / nicht akzeptiert werden sofort arbeiten. Warum sollte es nicht? Es teilt nur dann Paare von Zuständen auf, wenn sie aufgeteilt werden müssen, sodass immer noch eine möglichst grobe Verfeinerung der Zustände erzeugt wird. TiT
David Eppstein
1
Der Beweis des Kommentars von @DavidEppstein ist einfach, wenn Sie die Äquivalenzrelation iff x T i y für jedes i definieren , wobei x T i y die Myhill-Nerode-Äquivalenzrelation ist. Sie können dann wie beim Standard-Minimierungsalgorithmus vorgehen. xyxTiyixTiy
Shaull
verstehe nicht ganz. ist die Antwort auf dieses Problem das Finden des minimalen DFA einer Vereinigung von DFAs mit demselben "Setup" mit Ausnahme verschiedener Endzustände, wobei jeder DFA für ? auch die defn der Anerkennung von L = { . . . } scheint nicht genau sinnvoll zu sein, es scheint Strings und Statussätze zu verwechseln. 1..nL={...}
VZN
Die Punkte von DavidEppstein und Shaull sehen überzeugend aus. Ich werde etwas Zeit finden, um das Myhill-Nerode-Theorem durchzugehen, wenn ich Zeit habe, mich davon zu überzeugen, dass der Quotient immer noch den Minimalautomaten liefert. Im Nachhinein scheint es zu offensichtlich.
gdmclellan
@vzn: Ich möchte definitiv nicht die Sprachen des ursprünglichen Automaten zusammenführen. und das kann sich überlappen. Ein mehrsprachiger DFA mit den Sprachen A und B sollte beispielsweise melden können, dass s A , aber s B ist . Wie für die bei der Definition Notation Erkennung einer Sprache verwendet wird , wird die Notation definiert durch die Verlängerung δ auf einen Σ * -action auf Q durch die folgenden Regeln für alle q Q , & sgr; Σ , s Σ * :TiABsAsBδΣQqQ,σΣ,sΣ . qσ=δ(q,σ),q(sσ)=(qs)σ
gdmclellan

Antworten:

14

L=(Li)1in

Details . Der Fall entspricht der Standardkonstruktion und der allgemeine Fall unterscheidet sich im Geist nicht wesentlich. Wenn eine Sprache und ein Wort , sei . Definieren Sie eine Äquivalenzrelation auf indem Sie Since setzen die sind regulär, diese Kongruenz hat einen endlichen Index. Ferner ist es leicht zu sehen , dass jede durch gesättigt und daß für jeden , impliziertn=1Luu1L={vAuvL}A

uvfor each LL, u1L=v1L
LiLiaAuvuava. Bezeichnen wir mit das leere Wort und mit die Klasse eines Wortes . Sei der deterministische Multi-Automat, der wie folgt definiert ist:1[u]uAL=(Q,[1],,(Fi)1in)
  1. Q={[u]uA} ,
  2. [u]a=[ua] ,
  3. Fi={[u]uLi} .

Konstruktionsbedingt genau dann, wenn und damit die Familie . Es bleibt zu beweisen, dass minimal ist. Es ist tatsächlich in einem starken algebraischen Sinne minimal (was impliziert, dass es die minimale Anzahl von Zuständen hat). Sei und sind zwei Multi-Automaten. Ein Morphismus ist eine surjektive Abbildung von auf so dass[1]uFiuLiALLALA=(Q,q,,(Fi)1in)A=(Q,q,,(Fi)1in)f:AAQQ

  1. f(q)=q ,
  2. für gilt , 1inf1(Fi)=Fi
  3. für alle und ist .uAqQf(qu)=f(q)u

Dann für jede zugängliche deterministischen Automaten Mehr Annahme , gibt es eine morphism von auf . Um dies zu beweisen, verifiziert man zuerst, dass wenn , dann . Nun ist definiert durch wobei ein beliebiges Wort ist, so dass . Dann kann man zeigen, dass die drei erforderlichen Eigenschaften erfüllt.L A A L q -u 1 = q -u 2 = q u 1u 2 f f ( q ) = [ u ] u q -u = q fALAALqu1=qu2=qu1u2ff(q)=[u]uqu=qf

Das Ende ist etwas lückenhaft, lassen Sie mich wissen, wenn Sie weitere Details benötigen.

J.-E. Stift
quelle