Otomaton lengkap

Dalam definisi dasar otomaton hingga, tidak harus ada transisi dari setiap state untuk setiap simbol. Otomaton lengkap adalah otomaton yang memiliki transisi terdefinisi dari semua state untuk semua simbol alfabet input.

Cara mengonstruksi otomaton lengkap

Misalkan ada otomaton A = ⟨Q, Σ, δ, q₀, F⟩ berikut:

Di sini tidak ada transisi dari state q₀ untuk huruf “b”. Jika situasi seperti itu terjadi, kita katakan bahwa otomaton tidak menerima string input tersebut. Namun, dari sudut pandang formalisasi, kurang baik jika fungsi transisi δ tidak terdefinisi untuk beberapa nilai; di sini, misalnya, fungsi tersebut tidak terdefinisi untuk δ(q₀, b).

Masalah ini mudah diatasi dengan mengonstruksi otomaton ekuivalen yang memiliki satu state tambahan. Semua transisi yang “hilang” diarahkan ke state ini, state ini bukan state akhir, dan semua input berikutnya berputar di state ini. Otomaton seperti ini disebut otomaton lengkap. Otomaton ekuivalen hasil modifikasinya dapat terlihat seperti ini:

Kita menambahkan state q_fail. Dari state lain, kita membuat transisi ke state ini hanya jika sebelumnya transisi tersebut tidak ada. State ini bukan state akhir dan berputar pada dirinya sendiri untuk semua input berikutnya. Jadi, jika pada otomaton sebelumnya kita menemui transisi yang tidak ada, di sini tidak ada transisi yang hilang, dan otomaton akan sampai di state q_fail.

Karena itu, tanpa mengurangi keumuman, kita selalu dapat mengasumsikan bahwa otomaton memiliki transisi terdefinisi untuk semua kombinasi state dan simbol alfabet.

Definisi

Untuk otomaton lengkap A = ⟨Q, Σ, δ, q₀, F⟩ berlaku

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