Mehrsprachige DFA-Minimierung

Ich interessiere mich für eine leichte Verallgemeinerung von DFA. Wie üblich wir state-Satz haben , finite Alphabet , a -action definiert auf durch und Anfangszustand ; aber statt der üblichen Endapparat, nehmen wir eine Familie von Teilmengen von . Ein mehrsprachiges DFA ist dann das Tupel $Q$ $\Sigma$ $\Sigma^*$ $Q$ $\delta : Q\times\Sigma\rightarrow Q$ $q_0$ $(T_i)_{i\in 1..n}$ $Q$ $M$

$(Q, \Sigma, \delta, q_0, (T_i))$

und ist anerkannt von genau dann , wenn für einige . Definieren Sie als die von M erkannte Sprachfamilie, wenn Sie möchten. $L \subseteq \Sigma^*$ $M$ $L = \{s\in\Sigma^*|q_0s\in T_i\}$ $i\in 1..n$ $(L_i(M))_{i\in 1..n}$

Okay, jetzt zu meiner Frage: Bei einer Familie regulärer Sprachen möchte ich das minimale mehrsprachige DFA wie oben beschrieben so finden, dass für alle ist , das heißt, dass 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? $(L_i)_{i\in 1..n}$ $M$ $L_i = L_i(M)$ $i\in 1..n$ $|Q|$

automata-theory dfa gdmclellan
quelle

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

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.

T_{i}

$T_i$

T

$T$

David Eppstein

Der Beweis des Kommentars von @DavidEppstein ist einfach, wenn Sie die Äquivalenzrelation

iff

für jedes

, wobei

die Myhill-Nerode-Äquivalenzrelation ist. Sie können dann wie beim Standard-Minimierungsalgorithmus vorgehen.

x \sim y

$x\sim y$

x \sim_{T_{i}} y

$x\sim_{T_i}y$

i

$i$

x \sim_{T_{i}} y

$x\sim_{T_i} y$

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

scheint nicht genau sinnvoll zu sein, es scheint Strings und Statussätze zu verwechseln.

1.. n

$1..n$

L = {. . .}

$L=\{...\}$

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

und

sollte beispielsweise melden können, dass

, aber

. 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

durch die folgenden Regeln für alle

T_{i}

$T_i$

A

$A$

B

$B$

s \in A

$s\in A$

s \notin B

$s\notin B$

δ

$\delta$

Σ^{*}

$\Sigma^*$

Q

$Q$

q \in Q, σ \in Σ, s \in Σ^{*}

$q\in Q, \sigma\in\Sigma, s\in\Sigma^*$

q σ = δ (q, σ), q (s σ) = (q s) σ

$q\sigma = \delta(q, \sigma), q(s\sigma) = (qs)\sigma$

gdmclellan

$\mathcal{L} = (L_i)_{1 \leqslant i \leqslant n}$

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 , impliziert $n = 1$ $L$ $u$ $u^{-1}L = \{ v \in A^* \mid uv \in L \}$ $\sim$ $A^*$

u \sim v ⟺ for each L \in L, u^{- 1} L = v^{- 1} L

$u \sim v \iff \text{for each }L \in \mathcal{L},\ u^{-1}L = v^{-1}L$

L_{i}

$L_i$

L_{i}

$L_i$

\sim

$\sim$

a \in A

$a \in A$

u \sim v

$u \sim v$

u a \sim v a

$ua \sim va$ . Bezeichnen wir mit das leere Wort und mit die Klasse eines Wortes . Sei der deterministische Multi-Automat, der wie folgt definiert ist:

1

$1$

[u]

$[u]$

\sim

$\sim$

u

$u$

A_{L} = (Q, [1], \cdot, (F_{i})_{1 ⩽ i ⩽ n})

$\mathcal{A}_\mathcal{L} = (Q, [1], \cdot, (F_i)_{1 \leqslant i \leqslant n})$

$Q = \{ [u] \mid u \in A^*\}$ ,
$[u] \cdot a = [ua]$ ,
$F_i = \{ [u] \mid u \in L_i\}$ .

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] \cdot u \in F_i$ $u \in L_i$ $\mathcal{A}_\mathcal{L}$ $\mathcal{L}$ $\mathcal{A}_\mathcal{L}$ $\mathcal{A} = (Q, q_-, \cdot, (F_i)_{1 \leqslant i \leqslant n})$ $\mathcal{A}' = (Q', q'_-, \cdot, (F'_i)_{1 \leqslant i \leqslant n})$ $f: \mathcal{A} \to \mathcal{A}'$ $Q$ $Q'$

$f(q_-) = q'_-$ ,
für gilt , $1 \leqslant i \leqslant n$ $f^{-1}(F'_i) = F_i$
für alle und ist . $u \in A^*$ $q \in Q$ $f(q \cdot u) = f(q) \cdot 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. $\mathcal{A}$ $\mathcal{L}$ $\mathcal{A}$ $\mathcal{A}_\mathcal{L}$ $q_- \cdot u_1 = q_- \cdot u_2 = q$ $u_1 \sim u_2$ $f$ $f(q) = [u]$ $u$ $q_- \cdot u = q$ $f$

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

J.-E. Stift
quelle

Mehrsprachige DFA-Minimierung

Antworten: