Automata

By | February 12, 2020

Table of Contents

Automata

Automata

Automata

Automata adalah mesin abstrak yang dapat mengenali (recognize), menerima (accept), atau membangkitkan (generate) sebuah kalimat dalam bahasa tertentu.
Beberapa Pengertian Dasar :
• Simbol adalah sebuah entitas abstrak (seperti halnya pengertian titik dalam geometri). Sebuah huruf atau sebuah angka adalah contoh simbol.
• String adalah deretan terbatas (finite) simbol-simbol. Sebagai contoh, jika a, b, dan c adalah tiga buah simbol maka abcb adalah sebuah string yang dibangun dari ketiga simbol tersebut.
• Jika w adalah sebuah string maka panjang string dinyatakan sebagai |w| dan didefinisikan sebagai cacahan (banyaknya) simbol yang menyusun string tersebut. Sebagai contoh, jika w = abcb maka |w|= 4.
• String hampa adalah sebuah string dengan nol buah simbol. String hampa dinyatakan dengan simbol ε (atau ^) sehingga |ε|= 0. String hampa dapat dipandang sebagai simbol hampa karena keduanya tersusun dari nol buah simbol.
• Alfabet adalah hinpunan hingga (finite set) simbol-simbol.
Grammar dan Klasifikasi Chomsky
Grammar G didefinisikan sebagai pasangan 4 tuple : VT, VN, S, Q dan dituliskan sebagai G(VT ,VN ,S , Q), dimana:
VT : himpunan simbol-simbol terminal (atau himpunan token -token, atau alfabet).
VN : himpunan simbol-simbol non terminal.
S ∈ VN : simbol awal (atau simbol start).
Q : himpunan produksi.
Berdasarkan komposisi bentuk ruas kiri dan ruas kanan produksinya (α → β), Noam Chomsky mengklasifikasikan 4 tipe grammar :
1. Grammar tipe ke-0 : Unrestricted Grammar (UG)
. Ciri : α, β ∈ (VT | VN) *, α > 0
2. Grammar tipe ke-1 : Context Sensitive Grammar (CSG)
. Ciri : α, β ∈ (VT | VN) *, 0 < α ≤ β
3. Grammar tipe ke-2 : Context Free Grammar (CFG)
. Ciri : α ∈ VN, β ∈ (VT | VN) *
4. Grammar tipe ke-3 : Regular Grammar (RG)
. Ciri : α ∈ VN, β ∈ { VT , VT VN} atau α ∈ VN, β ∈ { VT , VN VT}

Automata Hingga (AH)
AH didefinisikan sebagai pasangan 5 tupel : (Q, V T , σ, q0, F):
• Q : himpunan hingga stata
• VT : himpunan hingga simbol input (alfabet)
• σ : fungsi transisi, menggambarkan transisi stata AH akibat pembacaan simbol input.
Fungsi transisi ini biasanya diberikan dalam bentuk tabel.
• q0 ∈ Q : stata awal
• F ⊂ Q : 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.
. σ (AHD) : Q × V T → Q
– AHN : transisi stata AH akibat pembacaan sebuah simbol bersifat tak tentu.
. σ (AHN) : Q × V T → 2Q
Automata Hingga Deterministik (AHD)
Berikut ini sebuah contoh AHD F(Q, V T , σ, q0, Z), dimana :
Q = {q0, q1, q2}

Sumber : https://abovethefraymag.com/