.
AUTOMATA HINGGA DETERMINISTIK (AHD)
AHD dapat dilengkapi dengan fungsi Next-State berikut:
a) M(q, ^) = q untuk semua q anggota K
b) M(M(q, t), T), untuk semua t anggota VT dan T anggota VT
Dari definisi pertama, terlihat bahwa sebuah AHD tidak bisa mengubah stata tanpa membaca sebuah karakter masukan. Definisi kedua adalah sebuah definisi yang bersifat rekursif, yang menunjukkan di stata mana AHD berada pada saat di mulai di stata q dengan mendapat input berupa string w = tT.
Sebuah string w adalah diterima oleh sebuah F = (K, VT, M, S, Z) jika M(S, W) = p, sedemikian hingga w adalah anggota VT dan p anggota Z.
Atau dengan kata lain, string w diterima oleh AHD jika setelah membaca habis semua karakter dari untai, AHD berada pada sebuah Stata Akhir. Himpunan semua untai w anggota VT yang diterima oleh AHD F dinotasikan sebagai L(F).
AHD pada contoh ini merupakan sebuah AHD yang menerima untai yang terdiri dari simbol 0 dan 1. AHD tersebut dapat dinyatakan sebagai berikut :
F = ( {S, A, B, C}, {0, 1}, M, S, {S} ) dimana fungsi next state M adalah :
M(S, 0) = B M(S, 1) = A
M(A, 0) = C M(A, 1) = S
M(B, 0) = S M(B, 1) = C
M(C, 0) = A M(C, 1) = B
Fungsi stata berikut dari AHD kadang-kadang lebih mudah disajikan dalam bentuk tabel. Untuk contoh di atas tabel yang terbentuk adalah :
| STATA | INPUT |
| 0 1 | |
SA B C | B A C S S C A B |
Contoh dari string yang diterima AHD di atas adalah 110101 dan contoh string yang tidak dapat diterima adalah 11101. Bagan operasi AHD pada kedua untai di atas adalah sebagai berikut :
Penelusuran string 110101 : Penelusuran string 11101 :
M(S, 110101) = M(A, 10101) M(S, 11101) = M(A, 1101)
= M(S, 0101) = M(S, 101)
= M(B, 101) = M(A, 01)
= M(C, 01) = M(C, 1)
= M(A, 1) = M(B, ^)
= M(S, ^) = B (ditolak)
= S (diterima)
Tidak ada komentar:
Posting Komentar