Langsung ke konten utama

 

Teknik Kompilasi Pert 5: 

PERBEDAAN DFA dan NFA

Mari kita bahas dulu apa sih DFA & NFA itu?
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.
Non-Deterministic Finite Automata (NFA) menerima masukan (input) dengan memiliki lebih dari 1 busur keluar atau bahkan tidak memiliki busur keluar. Non-Deterministic Finite Automata (NFA) sering dikenal juga sebagai Non-Deterministic Finite-State Machine (NFSM) dan Non-Deterministic Finite-State Automaton (NFSA).


Finite Automata adalah mesin automata dari suatu Bahasa regular. Finite Automata memiliki jumlah state yang banyaknya berhingga dan dapat berpindah-pindah dari suate state ke state yang lainnya. Finite Automata dibagi menjadi Deterministic Finite Automata (DFA) dan Non Deterministic Finite Automata (NFA).

Berikut contoh dari Deterministic Finite Automata :

Berikut contoh dari Non Deterministic Finite Automata (NFA) :

Berdasarkan contoh Deterministic Finite Automata (DFA) dan Non Deterministic Finite Automata (NFA) yang ada di atas, terlihat perbedaan antara DFA dan NFA yaitu :

  • Pada Deterministic Finite Automata, jika suatu state diberi inputan maka state tersebut akan selalu tepat menuju satu state
  • Pada Non Deterministic Finite Automata, jika suatu state diberi inputan maka mungkin saja bisa menuju ke beberapa state berikutnya. Dapat dilihat di S0, jika diberi inputan b bisa menuju ke S1 dan S2.


Komentar

Posting Komentar

Postingan populer dari blog ini

 Teknik Kompilasi Pertemuan 7 Klasifikasi Grammar menurut Chomsky 1.        TATA BAHASA (GRAMMAR) Bahasa  merupakan himpunan  kalimat  (baik terhingga maupun tak terhingga). Bahasa dapat disajikan dengan menyebut kalimatnya satu persatu. Untuk bahasa tak hingga, penyebutan seperti itu tidak mungkin. Oleh karena itu diciptakan cara penyajian yang mendeskripsikan bahasa secara efisien. Cara penyajian tersebut adalah  Tata Bahasa  atau  Grammar. Sebuah Tata Bahasa (Grammar) didefinisikan sebagai 4 tupel :             G = (V n,  V t,  S, Q) V n  dan V t  adalah simbol  Non Terminal  dan  Simbol Terminal . S  adalah sebuah elemen anggota V n  yang disebut  Simbol Start . Q  merupakan himpunan  Produksi. Chomsky mengelompokkan Grammar menjadi 4 kelompok : 1.        Tipe nol : UnRes...
Posting Komentar
Baca selengkapnya
 Teknik Kompilasi Pertemuan 6 1.  Tuliskan ekspresi dan tata bahasa dari pohon urai dibawah ini. Jawab : Ekspresi  :  9-5+2  Tata Bahasa :  list => list + digit list => list - digit list => digit digit => 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 2.  Jelaskan dan berikan contoh mengenai tata bahasa yang mempunyai arti ganda ... Jawab :  Suatu tata bahasa dapat disebut sebagai tata bahasa yang mempunyai arti ganda apabila, suatu tata bahasa dapat memberikan lebih dari satu pohon urai untuk membentuk suatu rangkaian token dari tata bahasa yang digunakan tersebut. Contoh :  Misalkan tidak dibedakannya antara angka dan list. Maka, tata bahasa yang melibatkan angka dan tanda plus dan minus dapat dituliskan sebagai berikut :  string -> string + string | string - string | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 .    Sehingga tata bahasa yang seperti itu akan mempunyai lebih dari satu pohon urai, yaitu sebagai berikut : G...
Posting Komentar
Baca selengkapnya
  Teknik Kompilasi Pertemuan 12 Pengertian Sintaksis Sintaksis adalah cabang ilmu linguistik yang mengkaji seluk-beluk tata bahasa dalam satuan kalimat. Pengertian tersebut sejalan dengan pendapat Ramlan (2009, hlm. 1) yang mengungkapkan bahwa sintaksis adalah bagian atau cabang ilmu bahasa yang membicarakan seluk beluk wacana, kalimat, klausa, dan frasa. Objek Kajian (Satuan) Sintaksis Seperti yang telah disebutkan sebelumnya, objek kajian sintaksis menyelimuti frasa, klausa, dan kalimat. Berikut adalah penjelasan dari masing-masing objek. Frasa Frasa adalah gabungan dua kata atau lebih yang bersifat nonpredikatif atau lazim juga disebut gabungan kata yang mengisi salah satu fungsi sintaksis di dalam kalimat (Chaer, 2003, hlm. 222). Mudahnya, frasa adalah gabungan kata yang tidak memiliki predikat (P). Agar lebih jelas, perhatikan contoh-contoh berikut. Frasa Non Frasa pisang goreng rumah besar bayi sehat ayam hitam saya pisang digoreng rumah itu besar bayi ibu sehat ayam saya hit...
Posting Komentar
Baca selengkapnya