TEKNIK KOMPILASI




MESIN TURING , LINEAR BOUNDED AUTOMATA, PUSHDOWN AUTOMATA, FINITE STATE AUTOMATA , DFA DAN NFA


Assallamuallaikum Wr Wb
Saya Safia Rahmatulailah ingin menjelaskan beberapa materi tentang mesin turing , linear bounded automata , pushdown automata finite state automata , DFA dan NFA dari berbagai sumber .

Mesin Turing

Hasil gambar untuk mesin turing

Apakah anda tahu tentang Mesin Turing?? apaaa....tidak tahu.....
Hari gini ngak tau tentang mesin Turing..... :D sama...saya belajar dan baru cari di Om Google

Kali ini kita akan Kupas Tuntas tentang Mesin Turing


Pengertian Mesin Turing

 Ya Bisa di Bilang Mesin itu adalah Model yang sangat sederhana dari Komputer, Mesin turing itu bisa juga dibilang Sebuah Model Matematika untuk Komputasi diberikan dalam bentuk Mesin turing itu sendiri....oooh hampir lupa..Mesin Turing ditemukan oleh Alan Turing.

Nih fotonya Alan Turing....












Mesin Turing terkenal dengan ungkapan " Apapun yang bisa dilakukan oleh Mesin Turing pasti bisa dilakukan oleh komputer."

Mesin Turing adalah model komputasi teoritis yang ditemukan oleh Alan Turing, berfungsi sebagai model ideal untuk melakukan perhitungan matematis. Walaupun model ideal ini diperkenalkan sebelum komputer nyata dibangun, model ini tetap diterima kalangan ilmu komputer sebagai model komputer yang sesuai untuk menentukan apakah suatu fungsi dapat selesaikan oleh komputer atau tidak (menentukan computable function). Mesin Turing terkenal dengan ungkapan " Apapun yang bisa dilakukan oleh Mesin Turing pasti bisa dilakukan oleh komputer."
      Sebuah mesin Turing secara formal dinyatakan dalam 7 tupel, yaitu M = (Q, Î£, Î“, Î´, S, F, b)
dimana :
Q = himpunan state
Σ = himpunan simbol input
Γ = simbol pada pita (meliputi pula blank)
δ = fungsi transisi
S = state awal, S ∈ Q
F = himpunan state akhir, F⊆ Q
b = simbol kosong (blank)   bukan bagian dari Î£, b .Σ
Bagian dari pita yang belum ditulisi dianggap berisi simbol b (blank)


STUDI KASUS

A. Buatlah transisi masing-masing state seperti pada gambar berikut



B. Pseudocode Mesin Turing
Deklarasi:
Integer q0=0, q1=1, q2=2, q3=3, q4=4, q5=5, q6=6;
Boolean state_akhir = {false,false,false,false,false,false,true}
Integer state, i;
String Uji;
Char c;
Deskripsi:
Input (uji)
state = 0
i = 0;
if i < uji.length then
for i=0;i<uji.length;i++
c = uji.charAt(i)
case q0; switch(c)
case c = ‘a’ return q1
‘a’ = ‘x’
case c = ‘y’ return q4
case c=’ ’ return q6
case q1; switch(c)
case c = ‘a’ return q1
case c = ‘y’ return q1
case c = ‘b’ return q2
‘b’ = ‘y’
case q2; switch(c)
case c = ‘b’ return q2
case c = ‘z’ return q 2
case c = ‘c’ return q3
‘c’ = ‘z’
for i=0;i<uji.length;i--
c = uji.charAt(i)
case q3; switch(c)
case c = ‘a’ return q3
case c = ‘b; return q3
case c = ‘z’ return q3
case c = ‘y’ return q3
case q4; switch(c)
case c = ‘x’ return q4
case c = ‘ ‘ return q5
for i=0;i<uji.length;i++
c = uji.charAt(i)
case q5; switch(c)
case c = ‘x’ return q5
case c = ‘y’ return q5
case c = ‘z’ return q5
case c = ‘ ’ return q6
default (state_akhir = q0);
else
state_akhir{state}
output (state_akhir{state})


 
C. Flowchart Mesin Turing


D. Langkah Kerja 

1. Buka program aplikasi JFLAP.
2. Klik tabPushdown Automaton pada kotak dialog menu


