Automaton lengkap

Dalam takrif asas automaton terhingga, tidak semestinya setiap keadaan mempunyai peralihan bagi semua simbol. Automaton lengkap (total automaton) ialah automaton yang mempunyai peralihan yang ditakrifkan dari semua keadaan bagi semua simbol abjad input.

Cara membina automaton lengkap

Katakan kita mempunyai automaton A = ⟨Q, Σ, δ, q₀, F⟩ berikut:

Dalam rajah ini tiada peralihan dari keadaan q₀ bagi huruf “b”. Jika situasi ini berlaku, kita katakan bahawa automaton tidak menerima rentetan input itu. Namun, dari sudut formalisasi, kurang sesuai jika fungsi peralihan δ tidak ditakrifkan bagi sesetengah nilai; di sini, misalnya, δ(q₀, b) tidak ditakrifkan.

Masalah ini mudah diselesaikan dengan membina automaton setara yang mempunyai satu keadaan tambahan. Semua peralihan yang “hilang” menuju ke keadaan ini, keadaan ini bukan keadaan akhir, dan semua input seterusnya berulang dalam keadaan ini. Automaton ini dipanggil automaton lengkap. Automaton setara yang telah diubah suai boleh kelihatan seperti berikut:

Kita telah menambahkan keadaan q_fail (fail = gagal). Dari keadaan lain, kita melukis peralihan ke keadaan ini jika dan hanya jika peralihan itu tidak wujud sebelumnya. Keadaan ini bukan keadaan akhir dan mempunyai gelung bagi semua input seterusnya. Jadi, dalam situasi apabila automaton sebelum ini menemui peralihan yang hilang, automaton ini tiada peralihan yang hilang dan sebaliknya sampai ke keadaan q_fail.

Oleh itu, tanpa kehilangan keitlakan, kita sentiasa boleh menganggap bahawa automaton mempunyai peralihan yang ditakrifkan bagi semua gabungan keadaan dan aksara abjad.

Takrif

Bagi automaton lengkap A = ⟨Q, Σ, δ, q₀, F⟩,

$$\mathrm{\forall }q\in Q\mathrm{\forall }a\in \mathrm{\Sigma }\mathrm{\exists }r\in Q:\delta (q,a)=r.$$

Sumber

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools