Minimalkan Deterministic Finite Automata tanpa status penerimaan

Saya memiliki otomat terbatas tanpa status akhir / penerimaan, jadi F kosong. Bagaimana cara menguranginya?

Saya mendapatkan ini pada tes dan saya tidak tahu bagaimana mendekati masalah karena otomat tidak memiliki keadaan menerima. Apakah satu keadaan awal dengan semua transisi itu sendiri adalah jawaban yang benar?

Tebakan Anda benar dan Anda dapat melihatnya sedikit lebih formal sebagai berikut. Membiarkan$\mathcal{A} = (Q, A, \cdot, q_0, F)$menjadi DFA. Kesesuaian Nerode$\sim$ di $Q$ didefinisikan sebagai berikut:

$$p \sim q \text{ if and only if, for every word $u \in A^*$, }\ p \cdot u \in F \iff q \cdot u \in F$$ Himpunan status otomat minimal $\mathcal{A}$ adalah $Q/{\sim}$. Sekarang jika$F$ adalah set kosong, semua status $Q$ adalah $\sim$-Seivalen dan dengan demikian $Q/{\sim}$ hanya memiliki satu elemen, katakanlah $Q/{\sim} = \{1\}$. Anda tidak punya pilihan untuk transisi dan karenanya$1 \cdot a = 1$ untuk setiap huruf $a$. Akhirnya$1$ adalah keadaan awal, tetapi tidak ada keadaan akhir.

Otomat terbatas tanpa status akhir menunjukkan bahasa L = $\emptyset$. Untuk meminimalkan DFA, kami meminimalkan jumlah status dan bahasa yang dilambangkan harus sama. Menurut definisi DFA kita harus memiliki keadaan awal$q_0$ begitu $| Q | \geq 1$ dan seperti yang Anda katakan, kita perlu memasukkan fungsi transisi dengan semua transisi ke $q_0$ (Karena menciptakan negara mati adalah kontraproduktif).