UTS TEORI BAHHASA DAN AUTOMATA

1.     1.  Determiniatic finite automata(DFA)

ü  Sebuah state dan di input yang berlaku bisa ditentukan tepat satu state

ü  String X dinyatakan diterima,bisa δ(S,x) berada pada state akhir

ü  Bila M adalah sebuah bahasa FSA

M=(Q,∑,δ,S,F) menerima bahasa yang disebut L(M)yang merupakan impunan {x|δ(S,x) di dalam F

            Pendeskripsian format penulisan M =(Q,∑,δ,S,F)

            1. Q=(q0,q1,q2,q3)

            2. ∑= (0,1)

            3. δ = is describeed as

δ	0	1
Q0	Q0	Q1
Q1	Q2	Q1
Q2	Q3	Q2
Q3	Q0	Q3

                                                                       

               4. S=q0

               5. F=q0

Diagram :

      

Uji input

1100=diterima      1101=ditolak      0110=ditolak

10101=diterima     0100=diterima

1.      2. Non deterministic automata (NFA)

ü  Setiap state tidak selalu tepat ada satu state berikutnya untuk setiap simbol inpt yang ada

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

NFA harus di coba 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 mendeskripsikan format penlisan M=(Q,∑,δ,S,F):

         1.Q=(q0,q1,q2,q3,q4)

         2. ∑=(0,1)

         3. = is describeed as

δ	0	1
Q0	Q0	Q1,Q3
Q1	Q2	Q1
Q2	Q2	Q0
Q3	Q4	Q3
Q4	-	Q2

         

          4.S=q0 is the start state

          5.F=q3

Diagram :

Uji input:

1100=diterima                           0011=ditolak              1010=diterima

1101=diterima                           1110=diterima

3. PUSHDOWN AUTOMATA

Deskripsi :

Q = {q0, q1, q2, q3}

Σ = {a, b}

Γ = {b, Z}

δ = {(q0, b, Z, q1, bZ), (q1, b, b, q1, bb), (q1, a,b, q1, ab), (q2, b, ba, q2, b), (q2, b, ba, q2, b), (q3, a, a, q3, aa), (q3, b, a, q3, ba)}

qs= q0

F = {q3}

Diagram:

                                                      input = baabbbaa =diterima  

                                          input = baabbaab = tidak diterima

                                         input = bbaabbaa = diterima

       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.

                                                   sekian semoga bermanfaat