TEORI BAHASA DAN OTOMATA [TBO]
NFA DENGAN -MOVE Terdapat jenis otomata baru yang disebut NFA dengan
-move ( disini bisa dianggap sebagai empty). Pada NFA dengan -move (transisi ), diperbolehkan merubah state tanpa membaca input. Disebut dengan transisi karena tidak bergantung pada suatu input ketika melakukan transisi
Gambar 1 Mesin NFA dengan -move
Penjelasan Gambar 1 Dari q0 tanpa membaca input dapat berpindah ke q1
Dari q1 tanpa membaca input dapat berpindah ke q2 Dari q4 tanpa membaca input dapat berpindah ke q1 Salah satu kegunaan dari transisi ini adalah
memudahkan dalam mengkombinasikan finite state automata.
-Closure Untuk NFA -Move -closure adalah himpunan state-state yang dapat
dicapai dari suatu state tanpa membaca input. Misal: -closure (q0)=himpunan-himpunan statestate yang dapat dicapai dari state q0 tanpa membaca input. Maka dengan melihat gambar 1 -closure (q0)=q0,q1,q2, artinya dari state q0 tanpa membaca input dapat mencapai state q0, q1, dan q2.
Perhatikan Gambar 1 -closure untuk state lainnya bisa dilihat sebagai
berikut: -closure (q1) = q1,q2 -closure (q2) = q2 -closure (q3) = q3 -closure (q4) = q1,q2,q4
Gambar 2 Mesin NFA dengan -move
Perhatikan Gambar 2 Dari gambar 2 diketahui -closure untuk setiap state
adalah: -closure (q0) = q0,q1,q3 -closure (q1) = q1,q3 -closure (q2) = q2,q4 -closure (q3) = q3 -closure (q4) = q4 Perhatikan: Pada suatu state yang tidak memiliki transisi , maka -closurenya adalah state itu sendiri.
Ekivalensi NFA -move ke NFA tanpa -move Dari sebuah NFA dengan -move dapat diperoleh NFA
tanpa -move yang ekivalen. (Dalam materi ini sebutan NFA saja mengacu pada NFA tanpa -move).
Contoh: Bila terdapat NFA -move, seperti pada gambar 3. Gambar 4 adalah NFA tanpa -move yang ekivalen dengan NFA -move pada gambar 3.
Perhatikan Gambar 3 dan 4 Gambar 3
Gambar 4
Penjelasan..
Perhatikan bahwa NFA -move semula menerima
bahasa yang membuat string ’b’, selanjutnya bisa dilihat bahwa NFA tanpa -move pada gambar 4 juga mampu menerima bahasa yang memuat string ‘b’. Maka dapat dinyatakan bahwa kedua mesin tersebut ekivalen, karena mampu menerima bahasa yang sama. Tentu saja bila gambarnya tidak sesederhana itu, perlu dilakukan beberapa tahapan untuk mendapatkan perubahan dari NFA -move ke NFA tanpa -move.
Tahapan Perubahan 1.
Buat table transisi Non-deterministic Finite Automata dengan -move semula 2. Tentukan -closure untuk setiap state 3. Carilah setiap fungsi transisi hasil perubahan dari NFA -move ke NFA tanpa -move (sebut saja sebagai ’), dimana ’ didapatkan dengan rumus: ’(state, input) = -closure ((-closure(state), input))
Tahapan Perubahan Lanjt.. 4. Berdasarkan hasil no.(3), buatlah table transisi dan diagram transisi dari NFA tanpa -move yang ekivalen dengan NFA -move tersebut. 5. Menentukan state-state akhir untuk NFA tanpa -move tersebut, yaitu state-state akhir semula ditambah dengan state-state yang -closure –nya menuju ke salah satu dari state akhir semula. Dalam bahasa formalnya: F’ = F q(-closure (q) F) Misal: bila semula F= q0, q3, _closure q1, = q0, q2, maka F’=q0, q1, q3.
Tahapan 1 Tabel transisi dari NFA -move pada gambar 3 δ q0 q1 q2
a
b
{q2}
{q3}
q3
Tahapan 2 Dari NFA -move pada gambar 3 tentukan -closure
untuk setiap state (-closure bisa juga disingkat sebagai -cl): -cl (q0) = q0,q1 -cl (q1) = q1 -cl (q2) = q2 -cl (q3) = q3
Tahapan 3 Cari ’ dengan memanfaatkan table transisi dan -closure
yang diperoleh sebelumnya, sebagai berikut: ’(q0,a), ’(q0,b), ’(q1,a), ’(q1,b), ’(q2,a), ’(q2,b), ’(q3,a), dan ’(q3,b) Perhatikan penjabaran pada slide selanjutnya !
Tahapan 3 Lanjt.. ’(q0,a) = -closure ((-closure(q0),a)) = -closure ((q0,q1,a)) = -closure (q2) = q2
’(q0,b)
= -closure ((-closure(q0),b)) = -closure ((q0,q1,b)) = -closure (q3) = q3
Tahapan 3 Lanjt… ’(q1,a)
= -closure ((-closure(q1),a)) = -closure ((q1,a)) = -closure (q2) = q2
’(q1,b)
= -closure ((-closure(q1),b)) = -closure ((q1,b)) = -closure (q3) = q3
Tahapan 3 Lanjt…. ’(q2,a)
= -closure ((-closure(q2),a)) = -closure ((q2,a)) = -closure () =
’(q2,b)
= -closure ((-closure(q2),b)) = -closure ((q2,b)) = -closure () =
Tahapan 3 Lanjt….. ’(q3,a)
= -closure ((-closure(q3),a)) = -closure ((q3,a)) = -closure () =
’(q3,b)
= -closure ((-closure(q3),b)) = -closure ((q3,b)) = -closure () =
Tahapan 4 Bisa dilihat table transisi dan diagram untuk NFA tanpa -
move dari hasil tahapan sebelumnya : δ
a
b
q0 q1 q2 q3
{q2} {q2}
{q3} {q3}
Tahapan 5 Akhirnya ditentukan himpunan state akhir untuk NFA
tanpa -move ini. Himpunan state akhir semula adalah q3. Karena tidak ada state lain yang -closure-nya memuat q3, maka himpunan state akhir sekarang tetap q3.
Perhatikan: karena disini mesin NFA maka state
tidak perlu dimunculkan dalam diagram transisi.
PENGGABUNGAN 2 FSA Pada 2 mesin FSA dapat dilakukan penggabungan, disebut
union serta konkatenasi. Misalkan terdapat dua mesin NFA, M1 dan M2
Gambar 5: M1
Gambar 6: M2
OPERASI UNION Diketahui L(M1) adalah bahasa yang diterima oleh M1 dan
L(M2) adalah bahasa yang diterima oleh M2. Dilakukan operasi union berikut: L(M3) = L(M1) L(M2) atau dengan notasi lain: L(M3) = L(M1) + L(M2) Bisa dibuat mesin M3 yang menerima bahasa L(M3) dengan cara: Tambahkan state awal untuk M3, hubungkan dengan state awal M1 dan state awal M2 menggunakan transisi Tambahkan state akhir untuk M3, hubungkan dengan statestate akhir M1 dan state-state akhir M2 menggunakan transisi
HASIL UNION qs dan qf adalah state awal dan state final mesin baru
FSA
OPERASI KONKATENASI Diketahui L(M1) adalah bahasa yang diterima oleh M1
dan L(M2) adalah bahasa yang diterima oleh M2. Dilakukan operasi konkatenasi berikut: L(M4) = L(M1).L(M2) Bisa dibuat mesin M4 yang menerima bahasa L(M4) dengan cara: State awal M1 menjadi state awal M4 State-state akhir M2 menjadi state akhir M4 Hubungan state-state akhir M1 dengan state awal M2 menggunakan transisi .
HASIL KONKATENASI qA0 dan qB1 adalah state awal dan state final mesin baru
FSA
ALUR PENGEMBANGAN FSA (1) FSA hasil operasi gabungan atau konkatenasi adalah sebuah
NFA -move. Untuk selanjutnya harus diubah menjadi NFA tanpa -move.
ALUR PENGEMBANGAN FSA (2)
