Minimalisasi DFA multi-bahasa

Saya tertarik dengan sedikit generalisasi DFA. Seperti biasa kita memiliki set-negara $Q$ , alfabet terbatas $\Sigma$ , sebuah aksi $\Sigma^*$ didefinisikan pada $Q$ oleh $\delta : Q\times\Sigma\rightarrow Q$ , dan kondisi awal $q_0$ ; tapi bukannya biasa set terminal, kita mengambil keluarga $(T_i)_{i\in 1..n}$ himpunan bagian dari . DFA Multi-bahasa $Q$ $M$ adalah tuple

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

dan $L \subseteq \Sigma^*$ dikenali oleh $M$ iff $L = \{s\in\Sigma^*|q_0s\in T_i\}$ untuk beberapa $i\in 1..n$ . Tentukan $(L_i(M))_{i\in 1..n}$ untuk menjadi keluarga bahasa yang dikenali oleh M, jika Anda mau.

Oke, sekarang untuk pertanyaan saya: diberikan sekumpulan bahasa reguler , saya ingin mencari DFA Multi-bahasa minimal seperti yang dijelaskan di atas sehingga untuk semua , yaitu, sedemikian rupa sehingga diminimalkan pada semua mesin seperti itu. Pertanyaan saya adalah, adakah cara efisien yang diketahui melakukan hal ini, mungkin analog dengan teori minimalisasi DFA standar? Sebaliknya, adakah bukti bahwa masalah ini mungkin sulit? $(L_i)_{i\in 1..n}$ $M$ $L_i = L_i(M)$ $i\in 1..n$ $|Q|$

automata-theory dfa gdmclellan
sumber

Sepertinya saya bahwa algoritma berbasis penyempurnaan partisi standar, dimodifikasi hanya untuk memulai dengan mempartisi set awal negara dengan apakah mereka menerima / tidak menerima untuk masing-masing himpunan bagian yang diberikan

daripada untuk satu set

, harus hanya segera bekerja. Kenapa tidak? Itu hanya membagi pasangan negara ketika mereka harus dibagi, sehingga masih menghasilkan penyempurnaan yang paling kasar dari negara.

T_{i}

$T_i$

T

$T$

David Eppstein

Bukti komentar oleh @DavidEppstein mudah jika Anda mendefinisikan relasi ekivalensi

iff

untuk setiap

, di mana

adalah relasi ekivalensi Myhill-Nerode. Anda kemudian dapat melanjutkan sepanjang garis yang sama dengan algoritma minimisasi standar.

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

tidak cukup mengerti. Apakah jawaban untuk masalah ini adalah menemukan DFA minimal dari gabungan DFA dengan "pengaturan" yang sama kecuali status akhir yang berbeda, masing-masing DFA untuk

? juga definisi pengakuan

tampaknya tidak masuk akal persis, tampaknya mencampur string dan set negara.

1.. n

$1..n$

L = {. . .}

$L=\{...\}$

vzn

Poin yang dibuat oleh David Epstein dan Shaull terlihat menarik, saya akan menemukan waktu untuk membahas teorema Myhill-Nerode ketika saya punya waktu untuk meyakinkan diri sendiri bahwa hasil bagi masih menghasilkan otomat minimal. Kalau dipikir-pikir, sepertinya sudah terlalu jelas.

gdmclellan

@ vzn: pasti tidak ingin menyatukan bahasa automaton yang asli; dan

mungkin tumpang tindih. Sebuah multi-bahasa DFA dengan bahasa

dan

harus dapat laporan, misalnya, bahwa

, tapi

. Adapun notasi yang digunakan dalam mendefinisikan pengakuan bahasa, notasi didefinisikan dengan memperluas

-aksi pada

dengan aturan berikut untuk semua

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

Jawaban:

Jawaban singkat . Diberikan keluarga berhingga dari bahasa-bahasa reguler , ada multi-automaton lengkap deterministik minimal unik yang mengenali keluarga ini. $\mathcal{L} = (L_i)_{1 \leqslant i \leqslant n}$

Detail . Kasus sesuai dengan konstruksi standar dan kasus umum tidak jauh berbeda dalam semangat. Diberi bahasa dan kata , misalkan . Tentukan relasi ekivalensi pada dengan mengatur $n = 1$ $L$ $u$ $u^{-1}L = \{ v \in A^* \mid uv \in L \}$ $\sim$ $A^*$ Karena teratur, kongruensi ini memiliki indeks hingga. Selanjutnya, mudah untuk melihat bahwa setiap jenuh oleh dan bahwa untuk setiap , menyiratkan . Mari kita dilambangkan dengan kata kosong dan oleh yang -class dari kata

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$

1

$1$

[u]

$[u]$

\sim

$\sim$

u

$u$ . Misalkan

menjadi deterministik multi-otomat yang didefinisikan sebagai berikut:

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\}$

Dengan konstruksi, jika dan hanya jika dan karenanya menerima keluarga . Tetap membuktikan bahwa minimal. Ini sebenarnya minimal dalam arti aljabar yang kuat (yang menyiratkan bahwa ia memiliki jumlah minimum negara). Misalkan dan $[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})$ menjadi dua multi-automata. Morfisme adalah peta perkiraan dari ke sedemikian rupa $\mathcal{A}' = (Q', q'_-, \cdot, (F'_i)_{1 \leqslant i \leqslant n})$ $f: \mathcal{A} \to \mathcal{A}'$ $Q$ $Q'$

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

Kemudian untuk setiap diakses deterministik multi-otomat menerima , ada morphism dari ke . Untuk membuktikan ini, yang pertama memverifikasi bahwa jika , maka . Sekarang didefinisikan oleh mana adalah setiap kata sedemikian rupa sehingga $\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$ . Maka kita dapat menunjukkan bahwa memenuhi tiga properti yang diperlukan. $q_- \cdot u = q$ $f$

Akhirnya agak samar, beri tahu saya jika Anda membutuhkan detail lebih lanjut.

J.-E. Pin
sumber