Membuat DFA, NFA, PDA

Nama : Alan Maulana
NIm : 161021450350
Kelas : TPLM05003


assalamualaikum wr.wb
Disni saya akan menjelaskan tentang DFA , NFA ,PDA , apa si mereka itu .?
Pertama - tama saya akan membahas DFA.
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.contoh Ilustrasi graf untuk DFA Konfigurasi DFA di samping secara formal dinyatakan sebagai berikut

•       M = (Q, ∑, δ, S, F),

•       Q = {q0, q1, q2, q3}

•       ∑ = {0,1}

•       S = q1

•       F = {q3}

•       δ  =  { q0,q1,q2,q3 }

Dan berikut adalah hasil input dari DFA tersebut :

Apabila stata awal q0 diberi masukan 1 maka akan berputar di q0 (luping) dan state berikutnya di berikan masukan 0 maka akan bergerak ke state q1 dan kita masukan input 1 dia akan bergerak ke state q2 dan kita masukan lagi 1 dia akan bergerak ke state q3 dan finis tetapi dia masih ada satu state ke 0 yang di mana balik kembali ke q2 dan hasilnya pun menjadi Reject

jadi pengertiannya bila satate terakhir berapa pas di garis finis dai akan di accept dan sebalikan seperti itu

Trace 10110

Trace 1011 

Trace 1010

2.       Non-deterministic Finite Automata (NFA)

Ketentuan NFA :

•       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.

FORMAL PENULISAN

M = (Q, ∑, δ, S, F),

•       Q = {q0,q1, q2, q3}

•       ∑ = {0,1}

•       S = q0

•       F = {q1}

•       δ  = 

DIAGRAM

UJI INPUT

Apabila State awal q0 kita berikan masukan 1 maka dia akan berputar di q0 lalu kita memasukan 0 maka dia akan bergerak menuju q1,kita input kembali 1 dia akan meluping ke q1 ,masukan 0 dia bergerak ke q2 masukan 0 dia akan berputar di q2,dan masukan 1 dia akan menuju state q3 yang dimana di sana adalah finis ,dan input tersebut di accepet
Contoh Trace Dari masing - masing Input :
Trace 101001

Trace  100110

Trace 101100

3.PDA

Gambar di atas disebut diagram state M3.• Ia memiliki empat state, berlabel q0, q1, q2 dan q3.• State awal(Initial) yaitu q0, ditunjukkan oleh panah yang menunjuknya entah dari mana.• Panah yang berpindah dari satu kondisi ke kondisi lain disebut transisi.• State terima(Final) q3, dengan lingkaran ganda.
Deskripsi• M1=( Q, Σ, δ, S, F)• Q = {q0, q1, q2, q3}• Σ = {A, B}• Γ = {A, Z}• δ = {(q0, a, Z, q1, bb), (q1, b, b, q1, bb), (q1, b, a, q2, bb), (q2, a, b, q3, ab), (q3, b, a, q3, ba), (q3,a,a,q3,aa)}• S = {q0}• F = {q3}
Contoh Trace :ababa

aba

abaaba