Perbedaan antara bahasa yang diterima oleh dua DFA dengan negara bagian / negara penerima yang berbeda?

Baru-baru ini, saya mengajukan pertanyaan tentang Matematika SE. Belum ada tanggapan. Pertanyaan ini terkait dengan pertanyaan itu, tetapi rincian teknis lebih ke arah ilmu komputer.

Diberikan dua DFA dan mana set status, alfabet input, dan fungsi transisi dari dan adalah sama, keadaan awal dan kondisi akhir (menerima) bisa berbeda. Biarkan dan menjadi bahasa yang diterima oleh dan , masing-masing. $A = (Q, \Sigma, \delta, q_1, F_1)$ $B = (Q, \Sigma, \delta, q_2, F_2)$ $A$ $B$ $L_1$ $L_2$ $A$ $B$

Ada empat kasus:

$q_1 = q_2$ dan . $F_1 = F_2$
$q_1 \neq q_2$ dan . $F_1 = F_2$
$q_1 = q_2$ dan . $F_1 \neq F_2$
$q_1 \neq q_2$ dan . $F_1 \neq F_2$

Pertanyaanku adalah

Apa perbedaan antara dan dalam kasus 2, 3 dan 4? $L_1$ $L_2$

Saya punya pertanyaan yang lebih spesifik di sepanjang baris ini,

Transisi mono automaton adalah himpunan semua fungsi pada himpunan status yang diinduksi oleh string input. Lihat halaman untuk detail lebih lanjut. Transoid monoid dapat dianggap sebagai monoid yang bekerja pada himpunan negara. Lihat halaman Wiki ini untuk lebih jelasnya.

Dalam banyak literatur, otomat disebut sangat terhubung ketika aksi monoid transitif, yaitu selalu ada setidaknya satu transisi (input string) dari satu keadaan ke keadaan lain.

Jika dan terhubung automata kuat, apa perbedaan antara dan dalam kasus 2, 3 dan 4 di atas? $A$ $B$ $L_1$ $L_2$

Adakah literatur yang membahas masalah ini secara terperinci?

Saya telah mencari banyak buku dan artikel dan sejauh ini tidak menemukan apa pun yang bermanfaat. Saya yakin saya belum memiliki kata-kata kunci yang tepat. Karena itu saya mencari bantuan. Setiap petunjuk / referensi akan sangat dihargai.

formal-languages reference-request finite-automata scaaahu
sumber

Apa yang Anda maksud dengan "apa perbedaannya"? Anda ingin tahu apakah

dan

dapat / harus berbeda dalam kasus 2,3,4?

L_{1}

$L_1$

L_{2}

$L_2$

Hendrik Jan

@ HendrikJan Jika Anda membaca jawaban yang diberikan Shaull di bawah ini, Anda akan memahami

dan

dapat berbeda. (Dia menggunakan

dan

). Saya tidak tahu apakah mereka harus berbeda. Itu bagian dari pertanyaan saya. Saya bertanya "apa perbedaannya?". Saya tidak menyiratkan mereka harus berbeda.

L_{1}

$L_1$

L_{2}

$L_2$

L (A)

$L(A)$

L (B)

$L(B)$

scaaahu

Jawaban:

Karena sangat terhubung, maka jika , ada kata sedemikian rupa sehingga dan . $A,B$ $q_1\neq q_2$ $p_1,p_2$ $\delta(q_1,p_1)=q_2$ $\delta(q_2,p_2)=q_1$

Pertimbangkan kasus 2, lalu iff , dan iff . Jadi, Anda dapat menambahkan awalan untuk beralih antar bahasa. $w\in L(A)$ $p_2w\in L(B)$ $x\in L(B)$ $p_1 x\in L(A)$

Pertimbangkan kasus 3, sekali lagi - dengan konektivitas yang kuat paling banyak kata sedemikian rupa sehingga untuk setiap Anda memiliki , dan demikian pula untuk arah lainnya (dari ke ). $|F_1|$ $s_1,...,s_k$ $q_i\in F_1$ $\delta(q_i,s_i)\in F_2$ $B$ $A$

Dengan demikian, Anda dapat membuat sufiks untuk beralih antar bahasa.

$w\in L(B)$ $p_1 w s_i$ $L(A)$ $s_i$

$C$ $q_1$ $q_2$ $L(B)=L(C)\cdot L(A)$

$L(B)=\bigcup_{q\in F_1}L(A_q)\cdot L(E_q)$ $A_q$ $A$ $F=\{q\}$ $E_q$ $q$ $F_2$

Untuk case 4 Anda dapat menggabungkan keduanya.

Anda mungkin khawatir bahwa ini bukan jawaban yang nyata, tetapi lebih merupakan karakterisasi properti yang menggunakan kata-kata daripada negara, tetapi ini adalah jawaban yang khas dalam bidang ini (mirip dengan teorema Myhill-Nerode).

Shaull
sumber

p_{1}

$p_1$

p_{1}

$p_1$

δ (q_{1}, p_{1}) = q_{2}

$\delta(q_1,p_1) = q_2$

L (A)

$L(A)$

L (B)

$L(B)$

Saya mengedit jawabannya dengan beberapa informasi yang lebih tepat.

Shaull

C

$C$

Harap perhatikan suntingan tambahan di pos.

Shaull

Ide bagus. Anda mengambil satu kondisi terakhir pada suatu waktu kemudian mengambil serikat. Semoga interpretasi saya benar.

scaaahu