Teori Automata

Teori Automata

Teori automata bercerita tentang teori yang mengenai mesin-mesin abstrak dan berkaitan erat dengan teori bahasa formal. Ada beberapa hal yang berkaitan dengan Otomata, yaitu Grammar. Grammar adalah bentuk abstrak yang dapat diterima (accept) untuk membangkitkan suatu kalimat otomata berdasarkan suatu aturan tertentu. Mudahnya adalah mesin abstrak yang mampu menerima dan menerjemahkan bahasa manusia (kalimat manusia) ke dalam bahasa mesin (komputer) atau bahasa mesin (komputer) ke bahasa manusia.

Konsep Dasar

• Anggota alfabet dinamakan simbol terminal.
• Kalimat adalah deretan hingga simbol-simbol terminal.
• Bahasa adalah himpunan kalimat-kalimat. Anggota bahasa bisa tak hingga kalimat.
• Simbol-simbol berikut adalah simbol terminal:

Huruf kecil, misalnya: a, b, c
Simbol operator, misalnya: +, , dan *
Simbol tanda baca, misalnya: (, ), dan ;
Simbol tanda baca, misalnya: (, ), dan ;[1]
String yang tercetak tebal, misalnya: if, then, dan else.

• Simbol-simbol berikut adalah simbol non terminal /Variabel: Huruf besar, misalnya: A, B, C. Huruf S sebagai simbol awal
• Huruf yunani melambangkan string yang tersusun atas simbol-simbol terminal atau simbol-simbol non terminal atau campuran keduanya, misalnya: α,β, dan ε
• Sebuah produksi dilambangkan sebagai α --> β, artinya: dalam sebuah derivasi dapat dilakukan penggantian simbol α dengan simbol β.
• Derivasi adalah proses pembentukan sebuah kalimat atau sentensial. Sebuah derivasi dilambangkan sebagai: α ==> β.
• Sentensial adalah string yang tersusun atas simbol-simbol terminal atau simbol-simbol non terminal atau campuran keduanya. Pada teori automata ini terdapat 4 jenis mesin automata yang terdiri dari :

Pada teori automata ini terdapat 4 jenis mesin yang terdiri dari :

1. Mesin Turing
2. Linear Bounded Automata
3. Push Down Automata
4. Finite State Automata

Untuk penjelasan lebih lanjut mengenai 4 jenis mesin automata, bisa kalian klik link pada tiap jenis mesin automata di atas.

Terima kasih sudah mau mengunjungi blog ini.

Mesin Turing

Mesin Turing

Sejarah Mesin Turing

Mesin turing diusulkan pada tahun 1936 oleh Alan Turing, seorang matematikawan Inggris sebagai model matematis sederhana sebuah komputer. Meskipun sederhana, Mesin Turing memiliki kemampuan untuk menggambarkan perilaku komputer (general-purpose) Mesin Turing dapat digunakan untuk menghitung kelas fungsi bilangan bulat yang dikenal sebagai fungsi rekursif sebagian (partial recursive function). Bahasa yang dikenali oleh Mesin Turing adalah bahasa tanpa- pembatasan (non-restricted language),yang disebut juga himpunan terenumerasi rekursif (recursively enumerable set).

Alan Mathison Turing (23 Juni 1912 - 7 Juni 1954), adalah seorang peneliti matematika dan komputer, dan pahlawan perang Inggris. Dia adalah dari peneliti-peneliti komputer modern digital pertama. Selain itu dia adalah orang pertama yang berpikir menggunakan komputer untuk berbagai keperluan. Dia mengatakan bahwa komputer dapat menjalankan berbagai program. Dia juga memberikan ide tentang mesin Turing, mesin yang dapat menjalankan sekumpulan perintah. Turing juga yang mencetuskan tes Turing. Namanya diabadikan dalam nama Penghargaan Turing.




Model Mesin Turing

Sebuah mesin Turing terdiri dari komponen-komponen:

1. Pengendali berhingga (finite control)
2. Pita masukan dengan sifat:

• Panjangnya tidak berhingga (ujung kiri terbatas, ujung kanan tidak terbatas)
• Dapat dibaca maupun ditulis
• Sel yang tidak berisi simbol masukan akan berisi simbol kosong (blank = B)

Perbedaan mesin turing dengan FSA dan PDA

Aksi Mesin Turing

Perilaku mesin turing bergantung pada simbol masukan yang berada pada posisi head baca/tulis dan status dari Finite Control. Dalam setiap gerakannya, mesin turing dapat melakukan salah satu dari aksi berikut:

1. Berubah status
2. Menuliskan simbol pada pita masukan. Aksi penulisan ini mengubah simbol yang sebelumnya berada pada sel tersebut
3. Menggerakan head ke kiri atau ke kanan

Linear Bounded Automata

Linear Bounded Automata

Linear bounded automata (LBA) adalah mesin yang berdasar pada state, sebuah tape yang berisi input strung, dan sebuah read/write head yang bergerak ke kiri dan ke kanan disekitar tape. Mesin ini membandingkan state saat ini dan simbol dari tape pada posisi head dengan jumlah aturan yang terbatas untuk menentukan state berikutnya, simbol mana yang akan ditulis pada tape, dan ke arah mana head akan bergerak.

