CARA MEMBUAT FSA UTS TEORI BAHASA DAN AUTOMATA

  Assalamu'alaikum warahamtullohi Wabarakatuh

        Salam Sejahtera untuk kita semua, kembali berjumpa lagi di blog saya Widia Rahayu. Pada kesempatan kali ini yang akan dibahas pada blog saya adalah Mengenai Membuat Mesin Abstrak Finite State Automata. Adapun tujuan penulisan pada artikel kali ini selain sharing ilmu, juga untuk memenuhi tugas Ujian Tengah Semester Mata Kuliah Teori Bahasa dan Automata Semester V.

        Mesin Abstrak yang saya buat diantaranya adalah Deterministic Finite Automata (DFA). Non-Deterministic Automata (NFA) dan Push Down Automata (PDA). Untuk uraian selengkapnya langsung saja kita mulai pembahasannya :

 
DFA (Deterministic Finite Automata)

DFA merupakan teori komputasi dan cabang dari ilmu komputer teoritis. DFA adalah Finite-state Machine atau mesin keadaan terbatas yang menerima atau menolak string dari simbol dan hanya menghasilkan perhitungan unik dari otomata untuk setiap string yang di masukan.

DFA hanya mempunyai paling banyak satu transisi pada masing-masing state pada sembarang masukan. Jika digunakan tabel transisi untuk merepresentasikan fungsi transisi DFA, maka masing-masing isian di table transisi adalah satu state tunggal. Konsekuensinya, pada DFA lebih mudah menentukan apakah suatu string masukan diterima karena hanya terdapat paling banyak satu jalur dari state awal.

 a. Formal Definition Tuple

 

b. Diagram FSA

c. Uji Input
Dalam setiap pengujian input pada mesin abstrak FSA, apabila inputan berakhir pada state akhir / final, maka status input diterima (Accept), dan berlaku sebaliknya, apabila berakhir bukan pada state akhir, maka input di reject.

NFA (Non-Deterministic Finite Automata)

Nondeterministic Finite Automata (NFA) adalah salah satu bagian dari otomata berhingga atau Finite State Automata (FSA). Pada Nondeterministic Finite Automata (NFA) dimungkinkan satu simbol menimbulkan transisi ke lebih dari satu kondisi dan memberikan beberapa kemungkinan gerakan sehingga keluarannya tidak dapat dipastikan. Selain itu dimungkinkan juga terjadinya transisi spontan atau transisi –ε.

a. Formal Definition Tuple

  

 b. Diagram PSA

 c. Uji Input
Suatu string diterima oleh mesin abstrak bila terdapat suatu urutan transisi sehubungan dengan input string tersebut dari state awal sampai state akhir

PDA (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”.

a. Formal Definition Tuple

 M3=( Q, Σ, δ, S, F)
             Q = {q0, q1, q2, q3}
             Σ = {a, b}
             Γ = {b, Z}
             δ = {(q0, b, Z, q1, bZ), (q1, b, b, q1, bb), (q1, a, b, q2, λ), (q2, a, b, q3, λ), (q3, λ, Z, q2, Z)}

             S = {q0}

             F = {q3}

           b. Diagram PDA
       

            c.  Uji Input

Demikianlah yang bisa saya sharing mengenai pembuatan mesin Abstrak DFA, NFA dan PDA. Apabila masih ada kekurangan boleh dikoreksi dikolom komentar. Atas perhatian dan kunjungannya melihat blog ini, saya ucapkan terimakasih. :)

Salam manis,

Widia Rahayu Debora Namah