3. Buatlah 6 buah state dengan transisi dan input masing-masing state seperti dibawah ini :


4. Klik menu input lalu pilih Step by BuildingBlock, kemudian masukan “aabbcc” kemudian klik OK dan enter


5. Klik Step untuk melakukan simulasi transisi langkah-demi langkah.
6. Berdasarkan hasil dari langkah di atas maka akan didapat hasil sebagai berikut





 Deskripsi Instantaneous (ID) untuk Mesin Turing

 ID digunakan untuk mengetahui apa yang mesin Turing kerjakan.  ID direpresentasikan oleh string X1X2X3… Xi-1qXiXi+1 … Xn, dimana:
  •  q adalah state dari TM
  •  Tape head men-scan simbol ke-i dari kiri.
  •  X1X2 …Xn adalah bagian dari tape di antara nonblank pada sel paling kiri dan paling kanan.
Pergerakan TM M = (Q, S, G, d, q0, B, F) dinyatakan oleh notasi ├ atau ├. ├*M atau ├* digunakan untuk menunjukkan nol, satu atau lebih pergerakan dari TM.
Anggap d(q, Xi) = (p, Y, L), yaitu pergerakan selanjutnya adalah ke kiri.  Maka
X1X2… Xi-1qXiXi+1 … Xn
├ X1X2… Xi-2pXi-1 YXi+1 … Xn
Pergerakan ini menyatakan perubahan ke state p. Tape head sekarang diposisikan di sel i-1.
Jika i = n dan Y = B maka simbol B yang ditulis pada Xn berhubungan dengan urutan tak hingga dari blank–blank yang mengikuti dan tidak muncul dalam ID selanjutnya.  Dengan demikian
X1X2 …Xn-1 q Xn├ X1X2… Xn-2p Xn-1

Terdapat dua pengecualian:
  • Jika i=1, maka M bergerak ke blank ke bagian kiri dari X1.  Dalam kasus ini,qX1X2 …Xn├ pBYX2… Xn.
  •  Jika i = n dan Y = B maka simbol B yang ditulis pada Xn berhubungan dengan urutan tak hingga dari blank–blank yang mengikuti dan tidak muncul dalam ID selanjutnya.  Dengan demikian X1X2 …Xn-1 q Xn├ X1X2… Xn-2p Xn-1 Anggap d(q, Xi) = (p, Y, R), yaitu pergerakan selanjutnya adalah ke kanan.  Maka X1X2… Xi-1qXiXi+1 … Xn ├ X1X2… Xi-1 YpXi+1 … Xn Tape head telah bergerak ke sel i+1.

Diagram Transisi untuk Mesin Turing
Diagram transisi terdiri dari sebuah himpunan dari node–node yang menyatakan state–state dari Mesin Turing .sebuah arc dari state q ke state p diberi label oleh satu atau lebih item dengan bentuk X/Y D, dimana X dan Y adalah tape symbol, dan D adalah arah, kiri (L) atau kanan (R).  Bahwa bila d(q, X) = (p, Y, D) diperoleh label X/Y D pada arc dari q ke p. Dalam diagram arah D dinyatakan dengan tanda ¬ untuk “left” dan ® untuk “right”.  Start state ditandai dengan kata “start” dan sebuah panah yang masuk ke dalam state tersebut.  Final state ditandai dengan putaran ganda.


Contoh:
Mesin Turing berikut menghitungan fungsi   , yang dinamakan monus atau proper substraction.  Fungsi ini didefinisikan oleh  m   n = max(m – n, 0).  Bahwa, m   n = m – n jika m ³ n dan 0 jika m < n.  Mesin Turing yang melakukan operasi ini adalah
M = ({q0, q1, … , q6}, {0, 1}, {0, 1, B}, d, q0, B)
Aturan untuk fungsi transisi d:
 
Diagram transisi dari mesin Turing M:

Contoh Mesin Turing Sederhana

Sebuah contoh mesin Turing dapat dibangun untuk melakukan komputasi sederhana yang didefinsikan seperti ini:
Tentukan ada berapa angka 1 dalam sebuah string berbentuk 0111...110 (rangkaian angka 1 yang didahului dengan 0 dan diakhiri juga dengan 0), apakah berjumlah genap atau berjumlah ganjil.

