FINITE STATE AUTOMATA & GRAMMER

NAMA  : FERDIAN PUTRA DINANDA

NIM      : 161021450161

KELAS : 05TPLE003 (Regular C)

SEKOLAH TINGGI MANAJEMEN INFORMATIKA DAN KOMPUTER ERESHA

UTS BAHASA & AUTOMATA

1. FINITE STATE AUTOMATA

    Didefinisikan sebagai pasangan 5 tupel : (Q, Σ, δ, S, F).

      Q : Himpunan hingga state.

      Σ : Himpunan hingga simbol input (alfabet).

      δ : Fungsi transisi, menggambarkan transisi FSA akibat pembacaan simbol input.

      S : State AWAL.

      F : Himpunan state AKHIR.

Contoh FSA : 

     Q : {q0, q1, q2, q3, q4, q5}

     Σ : {0,1}

     δ :

   S : {q0}

   F : {q4}

CONTOH GAMBAR FSA

TEST FSA

                                           1011010 : Accept

                                           1101011 : Reject

                                           1100110 : Reject

                                           1010110 : Accept

                                           1011101 : Reject

2. GRAMMER

    didefinisikan sebagai 4 tupel : VT, VN, S dan Q 

• VT : Himpunan simbol-simbol terminal.
• VN : Himpunan simbol-simbol non terminal.
• S    : Simbol AWAL (atau simbol start).
• Q    : Himpunan produksi.

       G1 : VT = {a,b}

               VN = {S, A, B, C, D, E} 

                 S = {q0}

                Q = D -> aD | S -> aS | C -> aE | C -> bD | D -> bE | D -> aC | C -> bB | B -> aC |

                       S -> bA | D -> aA | A -> aC|

CONTOH GAMBAR

TEST GRAMMER

                                               abababa = Reject

                                               bababab = Accept

                                               aababba = Reject

                                               ababaab = Accept

                                               babaaba = Reject