TUGAS 1
TEORI BAHASA OTOMATA (AUTOMATA)
Waktu terus berlalu kesibukanpun tak pernah
berhenti, berangkat pagi pulang sore, berangkat sore pulang malam, saya jadi
bingung sendiri gimana atur waktunya ya?
mau kerja tugas kantoran atau mau kerja tugas kuliah? Hehehe,... jangan
bingung mas, kalau kerja tugas kuliah sama aku aja, aku janji pasti bereslah
!!!! hahaha,.. kata bang google. Oh iya, ya,... sory saya lupa kalau gitu enak
dong kan ada yag bantu,.....hehehe.
Ok, tugas kali ini adalah :
- Contoh penggunaan mesin Turing
- Contoh-contoh otomata ( Automata)
Sebelum kita membahas soal nomor 1 dan 2 diatas perlu kita memahami dulu
tentang apa sih mesin turing itu dan bagaimana kerjanya, untuk itu maka mari
kita perhatikan ilustrasi berikut ini :
MESIN TURING
Ilustrasi
TM sebagai sebuah ‘mesin’:
Di sebelah kanan kalimat terdapat tak hingga simbol hampa.
Head : membaca dan menulisi sel pita TM, bisa
bergerak ke kiri atau ke kanan
FSC : otak dari TM,
diimplementasikan dari algoritma pengenalan kalimat.
Ilustrasi TM sebagai sebuah
graf berarah :
1. Sebagaimana graf, TM terdiri
dari beberapa node dan beberapa edge. Dari satu node mungkin terdapat
satu atau lebih edge yang menuju node lainnya atau dirinya sendiri.
2. Sebuah node menyatakan
sebuah stata (state). Dua stata penting adalah stata awal S (start) dan stata penerima H (halt).
Sesaat sebelum proses pengenalan sebuah kalimat, TM berada pada stata S. Jika
kalimat tersebut dikenali maka, setelah selesai membaca kalimat tersebut, TM akan berhenti pada stata H.
3. Sebuah edge mempunyai
‘bobot’ yang dinotasikan sebagai triple : (a, b, d). a adalah karakter acuan
bagi karakter dalam sel pita TM yang sedang dibaca head. Jika yang dibaca head
adalah karakter a maka a akan di-overwrite
dengan karakter b dan head akan berpindah satu sel ke arah d (kanan atau
kiri).
4. Kondisi crash akan terjadi jika ditemui keadaan sebagai berikut :
TM sedang berada pada stata
i. Jika TM sedang
membaca simbol ax ¹ a1 ¹ a2 ¹ … ¹ an maka
TM
tidak mungkin beranjak dari stata i. Jadi
pada
kasus ini penelusuran (tracing) TM
ber-
akhir
pada stata i.
Contoh :
Rancanglah sebuah mesin turing pengenal bahasa L =
{a
b
| n ³ 0).
![](file:///C:%5CDOCUME%7E1%5CPKALEK%7E1%5CLOCALS%7E1%5CTemp%5Cmsohtmlclip1%5C01%5Cclip_image002.gif)
![](file:///C:%5CDOCUME%7E1%5CPKALEK%7E1%5CLOCALS%7E1%5CTemp%5Cmsohtmlclip1%5C01%5Cclip_image002.gif)
Jawab :
L tersebut terdiri dari 2 kelompok kalimat yaitu e dan non-e. Kelompok non-e adalah : ab, aabb, aaabbb, dan seterusnya.
Untuk dapat menerima kalimat e TM harus mempunyai edge
dari S ke H dengan bobot (e ,e , R). TM menerima kalimat-kalimat : ab,
aabb, aaabbb, dan seterusnya, dengan algoritma sebagai berikut :
1. Mulai dari S, head membaca
simbol a.
2. Head membaca simbol a.
Tandai simbol a yang sudah dibaca tersebut, head bergerak ke kanan mencari
simbol b pasangannya.
3. Head membaca simbol b.
Tandai simbol b yang sudah dibaca tersebut, head bergerak ke kiri mencari
simbol a baru yang belum dibaca/ditandai.
4. Ulangi langkah 2 dan 3.
5. Head sampai ke H hanya jika
semua simbol a dan simbol b dalam kalimat a
b
selesai dibaca.
![](file:///C:%5CDOCUME%7E1%5CPKALEK%7E1%5CLOCALS%7E1%5CTemp%5Cmsohtmlclip1%5C01%5Cclip_image002.gif)
![](file:///C:%5CDOCUME%7E1%5CPKALEK%7E1%5CLOCALS%7E1%5CTemp%5Cmsohtmlclip1%5C01%5Cclip_image002.gif)
Algoritma di atas lebih diperinci lagi sebagai
berikut :
1. Mulai dari S, head membaca
simbol a.
2. Overwrite a tersebut dengan suatu simbol (misalkan A) untuk menandakan bahwa a
tersebut sudah dibaca. Selanjutnya head harus bergerak ke kanan untuk mencari sebuah b sebagai pasangan a yang sudah dibaca
tersebut.
i)
Jika yang ditemukan adalah
simbol a maka a tersebut harus dilewati (tidak boleh dioverwrite), dengan kata lain a dioverwrite dengan a juga
dan head bergerak ke kanan.
ii) Jika TM pernah membaca
simbol b ada kemungkinan ditemukan simbol B. Simbol B tersebut harus dilewati (tidak boleh dioverwrite), artinya B diover-write dengan B juga dan head bergerak ke kanan.
3. Head membaca simbol b, maka
b tersebut harus dioverwrite dengan simbol lain (misalnya B) untuk menandakan
bahwa b tersebut (sebagai pasangan dari a) telah dibaca, dan head bergerak ke kiri untuk mencari simbol A.
i)
Jika ditemukan B maka B tersebut harus dilewati (tidak boleh dioverwrite), dengan kata lain B dioverwrite dengan B juga
dan head bergerak ke kiri.
ii) Jika ditemukan a maka a
tersebut harus dilewati (tidak boleh
dioverwrite), dengan kata lain a dioverwrite
dengan a juga dan head bergerak
ke kiri.
4. Head membaca simbol A, maka
A tersebut harus dilewati (tidak boleh
dioverwrite), dengan kata lain A dioverwrite
dengan A juga dan head bergerak
ke kanan.
5. Head membaca simbol a,
ulangi langkah 2 dan 3.
6. (Setelah langkah 3) head
membaca simbol A, maka A tersebut harus dilewati (tidak boleh dioverwrite), dengan kata lain A dioverwrite dengan A juga
dan head bergerak ke kanan.
7. Head membaca simbol B, maka
B tersebut harus dilewati (tidak boleh
dioverwrite), dengan kata lain B dioverwrite
dengan A juga dan head bergerak
ke kanan.
8. Head membaca simbol e, maka e dioverwrite dengan e dan head bergerak ke kanan menuju stata H.
Skema graf Mesin Turing di atas adalah :
Contoh :
Lakukan tracing dengan mesin turing di atas untuk
kalimat-kalimat : aabb, aab.
Jawab :
i)
(S,aabb) Þ (1,Aabb) Þ (1,Aabb) Þ (2,AaBb) Þ (3,AaBb) Þ (S,AaBb)
Þ (1,AABb) Þ (1,AABb) Þ (2,AABB) Þ (2,AABB) Þ (4,AABB)
Þ (4,AABB) Þ (4,AABBe) Þ (H,AABBee)
ii) (S,aab) Þ (1,Aab) Þ (1,Aab) Þ (2,AaB) Þ (3,AaB) Þ (S,AaB) Þ (1,AAB)
Þ (1,AAbe) Þ crash, karena dari node 1 tidak ada edge
dengan bobot
komponen
pertamanya hampa (e)
AUTOMATA HINGGA (AH)
·
AH didefinisikan sebagai pasangan 5 tupel : (K, V
, M, S, Z).
K : himpunan hingga stata, ![](file:///C:%5CDOCUME%7E1%5CPKALEK%7E1%5CLOCALS%7E1%5CTemp%5Cmsohtmlclip1%5C01%5Cclip_image002.gif)
V
: himpunan hingga
simbol input (alfabet)
![](file:///C:%5CDOCUME%7E1%5CPKALEK%7E1%5CLOCALS%7E1%5CTemp%5Cmsohtmlclip1%5C01%5Cclip_image002.gif)
M : fungsi transisi,
menggambarkan transisi stata AH akibat pembacaan simbol
input.
Fungsi transisi ini biasanya diberikan
dalam bentuk tabel.
S Î K : stata awal
Z Ì K : himpunan stata penerima
·
Ada dua jenis automata hingga : deterministik (AHD, DFA = deterministic finite automata) dan non
deterministik (AHN, NFA = non
deterministik finite automata).
- AHD : transisi stata AH
akibat pembacaan sebuah simbol bersifat tertentu.
M(AHD) : K ´ V
® K
- AHN : transisi stata AH
akibat pembacaan sebuah simbol bersifat tak tentu.
M(AHN) : K ´ V
® ![](file:///C:%5CDOCUME%7E1%5CPKALEK%7E1%5CLOCALS%7E1%5CTemp%5Cmsohtmlclip1%5C01%5Cclip_image004.gif)
![](file:///C:%5CDOCUME%7E1%5CPKALEK%7E1%5CLOCALS%7E1%5CTemp%5Cmsohtmlclip1%5C01%5Cclip_image002.gif)
![](file:///C:%5CDOCUME%7E1%5CPKALEK%7E1%5CLOCALS%7E1%5CTemp%5Cmsohtmlclip1%5C01%5Cclip_image004.gif)
Automata Hingga Deterministik (AHD)
Ilustrasi
graf untuk AHD F adalah sebagai berikut :
Lambang
stata awal adalah node dengan anak panah.
Lambang
stata awal adalah node ganda.
ontoh
kalimat yang diterima AHD : a, b, aa, ab, ba, aba, bab, abab, baba
Contoh
kalimat yang tidak diterima AHD : bb, abb, abba
AHD
ini menerima semua kalimat yang tersusun dari simbol a dan b yang tidak
mengandung substring bb.
Contoh :
Telusurilah,
apakah kalimat-kalimat berikut diterima AHD :
abababaa,
aaaabab, aaabbaba
Jawab :
i)
M(q0,abababaa) Þ M(q0,bababaa) Þ M(q1,ababaa) Þ M(q0,babaa)
Þ M(q1,abaa) Þ M(q0,baa) Þ M(q1,aa) Þ M(q0,a) Þ q0
Tracing
berakhir di q0 (stata penerima) Þ kalimat abababaa diterima
ii)
M(q0, aaaabab) a M(q0,aaabab) a M(q0,aabab) a M(q0,abab)
Þ M(q0,bab) Þ M(q1,ab) Þ M(q0,b) a q1
Tracing berakhir di q1 (stata penerima) Þ kalimat aaaababa diterima
iii) M(q0, aaabbaba) Þ M(q0, aabbaba) Þ M(q0, abbaba) Þ M(q0, bbaba)
Þ M(q1,bbaba) Þ M(q2,baba) Þ M(q2,aba) Þ M(q2,ba) Þ M(q2,a) a q2
Tidak ada komentar:
Posting Komentar