Jika angka 1 di antara dua angka 0 berjumlah genap, tulis sebuah angka 0 pada salah satu sel dari tape mesin Turing.

Jika angka 1 di antara dua angka 0 berjumlah ganjil, tulis sebuah angka 1 pada salah satu sel dari tape mesin Turing.
Untuk menyelesaikan masalah komputasi ini, kita buat tiga buah State bagi mesin Turing ini, yaitu Start, Even, dan Odd. Di samping itu kita buat sekumpulan aturan Transisi yang digunakan oleh
mesin Turing ini untuk melakukan proses komputasinya. Aturan-aturan Transisi tersebut dapat dituliskan demikian:
  • Jika mesin Turing berada pada status Start, dan membaca simbol 0 pada Tape, lakukan hal berikut: Pindah status menjadi status Even, Ganti simbol 0 pada Tape dengan Blank (atau Hapus simbol 0 pada Tape), dan Bergerak ke kanan satu sel.
  • Jika mesin Turing berada pada status Even, dan membaca simbol 1 pada Tape, lakukan hal berikut: Pindah status menjadi status Odd, Ganti simbol 1 pada Tape dengan Blank, dan Bergerak ke kanan satu sel.
  • Jika mesin Turing berada pada status Odd, dan membaca simbol 1 pada Tape, lakukan hal berikut: Pindah status menjadi Even, Ganti simbol 1 pada Tape dengan Blank, dan Bergerak ke kanan satu sel.
  • Jika mesin Turing berada pada status Even, dan membaca simbol 0 pada Tape, lakukan hal berikut: Pindah status menjadi Halt, Ganti simbol 0 pada Tape dengan 0, dan tetap pada sel tersebut (tidak perlu berpindah ke kiri maupun ke kanan).
  • Jika mesin Turing berada pada status Odd, dan membaca simbol 0 pada Tape, lakukan hal berikut: Pindah status menjadi Halt, Ganti simbol 0 pada Tape dengan 1, dan tetap pada sel tersebut.

Spesifikasi Mesin Turing



  • Mesin Turing memiliki pita berupa array sebagai memori yang dapat menyimpan sebuah simbol tunggal
  • Mesin Turing juga memiliki Head fungsinya Sebagai Penunjuk Posisi yang diakses oleh Pita
  • Head pada Mesin Turing juga dapat bergerak ke-kanan dan ke-kiri pada pita  sesuai fungsi transisi yang ditetapkan untuk membaca inputan
  • Head juga Mampu melakukan tugas untuk menghapus dan mengubah isi dari Pita



Prinsip Kerja Mesin Turing

  • Lihat pada State Semula dan simbol yang ditunjuk Head
  • Berdasarkan fungsi transisinya, tentukan :
           -  State Berikutnya
           -  Lakukan Penulisan ke pita
           -  Gerakan Head kekanan dan ke-kiri
  • Bila pasanan dari state dan simbol yang ditunjuk head tidak ada lagi fungsi transisinya,  berarti mesin turing berhenti.
  • Bila mesin turing berhenti pada state final (F), brarti input diterima. Sebaliknya jika mesin turing tidak berhenti pada state akhir/final(F), maka berarti inputan tersebut ditolak
 Mesin Turing dijelaskan oleh 7-tuple:
M = (Q, S, G, d, q0, B, F)
Komponen-komponennya adalah:
  •  Q:  Himpunan berhingga dari state dari finite control.
  •  S: himpunan berhingga dari simbol-simbol input.
  •  G: Himpunan dari tape symbol.  S merupakan subset dari G.
  •  d:  Fungsi transisi.  Argumen d(q, X) adalah sebuah state q dan sebuah tape symbol X.  Nilai dari d(q, X), jika nilai tersebut didefinisikan, adalah triple (p, Y, D), dimana:
  •  p adalah next state dalam Q
  •  Y adalah simbol, dalam G, ditulis dalam sel yang sedang di-scan, menggantikan simbol apapun yang ada dalam sel tersebut.
  •  D adalah arah, berupa L atau R, berturut-turut menyatakan left atau right, dan menyatakan arah dimana head bergerak.
  •  q0: start state, sebuah anggota dari Q, dimana pada saat awal finite control ditemukan.
  •  B: simbol blank.  Simbol ini ada dalam G tapi tidak dalam S, yaitu B bukan sebuah simbol input.
  •  F: himpunan dari final state, subset dari Q.
