UTS TEORI BAHASA DAN AUTOMATA


 Assalamu'alaikum Warahmatullahi Wabarakaatuh

 Haiii guys... hari ini saya membuat blogger tentang Teori Bahasa dan Automata, disini saya   membuat 3 jenis mesin abstrak yaitu Deterministic Finite Automata (DFA), Non Deterministic Automata (NFA) dan PushDown Finite Automata (PDFA).

1.  Deterministic Finite Automata (DFA)

 ·      Sebuah state dan di input yang berlaku bisa ditentukan tepat satu state
 ·      String x dinyatakan diterima, bila δ (S,x) berada pada state akhir
 ·      Bila M adalah sebuah bahasa FSA
 M = (Q,∑,δ,S,F) menerima bahasa yang disebut L(M) yang merupakan
 himpunan {x | δ(S,x) di dalam F}

      Saya akan meng Deskripsikan format penulisan M = (Q,∑,δ,S,F) :
  1. Q = (q0,q1,q2,q3) 
  2. ∑ = (0,1)
  3. δ = is describeed as 
  4. S = q0 is the start state
  5. F = q0

      Diagram :

     
      Uji Input :

      11010 = di tolak
      10101 = di tolak
      01010 = di tolak 
      0101   = di terima
      1010   = di terima


2.  Non Deterministic Automata (NFA)

 ·      Setiap state tidak selalu tepat ada satu state berikutnya untuk setiap simbol input yang ada

 ·      Suatu state bisa terdapat 0,1 / lebih busur keluar (trasnsisi) berlabel simbol input yang  sama

 ·      NFA harus dicoba semua dan yang ada sampai terdapat satu yang mencapai state akhir
 ·      String x dinyatakan diterima bahasa FSA, M = (Q,∑,δ,S,F)
 bila {x | δ(S,x) memuat sebuah state di dalam F}
 
     Saya akan meng Deskripsikan format penulisan M = (Q,∑,δ,S,F) :
  1. Q = (q0,q1,q2,q3,q4) 
  2. ∑ = (0,1)
  3. δ = is describeed as 


  4. S = q0 is the start state
  5. F = q3 



     
      Diagram :
       


   
      Uji Input :

      01011 = di terima
      10011 = di terima
      10111 = di terima
      00011 = di terima
      11111 = di tolak

  3.   PushDown Automata (PDA)

·       Definisi : PDA adalah pasangan 7 tuple M = (Q, Σ, , q 0 , Z 0 , δ, A),

dimana : Q : himpunan hingga stata, Σ : alfabet input, : alfabet stack, q 0 ∈ Q : stata awal, Z 0       ∈ : simbol awal stack, A ⊆ Q : himpunan stata penerima,

fungsi transisi δ : Q × (Σ ∪ {ε}) ×    → 2 Q ×   *  (himpunan bagian dari Q ×   *)
·      Untuk stata q ∈ Q, simbol input a ∈ Σ, dan simbol stack X∈ , δ(q, a, X) = (p, α) berarti : PDAbertransisi ke stata p dan mengganti X pada stack dengan string α.
·         Konfigurasi PDA pada suatu saat dinyatakan sebagai triple (q, x, α), dimana :
q ∈ Q : stata pada saat tersebut, x ∈ Σ* : bagian string input yang belum dibaca, dan α ∈ * : string yang menyatakan isi stack dengan karakter terkiri menyatakan top of stack.
·      Misalkan (p, ay, Xβ) adalah sebuah konfigurasi, dimana : a ∈ Σ, y ∈ Σ*, X ∈ , dan β ∈ *. Misalkan pula δ(p, a, X) = (q, γ) untuk q ∈ Q dan γ ∈ *. Dapat kita tuliska
bahwa : (p, ay, Xβ) ⇒ (q, y, γβ).

     Saya akan meng Deskripsikan format penulisan M = (Q,Ꞅ,∑,δ,S,F) :
     
     Q = (q0,q1,q2,q3,q4)  
     ∑ = (a,b)
      δ = {(q0,a,z,q1,aZ),(q1,a,a,q1,aa),(q1,b,a,q,-),(q2,b,a,q2,-),(q2,b,Z.q3,Z),(q3,b,Z,q3,Z)}
      Ꞅ = (a,Z)
       S = q0
       F = q3 

       Diagram :
       

 
      Uji Input :
        
  
     
    View Trace :
  
    


     
  Simulasi :

 





         






      





     Sekian dan Terimakasih

Komentar

Posting Komentar