Linear bounded automata memiliki kemiripan dengan mesin turing dimana sama-sama menggunakan tape, tetapi pada mesin ini adalah finite yakni terbatas.

Length = function (Length of the initial input string, constant c)

Perhitungan dibatasi pada area yang dibatasi konstan. Alfabet input berisi dua simbol khusus yang berfungsi sebagai tanda ujung kiri dan tanda ujung kanan yang berarti transisi tidak bergerak ke kiri dari penanda ujung kiri atau ke kanan penanda ujung kanan pada tape tersebut.

Linear bounded automata terdiri dari 8 tuples:

Q adalah seperangkat status terbatas

X adalah alfabet rekaman

∑ adalah alfabet input

q0 adalah kondisi awal

ML adalah penanda ujung kiri

MR adalah penanda ujung kanan di mana M R ≠ M L

δ adalah fungsi transisi yang memetakan setiap pasangan (negara, simbol pita) ke (negara, simbol pita, Konstan 'c') di mana c dapat berupa 0 atau +1 atau -1

F adalah himpunan status akhir

Linear bounded automata deterministik selalu context-sensitive dan linear bounded automata dengan bahasa kosong tidak dapat ditentukan.

Daftar Pustaka

Pratama, Rizky. 2016. Linear Bounded Automata. diakses dari https://prezi.com/drtqfxnwusl3/linear-bounded-automata/, pada 6 Maret 2020.
Tutorialspoint.com. 2020. Linear Bounded Automata. diakses dari https://www.tutorialspoint.com/automata_theory/linear_bounded_automata.htm, pada 6 Maret 2020.

Push Down Automata

PUSH DOWN AUTOMATA

PDA adalah mesin otomata dari TBBK yang diimplementasikan dengan stack sehingga hanya terdapat operasi “push” dan “pop” Stack (tumpukan) adalah suatu struktur data yang menggunakan prinsip LIFO (Last In First Out). Sebuah stack selalu memiliki top of stack dan elemen-elemen stack itu yang akan masuk ke dalam stack dengan method “push” dan akan keluar dari stack dengan method “pop”.

PDA memiliki 2 jenis transisi, yaitu yang merima simbol input, simbol top of stack, dan state. Setiap pilihan terdiri dari state berikutnya dan simbol- simbol. Penggantian isi stack dilakukan dengan opersi push dan pop. Jenis transisi yang kedua adalah transisi ε. Transisi ε tidak melakukan pembacaan input namun hanya menerima simbol top of stack dan state. Transisi ini memungkinkan PDA untuk memanipulasi isi stack dan berpindah antar state tanpa membaca input.

Dalam ilmu komputer, sebuah robot pushdown (PDA) adalah jenis robot yang mempekerjakan stack.

automata pushdown digunakan dalam teori tentang apa yang dapat dihitung oleh mesin. Mereka lebih mampu dari mesin finite-state tetapi kurang mampu dari mesin Turing. Deterministik pushdown automata dapat mengenali semua bahasa bebas konteks deterministik sementara yang nondeterministic dapat mengenali semua bahasa bebas konteks. Terutama mantan digunakan dalam desain parser.

Istilah “pushdown” mengacu pada fakta bahwa tumpukan dapat dianggap sebagai yang “didorong ke bawah” seperti dispenser nampan di kantin, karena operasi tidak pernah bekerja pada unsur-unsur lain dari elemen atas. Sebuah robot tumpukan, sebaliknya, tidak memungkinkan akses dan operasi pada elemen yang lebih dalam. Stack automata dapat mengenali satu set ketat lebih besar dari bahasa dari pushdown automata. [1] Sebuah bersarang tumpukan otomat memungkinkan akses penuh, dan juga nilai-nilai memungkinkan ditumpuk menjadi seluruh sub-tumpukan bukan hanya simbol yang terbatas tunggal.

PDA Deterministik

PDA M = (Q, Σ,   , q 0 , Z 0 , δ, A) pengenal palindrome L = {xcx T    x ∈ (a  b)*}, dimana = {a, b, Z 0 }, dan fungsi transisi δ terdefinisi melalui tabel berikut :

Sebagai contoh, perhatikan bahwa fungsi transisi No. 1 dapat dinyatakan sebagai : δ(q 0 , a, Z 0 ) = (q 0 , aZ 0 ). Pada tabel transisi tersebut terlihat bahwa pada stata q 0 PDA akan melakukan PUSH jika mendapat input a atau b dan melakukan transisi stata ke stata q 1 jika mendapat input c. Pada stata q 1 PDA akan melakukan POP.

PDA Non-Deterministik

PDA M = (Q, Σ, , q 0 , Z 0 , δ, A) pengenal palindrome L = {xx T x ∈ (a b)*} mempunyai komponen tuple berikut : Q = {q 0 , q 1 , q 2 }, A = { q 2 }, Σ = {a, b}, = {a, b, Z 0 }, dan fungsi transisi δ terdefinisi melalui tabel berikut :