KESIMPULAN
1. Pada mesin turing memori berupa pita yang dasarnya berupa array
2. Pada mesin turing terdapat sebuah head yang menunjukan posisi yang diakses pada pita


LINEAR BOUNDED AUTOMATA

Pengertian

Linear bounded automata memiliki kemiripan dengan mesin Turing dimana sama-sama menggunakan tape, tetapi pada mesin ini adalah finite yakni terbatas.
Linear bounded automata (LBA) adalah mesin yang berdasar pada state,sebuah tape yang berisi input string, dan sebuah read/write head yang bergerak ke kiri dan ke kanan di sekitar tape.
Mesin ini membandingkan state saat ini dan simbol pada 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.
Tata bahasa tipe ini dapat direpresentasikan oleh mesin otomata
Linear Bounded Automata.
Aaac -> bBcd
aaCD -> ddCCA

Kami tidak dapat meningkatkan daya Mesin Turing dengan menyediakan beberapa opsi seperti 'TINGGAL', '2 Baca / Tulis Kepala' dll.
Tetapi kita dapat membatasi kekuatan Mesin Turing dengan cara berikut:
Jika kita menggunakan TAPE sebagai STACK maka itu akan menjadi "PDA"
Jika kita membuat TAPE terbatas, maka itu akan menjadi "Finite Automata"
Jika ukuran TAPE sama dengan ukuran input maka itu akan menjadi "LBA"

Perbedaan antara poin 2 dan 3
Untuk automata terbatas TAPE akan memiliki ukuran tetap terlepas dari ukuran input, sedangkan untuk LBA, ukuran TAPE akan bervariasi: untuk ukuran input lebih besar, TAPE lebih besar dan untuk ukuran input lebih kecil, ukuran TAPE lebih kecil.

Kekuatan LBA
LBA lebih kuat dari PDA misalnya: a n b n c n | n ≥1
tidak dapat diterima oleh PDA sedangkan itu dapat diterima oleh LBA tanpa menggunakan spasi tambahan atau simbol BLANK.
Pendekatan
Misalkan input adalah: "aaabbbccc"
Tandai 'a' sebagai 'X' dan bergerak ke kanan, tandai 'b' sebagai 'X' dan bergerak ke kanan, tandai 'c' sebagai 'X' dan bergerak ke kiri. Dan ulangi proses ini sampai semua simbol ditandai sama
Untuk klarifikasi lebih lanjut, silakan kunjungi tautan ini.

Jadi sampai sekarang kita telah melihat semua mesin di bawah ini:
Nama mesin Status Setara Deterministik dan Non-Deterministik
Automata terbatas Iya
PDA TIDAK, PDA Non-Deterministik lebih kuat
Automata Terikat Linier Tidak dapat ditentukan
Mesin Turing Iya

Contoh Standar LBA
Berikut ini adalah contoh standar dari LBA yang perlu diingat
L = {a n b n c n | n ≥1}
L = {a n! | n ≥ 0}
L = {a n | n = m 2 , m ≥ 1}, berarti n adalah kuadrat sempurna
L = {a n | n adalah prima}
L = {a n | n bukan bilangan prima}
L = {ww | w ε {a, b} + }
L = {w n | w ε {a, b} + , n ≥ 1}
L = {www R | w ε {a, b} + }

PUSHDOWN AUTOMATA

PDA adalah mesin otomata yang memiliki kendali masukan menggunakan teknik LIFO (Last In First Out), untuk menentukan apakah suatu output diterima atau tidak oleh mesin tsb. Dalam melakukan proses peneerimaan input, PDA menggunakan memory stack.

Mekanisme Cara Kerja Pushdown Automata

     Mekanisme kerja memory stack adalah menyimpan input pertama pada alamat paling bawah, input berikutnya di simpan pada alamat di atasnya, dan input terakhir di simpan pada alamat paling atas. Perintah operasi yang digunakan untuk menyimpan input pada stack adalah “push”. Sedangkan perintah operasi untuk mengeluarkan input yang telah tersimpan adalah “pop”.
