Tugas Teori Kompilasi
Mesin Turing
Pada PDA (Push Down Automata) digunakan stack untuk menyimpan dan
mengakses data inputan. Tetapi hal ini menyebabkan kemampuan kerja PDA yang
terbatas karena pada prinsip stack,hanya data teratas yang bisa diakses. Ini
menyebabkan keterbatasan PDA.
Mesin turing menggunakan pita (tape) sebagai memori yang berbentuk
array . Hal ini menyebabkan data pada pita dapat diakses dari mana saja.
Spesifikasi Mesin Turing
- Mesin turing memiliki pita berupa array sebagai memori yang dapat menyimpan sebuah simbol tunggal
- Mesin turing memiliki head sebagai penunjuk posisi yang sedang diakses pada pita
- Head dapat bergerak kekanan/kekiri pada pita sesuai fungsi transisi yang ditetapkan untuk membaca inputan
- Head juga dapat melakukan penulisan/ mengubah isi pita
Sebuah mesin turing secara formal dinyatakan dalam 7 tupel,
M = (Q, S, G, d, S, F, b)
Dimana:
Q = himpunan state
S = himpunan
simbol input
G = simbol pada
pita,termasuk blank
d = fungsi
transisi
S = state awal
(S anggota elemen Q)
F = himpunan
state akhir
b = simbol
kosong (menandakan bagian yang tidak terisi)
Pembacaan fungsi transisi pada mesin turing
Misal :
d (q1,a) =
(q1,b,R) dibaca :
Pada
state q1 yang menunjukkan karakter a pada pita, maka karakter pada state
tersebut berubah menjadi b dan head bergerak ke kanan dengan menunjuk array
sebagai state q1
Prinsip Kerja Mesin Turing
- Lihat state semula dan simbol yang ditunjuk head
- Berdasarkan
fungsi transisinya,tentukan:
a. State berikutnyab. Lakukan penulisan ke pita c. Gerakkan head ke kanan dan ke kiri - Bila dari pasangan state dan simbol yang ditunjuk head tidak ada lagi fungsi transisinya,berarti mesin turing berhenti
- Bila mesin turing berhenti di dalam state final (F) , berarti input diterima. Sebaliknya jika mesin berhenti tidak pada state akhir,maka berarti inputan tersebut ditolak.
Linear Bounded Automata
Dalam komputer sains, linear bounded automata (Singkatan
Iba) adalah bentuk terbatas dari Mesin Turing.
Operasi
Sebuah linear bounded automata adalah nondeterministik
mesin turing yang memenuhi tiga syarat berikut:
- Alfabet input termasuk dua simbol khusus, sebagai penanda ujung kanan dan kiri.
- Transisi nya mungkin tidak mencetak simbol lain selama penanda ujung.
- Transisi nya mungkin tidak bergerak ke kiri dari penanda ujung kiri atau ke kanan dari penanda ujung kanan.
Dengan kata lain: daripada memiliki potensi pita
tak terbatas di mana untuk menghitung, perhitungan terbatas pada bagian dari pita
berisi masukan ditambah dua kotak pita memegang penanda akhir.
Sebuah alternatif, definisi kurang terbatas adalah sebagai berikut:
Seperti mesin Turing, LBA memiliki sebuah kaset terbuat dari sel yang dapat memuat simbol dari alfabet terbatas, kepala yang dapat dibaca dari atau menulis ke satu sel pada suatu waktu dan dapat dipindahkan, dan sejumlah terbatas.
Sebuah LBA berbeda dari Mesin Turing bahwa ketika rekaman ini awalnya dianggap memiliki panjang tak terbatas, hanya bagian terbatas dari pita, yang panjangnya adalah fungsi linear dari panjang masukan awal, dapat dilakukan oleh read/write head; oleh sebab itu nama linear B dari b automaton.
Limitasi ini membuat sebuah LBA sebuah model yang agak lebih akurat dari komputer dunia nyata dari Mesin Turing, Yang definisi mengasumsikan kaset terbatas.
Seperti mesin Turing, LBA memiliki sebuah kaset terbuat dari sel yang dapat memuat simbol dari alfabet terbatas, kepala yang dapat dibaca dari atau menulis ke satu sel pada suatu waktu dan dapat dipindahkan, dan sejumlah terbatas.
Sebuah LBA berbeda dari Mesin Turing bahwa ketika rekaman ini awalnya dianggap memiliki panjang tak terbatas, hanya bagian terbatas dari pita, yang panjangnya adalah fungsi linear dari panjang masukan awal, dapat dilakukan oleh read/write head; oleh sebab itu nama linear B dari b automaton.
Limitasi ini membuat sebuah LBA sebuah model yang agak lebih akurat dari komputer dunia nyata dari Mesin Turing, Yang definisi mengasumsikan kaset terbatas.
Definisi
kuat dan lemah mengarah ke kemampuan komputasi yang sama dari kelas otomat, karena
teori linear speedup.
Bahasa LBA dan Konteks-Sensitif
Linear based automata menerima untuk kelas bahasa
konteks-sensitif. Satu-satunya pembatasan yang ditempatkan pada grammars untuk
bahasa tersebut adalah bahwa tidak ada peta produksi string ke string yang
lebih pendek. Dengan demikian tidak ada derivasi dari suatu string dalam bahasa
yang sensitif dalam konteks dapat berisi suatu bentuk pengirim pesan lebih lama
dari string itu sendiri. Karena ada korespondensi satu-ke-satu antara automata
yang berlinear dan grammars yang berlokasi, tidak lebih dari yang diduduki oleh
string asli diperlukan untuk string yang diakui oleh automaton.
Riwayat
Pada tahun 1960, John Myhill memperkenalkan
sebuah model automaton hari ini dikenal sebagai deterministik linear bobotive
automaton. Pada tahun 1963, Peter S. Landweber membuktikan bahwa bahasa
diterima oleh deterministic LBAs adalah konteks-sensitif. pada tahun 1964,
Kuroda s-Y. memperkenalkan lebih banyak model umum (nondeterministic) linear
bundedata, mencatat bahwa bukti Landweber juga bekerja untuk nondeterministic
linear bundata, dan menunjukkan bahwa bahasa yang diterima oleh mereka adalah
benar-bahasa yang sensitif.
Masalah LBA
Dalam makalah seminalnya, Kuroda juga menyatakan dua tantangan
penelitian, yang kemudian menjadi terkenal dikenal sebagai "masalah
LBA": masalah LBA pertama adalah apakah kelas bahasa diterima oleh LBA
sama dengan kelas bahasa yang diterima oleh menentukan LBA. Masalah ini dapat
diungkapkan dengan singkat dalam bahasa teori kompleksitas komputasi sebagai:
Masalah LBA pertama: apakah NSPACE(O(n) = DSPACE(O (n)?
Masalah LBA kedua adalah apakah kelas bahasa diterima oleh LBA
ditutup di bawah komplemen.
Masalah LBA kedua: adalah NSPACE(O(n) = co-NSPACE(O (n)?
Seperti
yang sudah diamati oleh Kuroda, jawaban negatif untuk masalah LBA kedua akan
menyiratkan jawaban negatif untuk masalah pertama. Tapi masalah LBA kedua
memiliki jawaban afirmatif, yang tersirat oleh teori Immerman–Szelepcsényi
terbukti 20 tahun setelah masalah itu dibesarkan. Sampai hari ini, masalah LBA
pertama masih terbuka.
Pushdown Automata
Pengenalan Pushdown Automata
Pushdown Automata adalah sebuah automata terbatas dengan memori
ekstra bernama stack yang membantu Pushdown automata untuk mengenali konteks
bahasa bebas.
Mesin pushdown tak-deterministik dapat memiliki lebih dari satu langkah dari sebuah negara pada sebuah simbol masukan dan stack simbol.
Hal ini tidak selalu mungkin untuk mengubah non-deterministik pushdown automata ke deterministic pushdown.
Kekuatan ekspresif dari PDA non-deterministik lebih dibandingkan dengan Polda ekspresif ekspresif yang sebagai beberapa bahasa yang diterima oleh NPDA tetapi bukan dengan deterministik yang akan dibahas dalam artikel berikutnya.
Push down automata dapat diimplementasikan menggunakan accepetance oleh stack kosong atau
accepetance oleh keadaan akhir dan satu dapat diubah ke yang lain.
Finite State Automata (FSA) adalah model matematika yang dapat menerima input dan mengeluarkan output yang memiliki state yang berhingga banyaknya dan dapat berpindah dari satu state ke state lainnya berdasarkan input dan fungsi transisi. Finite state automata tidak memiliki tempat penyimpanan/memory, hanya bisa mengingat state terkini.
Sebuah otomatis Pushdown (PDA) dapat didefinisikan sebagai :
Q adalah
seperangkat keadaan
∑ adalah set
dari simbol masukan
Γ adalah kumpulan simbol pushdown (yang dapat didorong dan keluar
dari stack)
q0 adalah keadaan awal
Z adalah simbol awal pushdown (yang awalnya ada dalam stack)
F
adalah satu set dari negara-negara terakhir fungsi transisi yang peta Q {Σ ∪ ∈} x γ
kedalam Q X γ*.
Dalam keadaan yang diberikan, PDA akan membaca simbol masukan dan stack simbol
(top dari stack) dan pindah ke sebuah negara baru dan mengubah simbol dari
stack.
Deskripsi Instan (ID)
Deskripsi instan (ID) adalah notasi informal tentang bagaimana
sebuah PDA "mengomput" sebuah string masukan dan membuat keputusan
bahwa string diterima atau ditolak.
Eg- (p, b, t) (q, w,)
Ini menyiratkan bahwa ketika mengambil transisi dari p state q, simbol masukan ' b 'telah dikonsumsi, dan puncak tumpukan' T 'diganti oleh Tali baru'
ID adalah triple (q, w,), dimana:
- q adalah negara saat ini.
- w adalah masukan yang tersisa.
- ini isinya, diatas sebelah kiri.
Notasi Turnstile
Tanda ⊢ disebut "notasi turnstile" dan melambangkan satu
gerakan. tanda * terdapat sejumlah langkah.
Eg- (p, b, t) (q, w,)
Ini menyiratkan bahwa ketika mengambil transisi dari p state q, simbol masukan ' b 'telah dikonsumsi, dan puncak tumpukan' T 'diganti oleh Tali baru'
Contoh : definisikan otomata pushdown untuk bahasa {anbn | n >
0}
Solusi : M = dimana Q = { q0, q1 } dan Σ = { a, b } dan Γ = { A, Z
} dan &delta diberikan oleh :
&delta( q0, a, Z) = {q0, AZ ) }
&delta( q0, a, A) = {q0, AA ) }
&delta( q0, b, A) = {q1, ∈) }
&delta( q1, b, A) = {q1, ∈) }
&delta( q1,∈, Z) = {q1, ∈) }
Mari
kita lihat bagaimana robot ini bekerja untuk aabbb.
Penjelasan : awalnya, keadaan automata adalah q0 dan simbol di
stack adalah Z dan masukan adalah aabbb seperti yang ditampilkan di baris 1.
Saat membaca ' a ' (ditampilkan dalam tebal di baris 2), Keadaan akan tetap q0
dan akan menekan simbol A di stack. Berikutnya ' a ' (ditampilkan di baris 3),
ini akan mendorong simbol A lain di stack. Setelah membaca 3 a's, tumpukan akan
AAAZ dengan A di atas. Setelah membaca ' b '(seperti yang ditampilkan di baris
5), Ini akan pop A dan pindah ke state q1 dan stack akan menjadi AAZ. Ketika
semua b dibaca, negara akan menjadi q1 dan stack akan menjadi Z. Di baris 8, di
masukan simbol ' ∈ ' dan Z di stack, ini akan pop Z dan stack akan kosong. Jenis
Penerimaan ini dikenal sebagai penerimaan dengan stack kosong.
Catatan :
Automaton di atas pushdown adalah deterministik dalam alam karena
hanya ada satu langkah dari sebuah negara bagian pada simbol masukan dan stack
simbol.
Mesin pushdown tak-deterministik dapat memiliki lebih dari satu langkah dari sebuah negara pada sebuah simbol masukan dan stack simbol.
Hal ini tidak selalu mungkin untuk mengubah non-deterministik pushdown automata ke deterministic pushdown.
Kekuatan ekspresif dari PDA non-deterministik lebih dibandingkan dengan Polda ekspresif ekspresif yang sebagai beberapa bahasa yang diterima oleh NPDA tetapi bukan dengan deterministik yang akan dibahas dalam artikel berikutnya.
Push down automata dapat diimplementasikan menggunakan accepetance oleh stack kosong atau
accepetance oleh keadaan akhir dan satu dapat diubah ke yang lain.
Pertanyaan: mana dari pasangan berikut memiliki kekuatan ekspresif
yang berbeda?
- Deterministic automata(DFA) dan otomatis finite automata(NFA)
- Deterministic push down automata(DPDA)dan non-deterministic push down automata(NPDA))
- Deterministic mesin Turing tunggal dan mesin Turing Non-deterministik tunggal-tape
- tunggal-tape mesin Turing dan mesin Turing
Setiap
NFA dapat diubah menjadi DFA. Jadi, ada kekuatan ekspresif. Seperti dibahas di
atas, setiap NPDA tidak dapat dikonversi ke DPDA. Jadi, kekuatan NPDA dan DPDA
tidak sama. Oleh karena itu Pilihan (2) benar.
Finite State Automata
Finite state automata
adalah mesin abstrak berupa sistem model matematika dengan masukan dan keluaran
diskrit yang dapat mengenali bahasa paling sederhana (bahasa reguler) dan dapat
diimplementasikan secara nyata.
Finite State Automata (FSA) adalah model matematika yang dapat menerima input dan mengeluarkan output yang memiliki state yang berhingga banyaknya dan dapat berpindah dari satu state ke state lainnya berdasarkan input dan fungsi transisi. Finite state automata tidak memiliki tempat penyimpanan/memory, hanya bisa mengingat state terkini.
Finite State Automata
dinyatakan oleh pasangan 5 tuple, yaitu:
M=(Q , Σ , δ , S , F )
M=(Q , Σ , δ , S , F )
Q = himpunan state
Σ = himpunan simbol
input
δ = fungsi transisi δ :
Q × Σ
S = state awal /
initial state , S ∈ Q
F = state akhir, F ⊆ Q
Karakteristik FSA
- Setiap Finite Automata memiliki keadaan dan transisi yang terbatas.
- Transisi dari satu keadaan ke keadaan lainnya dapat bersifat deterministik atau non-deterministik.
- Setiap Finite Automata selalu memiliki keadaan awal.
- Finite Automata dapat memiliki lebih dari satu keadaan akhir.
Jika setelah pemrosesan
seluruh string, keadaan akhir dicapai, artinya otomata menerima string
tersebut.
Setiap FSA memiliki:
- Himpunan berhingga (finite) status (state)a. Satu buah status sebagai status awal (initial state), biasa dinyatakan q0.b. Beberapa buah status sebagai status akhir (final state).
- Himpunan berhingga simbol masukan
- Fungsi transisi
Menentukan status berikutnya dari setiap pasang status
dan sebuah simbol masukan.
Cara Kerja Finite State Automata
Finite State Automata
bekerja dengan cara mesin membaca memori masukan berupa tape yaitu 1 karakter
tiap saat (dari kiri ke kanan) menggunakan head baca yang dikendalikan oleh
kotak kendali state berhingga dimana pada mesin terdapat sejumlah state
berhingga.
Finite Automata selalu dalam kondisi yang disebut state awal (initial state) pada saat Finite Automata mulai membaca tape. Perubahan state terjadi pada mesin ketika sebuah karakter berikutnya dibaca. Ketika head telah sampai pada akhir tape dan kondisi yang ditemui adalah state akhir, maka string yang terdapat pada tape dikatakan diterima Finite Automata (String-string merupakan milik bahasa bila diterima Finite Automata bahasa tersebut).
Fungsi Transisi (d) adalah representasi matematis atas transisi keadaan.
Finite State Diagram
terdiri dari:
dari suatu state ada 0, 1 atau lebih state berikutnya untuk setiap simbol masukan yang diterima.
Mesin Turing
Linear Bounded Automata
Pushdown Automata
Finite State Automata
Finite Automata selalu dalam kondisi yang disebut state awal (initial state) pada saat Finite Automata mulai membaca tape. Perubahan state terjadi pada mesin ketika sebuah karakter berikutnya dibaca. Ketika head telah sampai pada akhir tape dan kondisi yang ditemui adalah state akhir, maka string yang terdapat pada tape dikatakan diterima Finite Automata (String-string merupakan milik bahasa bila diterima Finite Automata bahasa tersebut).
Finite State Diagram (FSD)
Finite State Automata
dapat dimodelkan dengan Finite State Diagram (FSD) dapat juga disebut State
Transition Diagram. Sistem transisi adalah sistem yang tingkah lakunya
disajikan dalam bentuk keadaan-keadaan (states). Sistem tersebut dapat bergerak
dari state yang satu ke state lainnya sesuai dengan input yang diberikan
padanya.
Fungsi Transisi (d) adalah representasi matematis atas transisi keadaan.
S = himpunan alfabet.
Q = himpunan
keadaan-keadaan.
d = Q x S à Q
- Lingkaran menyatakan state
- Lingkaran diberi label sesuai dengan nama state tersebut. Adapun pembagian lingkaran adalah:
a. Lingkaran bergaris tunggal berarti state sementara
b. Lingkaran bergaris ganda berarti state akhir - Anak Panah menyatakan transisi yang terjadi.
Label di anak panah
menyatakan simbol yang membuat transisi dari 1 state ke
state lain. 1 anak
panah diberi label start untuk
menyatakan awal mula transisi dilakukan.
Contoh
FSA : pencek parity ganjil
Misal input : 1101
Genap 1 Ganjil 1 Genap 0 Genap 1 Ganjil :
diterima mesin
Misal input : 1100
Genap 1 Ganjil 1 Genap 0 Genap 0 Genap :
ditolak mesin
Dari contoh diatas, maka:
Q =
{Genap, Ganjil}
Σ =
{0,1}
S =
Genap
F =
{Ganjil }
atau
δ(Genap,0) = Genap
δ(Genap,0) = Genap
δ(Genap,1)
= Ganjil
δ(Ganjil,0)
= Ganjil
δ(Ganjil,1)
= Genap
Sebuah FSA dibentuk dari lingkaran yang
menyatakan state:
- Label pada lingkaran adalah nama state
- Busur menyatakan transisi/ perpindahan
- Label pada busur yaitu symbol input
- Lingkaran yang didahului sebuah busur tanpa label menyatakan state awal
- Lingkaranb ganda menyatakan state akhir/ final.
Jenis FSA
Ada dua jenis FSA :
Deterministic Finite Automata (DFA)
dari suatu state ada tepat satu state berikutnya
untuk setiap simbol masukan yang diterima. Deterministik artinya tertentu/sudah
tertentu fungsi transisinya.
Notasi matematis DFA:
M =
nama DFA
Q =
himpunan keadaan DFA
S =
himpunan alfabet
d =
fungsi transisi
q0 =
keadaan awal
F =
keadaan akhir
M = (Q, S, d, q0, F)
Contoh : Pengujian untuk menerima bit string
dengan banyaknya 0 genap, serta banyaknya 1 genap.
0011 :
diterima
10010
: ditolak, karena banyaknya 0 ganjil
Diagram transisi-nya :
DFA nya:
Q = {q0
, q1 , q2 , q3 }
Σ =
{0,1}
S = q0
F = { q0
fungsi transisi adalah:
δ(
q0,011)= δ( q2,11) =δ( q3,1)= q2 è Ditolak
δ(
q0,1010)= δ( q1,010) =δ( q3,10)=δ( q2,0)= q0 èDiterima
Non-deterministic Finite Automata (NFA)
dari suatu state ada 0, 1 atau lebih state berikutnya untuk setiap simbol masukan yang diterima.
Non-Deterministic Finite Automata:
- Otomata berhingga yang tidak pasti untuk setiap pasangan state input, bisa memiliki 0 (nol) atau lebih pilihan untuk state berikutnya.
- Untuk setiap state tidak selalu tepat ada satu state berikutnya untuk setiap simbol input yang ada.
- Dari suatu state bisa terdapat 0,1 atau lebih busur keluar (transisi) berlabel simbol input yang sama.
- Untuk NFA harus dicoba semua kemungkinan yang ada sampai terdapat satu yang mencapai state akhir.
- Suatu string x dinyatakan diterima oleh bahasa NFA, M= (Q, _, d, S, F) bila {x | d (S,x) memuat sebuah state di dalam F}
Kedua
finite automata di atas mampu mengenali himpunan reguler secara presisi. Dengan
demikian kedua finite automata itu dapat mengenali string-string yang
ditunjukkan dengan ekspresi reguler secara tepat.
DFA dapat menuntun recognizer(pengenal) lebih
cepat dibanding NDFA. Namun demikian, DFA berukuran lebih besar dibanding NDFA
yang ekivalen dengannya. Lebih mudah membangun NDFA dibanding DFA untuk suatu
bahasa, namun lebih mudah mengimplementasikan DFA dibanding NDFA.
Reference
Mesin Turing
Linear Bounded Automata
Pushdown Automata
Tugas Teori Kompilasi
Reviewed by Lis
on
08.42
Rating: 5
Reviewed by Lis
on
08.42
Rating: 5