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

1. Mesin turing memiliki pita berupa array sebagai memori yang dapat menyimpan sebuah simbol tunggal
2. Mesin turing memiliki head sebagai penunjuk posisi yang sedang diakses pada pita
3. Head dapat bergerak kekanan/kekiri pada pita sesuai fungsi transisi yang ditetapkan untuk membaca inputan
4. 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

1. Lihat state semula dan simbol yang ditunjuk head
2. Berdasarkan fungsi transisinya,tentukan:
   a.     State berikutnyab.     Lakukan penulisan ke pita c.     Gerakkan head ke kanan dan ke kiri
3. Bila dari pasangan state dan simbol yang ditunjuk head tidak ada lagi fungsi transisinya,berarti mesin turing berhenti
4. 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.

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.

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.

ID adalah triple (q, w,), dimana:

1. q adalah negara saat ini.
   
2. w adalah masukan yang tersisa.
3. 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?

1. Deterministic automata(DFA) dan otomatis finite automata(NFA)
2. Deterministic push down automata(DPDA)dan non-deterministic push down automata(NPDA))
3. Deterministic mesin Turing tunggal dan mesin Turing Non-deterministik tunggal-tape
4. 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 ) 

Q = himpunan state

Σ = himpunan simbol input

δ = fungsi transisi δ : Q × Σ

S = state awal / initial state , S ∈ Q

F = state akhir, F ⊆ Q

Karakteristik FSA

1. Setiap Finite Automata memiliki keadaan dan transisi yang terbatas.
2. Transisi dari satu keadaan ke keadaan lainnya dapat bersifat deterministik atau non-deterministik.
3. Setiap Finite Automata selalu memiliki keadaan awal.
4. 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:

1. 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).
2. Himpunan berhingga simbol masukan
3. 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).

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

Finite State Diagram terdiri dari:

1. Lingkaran menyatakan state
2. 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
3. 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,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.

Jadi sebuah mesin otomata dapat dinyatakan dalam diagram transisi, fungsi transisi dan tabel transisi.

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

https://techno-inmyworld.blogspot.com/2014/06/mesin-turing-cara-kerja-mesin-turing.html

Linear Bounded Automata

https://en.wikipedia.org/wiki/Linear_bounded_automaton

Pushdown Automata

https://www.geeksforgeeks.org/introduction-of-pushdown-automata/

Finite State Automata

https://riskasimaremare.wordpress.com/2013/04/23/finite-state-automata/