Sebuah PDA dinyatakan dengan 7 Tupel:
Q = himpunan state
Σ = himpunan simbol input
T = simbol stack
Δ = fungsi transisi
S = state awal
F = state akhir
Z = top of stack

PDA memiliki 2 jenis transisi, yaitu 

  1. Ä 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.
  2. å. 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.

STUDI KASUS

Buatlah empat state dengan transisi dan input masing-masing state seperti pada gambar berikut.
Q ={q0,q1,q2,q3}
∑={a,b,Z,λ}
S= q0
F= q3
Z = top of stack



Flowchart



Langkah Kerja 
1. Buka program aplikasi JFLAP.
2. Klik tabPushdown Automaton pada kotak dialog menu



3. Buatlah 4 buah state dengan transisi dan input masing-masing state seperti dibawah ini :


4. Klik menu input lalu pilih Step With Closure, kemudian masukan “aaaabbbb” kemudian klik OK dan enter


5. Klik tab Step untuk melakukan simulasi transisi langkah-demi langkah.
6. Berdasarkan hasil dari langkah di atas maka akan didapat hasil sebagai berikut



Contoh Soal Lain
a. baabbbaa




b. bababa





Kesimpulan :

     State yang berawal di q0 akan berpindah posisi ke state yang berikutnya bila busur yang keluar sesuai dengan jalur yaitu a,z. dan di q1 terdapat panah looping dengan jalur a sehingga selama jalur panah masih a maka state akan terus berulang di q1 sampai jalur menjadi b dan panah keluar ke q2. Dan di q2 terdapat looping dengan jalur b,a sehingga akan terus berulang di q2 sampai jalur z panah keluar ke q3.
     Selain kita dapat menyimpulkan cara kerja hasil input dan output berdasarkan program yang dibuat tersebut. Kita juga mengetahui :
1. Mengerti mekanisme mesin PDA.
2. Mengerti cara kerja Pop dan Push pada Stack yang di implementasikan pada mesin PDA.
3. Setelah pembuatan beberapa state, kita jadi bias menganalisa apakah string tersebut ditolak atau tidak.

