TUGAS UTS PENGANTAR BAHASA DAN OTOMATA


1.     UTS PENGANTAR BAHASA DAN OTOMATA
          NAMA : MUHAMMAD SIDIQ  JAELANI PANGESTU

          NIM : 161021450502
          KELAS : 05TPLM003


     Deterministic Finite Automata (DFA)
Ketentuan DFA adalah dari suatu state ada tepat satu state berikutnya untuk setiap simbol masukan yang diterima.

FORMAL PENULISAN
M = (Q, ∑, δ, S, F),
       Q = {q0,q1, q2, q3}
       ∑ = {0,1}
       S = q0
       F = {q0}
       δ  = 
Q
0
1
q0
q0
q1
q1
q2
q1
q2
q0
q3
q3
q0
q1

DIAGRAM


UJI INPUT
  
 



Berdasarkan hasil dari langkah di atas maka akan didapat hasil sebagai berikut :


INPUT  : 101010 : REJECT




        


 


INPUT : 110111




      

 




      
 INPUT : 011011




 



    


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}
       δ  = 
Q
0
1
q0
q1
q2, q0
q1
q0
q1
q2
q3
q1, q2
q3
q1
q1

DIAGRAM



UJI INPUT
Berdasarkan hasil dari langkah di atas maka akan didapat hasil sebagai berikut




INPUT : 110110  : ACCEPT



      

 


  


 

111000 : ACCEPT



      




    


 

100111 : ACCEPT



       

 



    

3.PDA (Pushdown automata)

  • 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 (x, y).
  • State terima(Final) q3, dengan lingkaran ganda.
Deskripsi :

M3=( Q, Σ, δ, S, F)
Q = {q0, q1, q2, q3}
Σ = {x, y}
Γ = {x, Z}
δ = {(q0, x, Z, q1, xZ), (q1, x, x, q1, xx), (q1, y, x, q2, yx), (q2, y, y, q3, yy), (q3, x, y, q3, xy)}
S = {q0}
F = {q3}


Hasil test step by state Run diagram M3




Saya menginputkan data xxyyxyy dan hasilnya adalah accept. Transisi awal adalah x melalui state awal yaitu q0 menuju q1 dan transisi seterusnya sampai dengan transisi terakhir yaitu y dari state q2 menuju state final yaitu q3. Jadi apa bila data yang diinputkan berakhiran pada state final yaitu q3 maka hasilnya accept.

Saya menginputkan data xyyxxxyy dan hasilnya adalah accept. Transisi awal adalah x melalui state awal yaitu q0 menuju q1 dan transisi seterusnya sampai dengan transisi terakhir.

Saya menginputkan data xyyxyy dan hasilnya adalah accept. Transisi awal adalah x melalui state awal yaitu q0 menuju q1 dan transisi seterusnya sampai dengan transisi terakhir. Sama dengan DFA dan NFA bila data yang diinputkan berakhiran pada state final yaitu q3 maka hasilnya accept.
    


Comments