Tugas 3- Teori Bahasa Automata

Diagram Finite State Automata (DFSA)


1. Ada sebuah mesin dengan dengan tabel transisi seperti gambar dibawah!! Mesin tersebut diberi saja nama M sehinngah :
M = {Q, ∑, ∂,S,F}
Q = {Q0, Q1, Q2}
∑ = {X,Y}
S=  Q0
F = Q1

- Kondisi Diagram (state Diagram) yang terjadi dimana masi identik dengan tabel transisi diatas sebagi berikut :



Berdasarkan Tabel Transisi maupun stste diagram disamping, bila diberi input string xxxyyxy maka :

(Q0,xxxyyxy)   ├M (Q0,xxyyxy)
                        ├M (Q0,xyyxy)
                        ├M (Q0,yyxy)
                        ├M (Q1,yxy)
                        ├M (Q0,xy)
                        ├M (Q0,y)
                        ├M (Q1,e)
Karena (Q0,xxxyyxy) ├*M (Q1,e), jadi string xxxyyxy diterima oleh mesin M




2. Diketahui sebuah mesin M memiliki  Q = {Q0, Q1, Q2}, ∑ = {0,1}, S = {Q0}, F = { Q1} dan diberi  input string 101010 dan 110011 serta mempunyai tabel transisi seperti gambar berikut! maka :

   - Untuk Inputan string 101010 :
      oleh karena start di Q0 maka :
      (Q0,101010)  ├M (Q1,01010)
                             ├M (Q3,1010)
                             ├M (Q2,010)
                             ├M (Q0,10)
                             ├M (Q1,1)
                             ├M (Q0,e)
Karena (Q0,101010) ├*M (Q0,e), maka string 101010 ditolak oleh mesin M disebabkan Finish tidak sesuai, dimana yang seharusnya berhenti di Q1




- Untuk Inputan string 110011 :   oleh karena start di Q0 maka :
   (Q0,110011)    ├M (Q1,10011)
                           ├M (Q0,0011)
                           ├M (Q2,011)
                           ├M (Q0,11)
                           ├M (Q1,1)
                           ├M (Q0,e)
Karena (Q0,110011) ├*M (Q0,e), maka string 110011 juga ditolak oleh mesin M dengan alasan yang relevan dengan inputan string sebelumnya.

State Diagramnya adalah sebagai berikut :

SEKIAN!!!!