FINITE STATE AUTOMATA ,DFA dan NFA ,pribadi
Finite state automata adalah mesin abstrak berupa sistem model matematika dengan masukan dan keluaran diskrit yang dapat mengenali bahasa paling sederhana (bahasa reguler) dan dapat diimplementasikan secara nyata.
Finite State Automata (FSA) adalah model matematika yang dapat menerima input dan mengeluarkan output yang memiliki state yang berhingga banyaknya dan dapat berpindah dari satu state ke state lainnya berdasarkan input dan fungsi transisi. Finite state automata tidak memiliki tempat penyimpanan/memory, hanya bisa mengingat state terkini.
Finite State Automata dinyatakan oleh pasangan 5 tuple, yaitu:
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
Karakteristik Finite Automata
1.Setiap Finite Automata memiliki keadaan dan transisi yang terbatas.
2.Transisi dari satu keadaan ke keadaan lainnya dapat bersifat deterministik atau non-deterministik.
3.Setiap Finite Automata selalu memiliki keadaan awal.
4.Finite Automata dapat memiliki lebih dari satu keadaan akhir.
jika setelah pemrosesan seluruh string, keadaan akhir dicapai, artinya otomata menerima string tersebut.
Setiap FSA memiliki:
1.Himpunan berhingga (finite) status (state)
•Satu buah status sebagai status awal (initial state), biasa dinyatakan q0.
•Beberapa buah status sebagai status akhir (final state).
2.Himpunan berhingga simbol masukan
3.Fungsi transisi
Menentukan status berikutnya dari setiap pasang status dan sebuah simbol masukan.
Cara Kerja Finite State Automata
Finite State Automata bekerja dengan cara mesin membaca memori masukan berupa tape yaitu 1 karakter tiap saat (dari kiri ke kanan) menggunakan head baca yang dikendalikan oleh kotak kendali state berhingga dimana pada mesin terdapat sejumlah state berhingga.
Finite Automata selalu dalam kondisi yang disebut state awal (initial state) pada saat Finite Automata mulai membaca tape. Perubahan state terjadi pada mesin ketika sebuah karakter berikutnya dibaca. Ketika head telah sampai pada akhir tape dan kondisi yang ditemui adalah state akhir, maka string yang terdapat pada tape dikatakan diterima Finite Automata (String-string merupakan milik bahasa bila diterima Finite Automata bahasa tersebut).
Finite State Diagram (FSD)
Finite State Automata dapat dimodelkan dengan Finite State Diagram (FSD) dapat juga disebut State Transition Diagram. Sistem transisi adalah sistem yang tingkah lakunya disajikan dalam bentuk keadaan-keadaan (states). Sistem tersebut dapat bergerak dari state yang satu ke state lainnya sesuai dengan input yang diberikan padanya.
Fungsi Transisi (d) adalah representasi matematis atas transisi keadaan.
S = himpunan alfabet.
Q = himpunan keadaan-keadaan.
d = Q x S à Q
Finite State Diagram terdiri dari:
1.Lingkaran menyatakan state
Lingkaran diberi label sesuai dengan nama state tersebut. Adapun pembagian lingkaran adalah:
•Lingkaran bergaris tunggal berarti state sementara
•Lingkaran bergaris ganda berarti state akhir
2.Anak Panah menyatakan transisi yang terjadi.
Label di anak panah menyatakan simbol yang membuat transisi dari 1 state ke state lain. 1 anak panah diberi
label start untuk menyatakan awal mula transisi dilakukan.
Contoh FSA : pencek parity ganjil
Image
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
Dari contoh diatas, maka:
Q = {Genap, Ganjil}
Σ = {0,1}
S = Genap
F = {Ganjil }
Image
atau
δ(Genap,0) = Genap
δ(Genap,1) = Ganjil
δ(Ganjil,0) = Ganjil
δ(Ganjil,1) = Genap
Sebuah FSA dibentuk dari lingkaran yang menyatakan state:
• Label pada lingkaran adalah nama state
• Busur menyatakan transisi/ perpindahan
• Label pada busur yaitu symbol input
• Lingkaran yang didahului sebuah busur tanpa label menyatakan state awal
• Lingkaranb ganda menyatakan state akhir/ final.
Jadi sebuah mesin otomata dapat dinyatakan dalam diagram transisi, fungsi transisi dan tabel transisi.
Jenis FSA
Ada dua jenis FSA :
1. Deterministic Finite Automata (DFA) : dari suatu state ada tepat satu state berikutnya untuk setiap simbol masukan yang diterima. Deterministik artinya tertentu/sudah tertentu fungsi transisinya.
Notasi matematis DFA:
• M = nama DFA
• Q = himpunan keadaan DFA
• S = himpunan alfabet
• d = fungsi transisi
• q0 = keadaan awal
• F = keadaan akhir
M = (Q, S, d, q0, F)
Contoh : Pengujian untuk menerima bit string dengan banyaknya 0 genap, serta banyaknya 1 genap.
0011 : diterima
10010 : ditolak, karena banyaknya 0 ganjil
Diagram transisi-nya :
Image
DFA nya:
Q = {q0 , q1 , q2 , q3 }
Σ = {0,1}
S = q0
F = { q0}
fungsi transisi adalah:
Image
δ( q0,011)= δ( q2,11) =δ( q3,1)= q2  Ditolak
δ( q0,1010)= δ( q1,010) =δ( q3,10)=δ( q2,0)= q0 Diterima
Non-deterministic 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 –ε.
 dari suatu state ada 0, 1 atau lebih state    berikutnya untuk setiap simbol masukan yang diterima.
Non-Deterministic Finite Automata:
• Otomata berhingga yang tidak pasti untuk setiap pasangan state input, bisa memiliki 0 (nol) atau lebih pilihan untuk state berikutnya.
• Untuk setiap state tidak selalu tepat ada satu state berikutnya untuk setiap simbol input yang ada.
• Dari suatu state bisa terdapat 0,1 atau lebih busur keluar (transisi)
berlabel simbol input yang sama.
• Untuk NFA harus dicoba semua kemungkinan yang ada sampai
terdapat satu yang mencapai state akhir.
• Suatu string x dinyatakan diterima oleh bahasa NFA, M= (Q, _, d, S, F) bila {x | d (S,x) memuat sebuah state di dalam F}
Kedua finite automata di atas mampu mengenali himpunan reguler secara presisi. Dengan demikian kedua finite automata itu dapat mengenali string-string yang ditunjukkan dengan ekspresi reguler secara tepat.
DFA dapat menuntun recognizer(pengenal) lebih cepat dibanding NDFA. Namun demikian, DFA berukuran lebih besar dibanding NDFA yang ekivalen dengannya. Lebih mudah membangun NDFA dibanding DFA untuk suatu bahasa, namun lebih mudah mengimplementasikan DFA dibanding NDFA.  

