Teori Bahasa dan Otomata

Tugas 3 - DFSA/DFA

T = ({Q},{∑},δ,S,f)

Dimana

Q = (q0,q1,q2)

∑= a,b

S = q0

F = q1

Ditanya :      1. Buatlah tabel transisinya

                     2. Bacalah input    a = abbabbaaa

                                                   b = bbbabbaa

                                                              c = ab

Penyelesaian:

1.      Tabel Transisi

	δ	a	b
→	q0	q0,q2	q1
*	q1	q1,q2	q1
	q2	-	q0,q1

2.      a. Jika T diberi input abbabbaaa dengan State awal (q0, abbabbaaa)

      maka :

               q0, abbabbaaa   ┣ T (q0, bbabbaaa)

                                          ┣ T (q1, babbaaa)

                                          ┣ T (q1, abbaaa)

                                          ┣ T (q2, bbaaa)

                                          ┣ T (q1,baaa)

                                          ┣ T (q1,aaa)

                                          ┣ T (q1,aa)

    ┣ T (q1,a)

                               ┣ T (q1,e)

                                  Karena (q0, abbabbaaa) ┣ * T jadi abbabbaaa diterima T

         b. Jika T diberi input bbbabbaa dengan State awal(q0, bbbabbaa)

              maka :

             q0, bbbabbaa   ┣ T (q1,bbabbaa)

                                      ┣ T (q1,babbaa)

                                      ┣ T (q1,abbaa)

                                      ┣ T (q2,bbaa)

                                      ┣ T (q0,baa)

                                      ┣ T(q1,aa)

                                      ┣ T(q1,a)

                                                                        ┣ T (q1,e)

                                  Karena (q0,bbbabbaa) ┣ * T jadi bbbabbaa diterima T

          c. Jika T diberi input ab dengan State awal (q0,ab)

              Maka :

              q0, ab  ┣ T (q0,b)

                          ┣ T (q1,e)

                           Karena (q0,ab) ┣ * T jadi ab diterima T