Finite State Automata dan Non Finite State Automata

-
Selamat Datang Kembali di Dunia Ilmu....

Dikesempatan kali ini, kami bakalan membahas penerapan FSA (Finite State Automata), DFA (Deterministik Finite Automata), NFA ( Non deterministik Finite Automata), Ekuivalen antar DFA, dan Reduksi jumlah State. Yuk langsung kita bahas aja...!!


  • Penerapan FSA (Finite Stste Automata)

Finite State Automata adalah model matematika yang dapat menerima input dan menghasilkan output yang memiliki state yang berhingga banyaknya dan daoat berpindah dari satu state ke state lainnya berdasarkan input dan fungsi transisi. Finite State Utomata bekerja dengan cara membaca memori masukan berupa tape menggunakan head baaca yang dikendalikan oleh kotak kendali state berhingga dimana terdapat sejumlah state berhingga. Namun FSA tidak memiliki tempat penyimpanan sehinga kemampuan mengingat sangatlah terbatas.
Finite State Automata didefisikan sebagai pasangan 5 tupel àM = ( Q, å, d, S, F).
Q : Himpunan hingga State
å : Himpunan hingga simbol input (Alfabet)
d  : Fungsi transisi, menggambarkan transisi stste FSA akibat pembacaan simbol
S  : State awal
F  : State Akhir
Contoh :
Q : { q0, q1, q2 }
å : { 1, 0 }
d  : 

S  : q0
F  : q1

Finite State Automata tebagi menjadi 2 yaitu DFA ( Deterministic Finite Automata) dan NFA ( Non deterministic Finite Automata)

  • Deterministik Finite Automata (DFA)
Deterministic Finite Automata didefisikan sebagai pasangan 5 tupel àM = ( Q, å, ∂, S, F).
Q : Himpunan hingga State
å : Himpunan hingga simbol input
∂  : Fungsi transisi, dimana  ∂ Î Q x å à Q
S  : State awal (initial state)
F  : State Akhir (final state)
Contoh :

Q : { q0, q1, q2 }
å : { a, b }
∂  : 
∂(q0, a) = q0
∂(q0, b) = q1
∂(q1, a) = q1
∂(q1, b) = q2
∂(q2, a) = q1
∂(q2, b) = q2

S  : q0
F  : q2
  • Non Deterministic Finite Automata (NFA)
Non deterministic Finite Automata bagian dari Finite State Automata yang memungkinkan satu simbom menimbulka beberapa transisi dan menghasilkan output yang tidak dapat dipastikan.
Non deterministic Finite Automata didefisikan sebagai pasangan 5 tupel àM = ( Q, å, ∂, S, F).
Q : Himpunan hingga State
å : Himpunan hingga simbol input
∂  : Fungsi transisi, dimana  ∂ Î Q x ( å U e ) à P (Q)
S  : State awal (initial state)
F  : State Akhir (final state)

  • Ekuivalen antar DFA
Dua istilah baru dalam ekuivalensi antar DFA yaitu Distinguishabel (dapat dibedakan) dan indistinguistable (tidak dapat dibedakan).
Dua DFA M1 dan M2 dinyatakan ekuivalen apabila L(M1) = L(M2)
  • Reduksi jumlah State
Reduksi dilakukan agar mengurangi jumlah state tanpa harus mengurangi kemampuan untuk menerima suatu bahasa. FSA direduksikan apabila terdapat atau terjadi useless state . hasil dari FSA yang diresuksikan merupakan eivalensi dari FSA semula.
Pasangan State dikelompokan berdasarkan :
1. Distinguishabel state (dapat dibedakan )
2. indistinguishabel State (tidak dapat dibedakan)
Pasangan dua buah state memiliki kemungkinan distinguishabel atau indistinguishabel namun tidak keduanya, dalam hal ini Jika 
a dan b adalah distinguishabel Dan
b dan c adalah distinguishabel Maka
p, r adalah distinguishabel dan p,q,r adalah distinguishabel.

Comments

Post a Comment

Popular posts from this blog

Testing Perangkat Lunak

-
Kata Testing pasti tidak asing ditelinga kita, Testing digunakan untuk menguji tingkat kelayakan suatu sistem ataupun barang yang bertujuan agar sistem dan barang jauh dari kerusakan dan error.  Menurut Myers (1979), testing adalah proses eksekusi program atau sistem secara intens untuk menemukan error. Testing memiliki beberapa prinsip untuk melakukan testing yaitu :  Testing yang komplit adalah tidak mungkin Testing adalah suatu pekerjaan yang kreatif namun sulit Alasan untuk melakukan testing adalah untuk mencegah adanya error pada program atau sistem Melakukan testing harus direncanakan terlebih dahulu Tahapan testing dibagi menjadi beberapa yaitu : Pre Implementation Testing Post Implementation Testing, d ibagi menjadi 2 bagian yaitu : White box Black box Unit Testing Integration Testing System Testing Testing terbagi menjadi beberapa tipe dan jenisnya, maka tipe-tipe testing dapat dibagi menjadi beberapa yaitu sebagai berikut : Volume Usability Performance Configuration ...
Read more

Pohon Penurunan - Tata Bahasa Bebas Konteks

-
Image
Selamat Datang Kembali di Dunia Ilmu ....... Parsing Apakah itu Pohon Penurunan...? Pohon penurunan atau  parse tree/ derivation tree  digunakan untuk menggambarkan penurunan simbol-simbol non terminal untuk memperoleh suatu string (untai). Setiap simbol variabel akan diturunkan menjadi terminal, sampai tidak ada yang belum tergantikan. Sebuah pohon (tree) adalah suatu graph  terhubung tidak sirkuler, yang memiliki suatu simpul (node) / vartex yang disebut akar (root) dan dari root memiliki lintasan ke setiap simpul. Contoh 1 : Misalkan Terdapat tata bahasa konteks dengan himpunan produksi sebagai berikut : Dari himpunan produksi tersebut buatlah pohon penurunan untuk membangkitkan string dengan susunan " bbabaaba ". Pohon penurunan yang didapatkan dari himpunan produksi tersebut ialah : Contoh 2 :  Misal terdapat himpunan produksi sebagai berikut : Dari himpunan produksi tersebut buatlah pohon penurunan yang membangkitkan string d...
Read more

Tugas IMK 4 Fasilkom UNSIKA-review software pembuatan prototype "Mockplus"

-
Image
Prototype adalah suatu metode pendekatan dalam pembuatan ata rekayasa perangkat lunak(software secara cepat dan bertahap. Dalam kesempatan ini saya akan me-review satu dari banyaknya software yang sering digunakan untuk membuat prototype yaitu " Mockplus ". Mockplus adalah software untuk membuat prototyping yng dapat membantu membuat prototype lebih cepat, praktis dan mudah, sepertihalnya slogan yang dikeluarkan oleh Mockplus yang berbunyi " Prototype Faster, Smarter and Easier ". Dengan menggunkan teknologi dari WYSIWYG  ( W hat Y ou S ee I s W hat Y ou G et) istilah ini digunakan untuk menggambarkan bahwasannya apa yang sedang dibuat ataupun disunting akan memiliki hasil akhir yang sama persis, sehingga memudahkan untuk melakukan drag-and-drop design yang ada pada Mockplus ini. 1. Menu     Fitur - fitur yang ada pada Mockplus : Design Specification Project Type Project Tree Prototype interaktif 2. Kelebihan Mockplus Mempunyai ...
Read more