EKUIVALENSI NF

EKUIVALENSI NFA-DFA  Ada apa dengan NFA ? konsep yang sulit diimplemen-tasikan. Komputer sepenuhnya deterministic.  Kenapa dipelajari ? Lebih dekat ke sistem nyata  Contoh : permainan catur, banyak alternatif pada suatu posisi tertentu -> nondeterministic

 DFA (Deterministic Finite Automaton) 

Deterministic Finite Automaton disingkat menjadi “DFA” dan juga biasa dikenal sebagai Deterministic Finite Acceptor (DFA), Deterministic Finite State Machine (DFSM), atau Deterministic Finite State Automaton (DFSA).
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.
Otomata berhingga deterministic atau DFA (Deterministic Finite Automata) adalah FSA(finite state automata) yang memiliki stata penerima tepat satu stata untuk setiap simbol masukan.

Contoh Kasus

Penulis memberikan contoh untuk DFA F(K,VT,M,S,Z) , dimana:
  • K = {S, A, B}
  • VT = {a, b}
  • S = {S}
  • Z = {B}
M diberikan dalam tabel berikut:




FA-TRANSISI
FA-TRANSISI

Ilustrasi graf untuk DFA F adalah sebagai berikut:




Ilustrasi graf untuk DFA F
Ilustrasi graf untuk DFA F

Apabila stata awal S diberi masukan a maka akan bergerak ke stata A, stata A diberi masukan b maka akan bergerak ke stata B (stata penerima). Yang artinya DFA tersebut apabila diberi masukan string ab maka masukan tersebut diterima. Lalu masukan apalagi yang diterima?
Bagaimana jika kita tulis DFA tersebut menggunakan Bahasa C untuk mengetahaui kalimat apa saja yang diterima.
Tulis header yang akan kita gunakan, yaitu:
1
2
#include <stdio.h>
#include <stdbool.h>
1. Pertama kita deklarisan dulu DFA sebagai integer dengan nilai 0.
1
int dfa = 0;
2. Buat fungsi pertama yaitu apabila Stata S diberi masukan a maka akan bergerak ke stata selanjutnya stata A dengan menukar nilai DFA menjadi 1 dan apabila diberi masukan selain a maka nilai DFA tetap 0.
1
2
3
4
5
6
7
void S(char c)
{
    if ( c == 'a' )
        dfa = 1;
    else
        dfa = 0; 
}
3. Buat fungsi selanjutnya yaitu apabila stata A diberi masukan b maka akan bergerak ke stata selanjutnya (stata B) dengan mengubah nilai DFA menjadi 2 dan apabila diberi masukan selain a maka nilai-nilai DFA tetap 1.
1
2
3
4
5
6
7
void Stata1(char c)
{
    if (c == 'b' )
        dfa = 2;
    else
        dfa = 1;
}
4. Fungsi terakhir adalah apabila stata B diberi masukan a maka akan kembali ke stata B dengan menukar nilai DFA menjadi 1 dan apabila diberi masukan selain a maka nilai-nilai DFA tetap 2.
1
2
3
4
5
6
7
void Stata2(char c)
{
    if (c == 'a' )
        dfa = 1;
    else
        dfa = 2;
}
5. Selanjutnya deklarasikan nilai int DFA serta string untuk menampung pergerakan sebagai nilai tukar DFA.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int diterima(char str[])
{
    int i, len = strlen(str);
   
    for ( i=0; i < len; i++) {
            if (dfa == 0)
                S(str[i]);
   
            else if (dfa == 1)
                Stata1(str[i]);
   
            else if (dfa == 2)
                Stata1(str[i]);
   
            else
                return 0;
    }
6. Buat Fungsi stata penerima, yaitu stata B (2).
1
2
3
4
5
if(dfa == 2)
        return 1;
    else
        return 0;
}
7. Buat fungsi utama untuk membaca string dan memproses string tersebut apakah diterima atau tidak berdasarkan fungsi yang telah kita buat sebelumnya.
1
2
3
4
5
6
7
8
9
10
11
int main()
{
    char str[10];
    printf("Masukan Kalimat: ");
    gets(str);
    if (diterima(str))
        printf("\nDiterima\n");
    else
        printf("Ditolak\n");
    return 0;
}
Program:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <stdio.h>
#include <string.h>
int dfa = 0;
   
