Wielojęzyczna minimalizacja DFA

Jestem zainteresowany niewielkim uogólnieniem DFA. Jak zwykle mamy ustawiony stan , skończony alfabet , działanie zdefiniowane na przez i stan początkowy ; lecz w zwykłym zestawem terminali wziąć rodziny podzbiorów . Wielojęzyczny DFA jest wtedy krotką $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))$

a jest rozpoznawany przez iff dla niektórych . Zdefiniuj aby być rodziną języków rozpoznawanych przez M, jeśli chcesz. $L \subseteq \Sigma^*$ $M$ $L = \{s\in\Sigma^*|q_0s\in T_i\}$ $i\in 1..n$ $(L_i(M))_{i\in 1..n}$

Dobra, teraz moje pytanie: biorąc pod uwagę rodzinę zwykłych języków , chcę znaleźć minimalny wielojęzyczny DFA jak opisano powyżej, tak aby dla wszystkie , to znaczy takie, żejest zminimalizowane w stosunku do wszystkich takich maszyn. Moje pytanie brzmi: czy istnieją znane skuteczne sposoby na zrobienie tego, być może analogiczne do standardowej teorii minimalizacji DFA? I odwrotnie, czy istnieją dowody na to, że ten problem może być trudny? $(L_i)_{i\in 1..n}$ $M$ $L_i = L_i(M)$ $i\in 1..n$ $|Q|$

automata-theory dfa gdmclellan
źródło

Wydaje mi się, że standardowy algorytm oparty na uszczegółowieniu partycji, zmodyfikowany tylko w celu rozpoczęcia od partycjonowania początkowego zestawu stanów według tego, czy akceptują / nie akceptują dla każdego z określonych podzbiorów a nie dla pojedynczego zestawu , powinien po prostu działać natychmiast. Dlaczego by nie miał Dzieli pary stanów tylko wtedy, gdy muszą być one podzielone, więc nadal generuje najgrubsze możliwe udoskonalenie stanów.

T_{i}

$T_i$

T

$T$

David Eppstein,

Dowód komentarza @DavidEppstein jest łatwy, jeśli zdefiniujesz relację równoważności iff dla każdego , gdzie jest relacją równoważności Myhill-Nerode. Następnie możesz postępować zgodnie z tymi samymi liniami, co standardowy algorytm minimalizacji.

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

nie do końca rozumiem. czy odpowiedzią na ten problem jest znalezienie minimalnego DFA unii DFA z tym samym „ustawieniem” oprócz różnych stanów końcowych, każdy DFA dla ? także defn rozpoznawania wydaje się nie mieć sensu dokładnie, wydaje się mieszać ciągi znaków i zestawy stanów.

1.. n

$1..n$

L = {. . .}

$L=\{...\}$

vzn

Uwagi DavidEppsteina i Shaulla wyglądają przekonująco, znajdę trochę czasu, aby przejść przez twierdzenie Myhill-Nerode, kiedy będę miał czas przekonać się, że iloraz nadal daje minimalny automat. Z perspektywy czasu wydaje się to zbyt oczywiste.

gdmclellan

@vzn: zdecydowanie nie chcę łączyć języków oryginalnego automatu; i

T_{i}

$T_i$ może się nakładać. Wielojęzyczny DFA z językami

A

$A$ i

B

$B$ powinien być w stanie na przykład zgłosić to

s \in A

$s\in A$ , ale

s \notin B

$s\notin B$ . Jeśli chodzi o notację używaną przy definiowaniu rozpoznawania języka, notacja jest definiowana przez rozszerzenie

δ

$\delta$ do

Σ^{*}

$\Sigma^*$ -akcja na

Q

$Q$ zgodnie z następującymi zasadami dla wszystkich

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

Odpowiedzi:

Krótka odpowiedź . Biorąc pod uwagę skończoną rodzinę zwykłych języków $\mathcal{L} = (L_i)_{1 \leqslant i \leqslant n}$ , istnieje wyjątkowa minimalna deterministyczna pełna automatyka rozpoznająca tę rodzinę.

Szczegóły . Walizka $n = 1$ odpowiada standardowej konstrukcji, a ogólny przypadek niewiele różni się duchem. Biorąc pod uwagę język $L$ i słowo $u$ , pozwolić $u^{-1}L = \{ v \in A^* \mid uv \in L \}$ . Zdefiniuj relację równoważności $\sim$ na $A^*$ przez ustawienie

u \sim v ⟺ dla każdego 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$ Od czasu

L_{i}

$L_i$ są regularne, ta zgodność ma skończony indeks. Co więcej, łatwo to zauważyć

L_{i}

$L_i$ jest nasycony

\sim

$\sim$ i to dla każdego

a \in A

$a \in A$ ,

u \sim v

$u \sim v$ implikuje

u a \sim v a

$ua \sim va$ . Oznaczmy przez

1

$1$ puste słowo i przez

[u]

$[u]$

\sim

$\sim$ -klasa słowa

u

$u$ . Pozwolić

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

$\mathcal{A}_\mathcal{L} = (Q, [1], \cdot, (F_i)_{1 \leqslant i \leqslant n})$ być deterministycznym automatem zdefiniowanym w następujący sposób:

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

Z założenia $[1] \cdot u \in F_i$ wtedy i tylko wtedy gdy $u \in L_i$ i stąd $\mathcal{A}_\mathcal{L}$ akceptuje rodzinę $\mathcal{L}$ . Pozostaje to udowodnić $\mathcal{A}_\mathcal{L}$ jest minimalny. Jest tak naprawdę minimalny w silnym sensie algebraicznym (co oznacza, że ma minimalną liczbę stanów). Pozwolić $\mathcal{A} = (Q, q_-, \cdot, (F_i)_{1 \leqslant i \leqslant n})$ i $\mathcal{A}' = (Q', q'_-, \cdot, (F'_i)_{1 \leqslant i \leqslant n})$ być dwiema automatami. Morfizm $f: \mathcal{A} \to \mathcal{A}'$ jest zaskakującą mapą z $Q$ na $Q'$ takie, że

$f(q_-) = q'_-$ ,
dla $1 \leqslant i \leqslant n$ , $f^{-1}(F'_i) = F_i$ ,
dla wszystkich $u \in A^*$ i $q \in Q$ , $f(q \cdot u) = f(q) \cdot u$ .

Następnie dla każdego dostępnego deterministycznego automatu $\mathcal{A}$ przyjmowanie $\mathcal{L}$ , istnieje morfizm z $\mathcal{A}$ na $\mathcal{A}_\mathcal{L}$ . Aby to udowodnić, najpierw sprawdza się, czy $q_- \cdot u_1 = q_- \cdot u_2 = q$ , następnie $u_1 \sim u_2$ . Teraz $f$ jest zdefiniowany przez $f(q) = [u]$ gdzie $u$ to dowolne słowo, które $q_- \cdot u = q$ . Następnie można to pokazać $f$ spełnia trzy wymagane właściwości.

Koniec jest nieco szkicowy, daj mi znać, jeśli potrzebujesz więcej szczegółów.

J.-E. Kołek
źródło