Pada tabel transisi tersebut terlihat bahwa pada stata q 0  PDA akan melakukan PUSH jika

mendapat input a atau b dan melakukan transisi stata ke stata q 1 jika mendapat input ε. Pada stata q 1 PDA akan melakukan POP. Contoh menunjukkan bahwa PDA dapat dinyatakan sebagai mesin PUSH-POP.

Daftar Pustaka

Oktaria, Resalina. 2016. Push Down Automata (Ekivalensi PDA dan CFG serta deterministic PDA). diakses dari http://web.if.unila.ac.id/resalinaoktaria/2016/06/29/push-down-automata-ekivalensi-pda-dan-cfg-serta-deterministic-pda, pada 6 Maret 2020.
Juarna, Asep. 2003. TEORI BAHASA DAN AUTOMATA. diakses dari http://didi.staff.gunadarma.ac.id/Downloads/folder/0.0.3, pada 6 Maret 2020.

Finite State Automata

Finite State Automata

• Model matematika yang dapat menerima input dan mengeluarkan output.
• Memiliki state yang berhingga banyaknya dan dapat berpindah dari satu state ke state lainnya berdasar input dan fungsi transisi.
• Tidak memiliki tempat penyimpanan/memory, hanya bisa mengingat state terkini. 
• Mekanisme kerja dapat diaplikasikan pada : elevator, text editor, analisa leksikal, pencek parity. 

Contoh 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

Def 1. Finite State Automata dinyatakan oleh 5 tuple :

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

Contoh diatas,

Q = {Genap, Ganjil}

Σ = {0,1}

S = Genap

F = {Ganjil }

atau

δ(Genap,0) = Genap

δ(Genap,1) = Ganjil

δ(Ganjil,0) = Ganjil

δ(Ganjil,1) = Genap

Jenis FSA

Deterministic Finite Automata (DFA) : dari suatu state ada tepat satu state berikutnya untuk setiap simbol masukan yang diterima.

Non-deterministic Finite Automata (NFA) : dari suatu state ada 0, 1 atau lebih state berikutnya untuk setiap simbol masukan yang diterima.

Deterministic Finite Automata

• Contoh : pengujian parity ganjil. 
• Contoh lain : Pengujian untuk menerima bit string dengan banyaknya 0 genap,serta banyaknya 1 genap. 

1. 0011 : diterima. 
2. 10010 : ditolak, karena banyaknya 0 ganjil 

• Diagram transisi-nya : 

DFA nya

Q = {q0 , q1 , q2 , q3 }

Σ = {0,1}

S = q0

F = { q0}

fungsi transisi.

• Contoh lain DFA : Variabel dalam bahasa pascal diawali oleh huruf (besar/kecil), dan diikuti dengan huruf atau angka.

• Contoh DFA lainnya : 

Nondeterministic Finite Automata

• Perbedaan dengan NFA: fungsi transisi dapat memiliki 0 atau lebih fungsi transisi
• G = ({q0 , q1 , q2 , q3, q4 }, {0,1}, δ ,  q0 , { q2 , q4}}

• String diterima NFA bila terdapat suatu urutan transisi berdasar input, dari state awal ke state akhir.
• Harus mencoba semua kemungkinan.
• Contoh : string 01001

Def 2. Dua buah FSA disebut ekuivalen apabila kedua FSA tersebut menerima bahasa yang sama.

Contoh : FSA yang menerima bahasa {an | n≥0 }

Def 3.  Dua buah state dari FSA disebut indistinguishable  (tidak dapat dibedakan)

apabila :

• δ(q,w)∈F sedangkan δ(p,w)∉F dan
• δ(q,w) ∉F sedangkan δ(p,w) ∈F untuk semua w ∈ Σ*

Def 4.  Dua buah state dari FSA disebut distinguishable  (dapat dibedakan) bila terdapat

w ∈ Σ* sedemikian hingga:

• δ(q,w)∈F sedangkan δ(p,w)∉F dan
• δ(q,w) ∉F sedangkan δ(p,w) ∈F untuk semua w ∈ Σ*

Prosedur menentukan pasangan status indistinguishable

1. Hapus semua state yang tak dapat dicapai dari state awal.

2. Catat semua pasangan state (p,q) yang distinguishable, yaitu {(p,q) | p ∈ F ∧ q ∉ F}.

3. Untuk setiap pasangan (p,q) sisanya, untuk setiap a∈ Σ,  tentukan δ(p,a) dan δ(q,a).

Contoh:

1. Hapus state yang tidak tercapai -> tidak ada.
2. Pasangan distinguishable (q0,q4), (q1,q4), (q2,q4), (q3,q4).
3. Pasangan sisanya (q0,q1), (q0,q2), (q0,q3), (q1,q2) (q1,q3) (q2,q3).

Daftar Pustaka

Rustamaji, Heru Cahya. 2004. TEORI BAHASA DAN AUTOMATA. diakses dari  http://dharmayanti.staff.gunadarma.ac.id/Downloads/files/8874/Modul_TBO-1.pdf, pada 6 Maret 2020.