void S(char c)
{
    if ( c == 'a' )
        dfa = 1;
    else
        dfa = 0; 
}
   
void Stata1(char c)
{
    if (c == 'b' )
        dfa = 2;
    else
        dfa = 1;
}
   
void Stata2(char c)
{
    if (c == 'a' )
        dfa = 1;
    else
        dfa = 2;
}
   
int diterima(char str[])
{
    int i, len = strlen(str);
   
    for ( i=0; i < len; i++) {
            if (dfa == 0)
                S(str[i]);
   
            else if (dfa == 1)
                Stata1(str[i]);
   
            else if (dfa == 2)
                Stata1(str[i]);
   
            else
                return 0;
    }
    if(dfa == 2)
        return 1;
    else
        return 0;
}
int main()
{
    char str[10];
    printf("Masukan Kalimat: ");
    gets(str);
    if (diterima(str))
        printf("\nDiterima\n");
    else
        printf("Ditolak\n");
    return 0;
}
Output 1:

Masukan Kalimat: abab
Diterima

Masukan Kalimat: baba
Ditolak
Kedua finite automata di atas mampu mengenali himpunan reguler secara presisi. Dengan demikian kedua finite automata itu dapat mengenali string-string yang ditunjukkan dengan ekspresi reguler secara tepat.
DFA dapat menuntun recognizer(pengenal) lebih cepat dibanding NDFA. Namun demikian, DFA berukuran lebih besar dibanding NDFA yang ekivalen dengannya. Lebih mudah membangun NDFA dibanding DFA untuk suatu bahasa, namun lebih mudah mengimplementasikan DFA dibanding NDFA.
RINGKASAN:
1. "DFA" ADALAH SINGKATAN DARI "DETERMINISTIC FINITE AUTOMATA" SEMENTARA "NFA" ADALAH SINGKATAN DARI "NONDETERMINISTIC FINITE AUTOMATA. "
2. KEDUANYA ADALAH FUNGSI TRANSISI AUTOMATA. DI DFA, KEADAAN YANG MUNGKIN BERIKUTNYA DITETAPKAN DENGAN JELAS SEMENTARA DI NFA, MASING-MASING PASANGAN SIMBOL NEGARA DAN MASUKAN DAPAT MEMILIKI BANYAK KEMUNGKINAN KEADAAN SELANJUTNYA.
3. NFA DAPAT MENGGUNAKAN TRANSISI STRING KOSONG SEMENTARA DFA TIDAK DAPAT MENGGUNAKAN TRANSISI STRING KOSONG.
4. NFA LEBIH MUDAH DIBANGUN SEMENTARA LEBIH SULIT UNTUK MEMBANGUN DFA.
5. PENGULANGAN DIIZINKAN DI DFA SEMENTARA DI NFA, MUNGKIN ATAU MUNGKIN TIDAK DIIZINKAN.
6. DFA MEMBUTUHKAN LEBIH BANYAK RUANG SEMENTARA NFA MEMBUTUHKAN LEBIH SEDIKIT RUANG.
7. SEMENTARA DFA DAPAT DIPAHAMI SEBAGAI SATU MESIN DAN MESIN DFA DAPAT DIBANGUN UNTUK SETIAP INPUT DAN OUTPUT, 8. NFA DAPAT DIPAHAMI SEBAGAI BEBERAPA MESIN KECIL YANG MENGHITUNG BERSAMA, DAN TIDAK ADA KEMUNGKINAN UNTUK MEMBANGUN MESIN NFA UNTUK SETIAP INPUT DAN OUTPUT. .
Sumber :


Komentar

Posting Komentar

Postingan Populer