Blog Teori Bahasa Dan Otomata tentang Finite State Otomata || Siti Nurul Maghfirah L_ 202131125

 

                                                                      Institute Teknologi PLN Jakarta

                                                            Dosen : Dine Tiara Kusuma S.T., M.Kom

Finite State Otomata

FSA (Finite State Automata) merupakan tool yang sangat berguna dalam perancangan lexical analyzer, yaitu bagian dari kompilator yang mengelompokkan karakter-karakter ke dalam sebuah token, yang berupa unit terkecil seperti nama, variabel, dan keyword. FSA dipakai untuk penganalisa leksikal dan dipakai juga dalam text editor, pemrosesan teks, dan program file-searching.

FSA atau AH (Automata Hingga) didefinisikan sebagai pasangan 5 tupel yaitu, M = (Q, ∑, δ, S, F).

Q = himpunan hingga state

∑ = himpunan hingga simbol input (alfabet)

δ = fungsi transisi, menggambarkan transisi state FSA akibat pembacaan simbol input.

Fungsi Transisi ini biasanya diberikan dalam bentuk tabel.

S ∈ Q : state awal

F ⊆ Q : Himpunan State AKHIR

• Mesin ini memiliki 6 state : (q0,q1,q2,q3,q4,q5).
• State awal q0,
• Sedangkan q3 dan q4 adalah state akhir, dan
• Simbol input adalah (a,d,u)

Contoh Finite State Automata untuk Mengecek Parity Ganjil

Keterangan :

• Q = [Gnp,Gjl]
• Σ= [0,1]
• S = Gnp
• F = Gjl

Definisi Formal Finite State Automata

Definisi Formal FSA

M = (Q, Σ, δ, S, F), dimana :

Q : Himpunan state

Σ : Abjad, Himpunan simbol input (masukan)

δ : Fungsi transisi, δ : Q x Σ => Q

S ∈ Q : State awal (Initial State)

F ⊆ Q : Himpunan state akhir (Final State)

Finite State Automata (FSA), yaitu Deterministic Finite Automata (DFA / DFSA) dan Non-Deterministic Finite Automata (NFA / NFSA).

·       Deterministic Finite Automata (DFA / DFSA) : Pada setiap input, hanya ada satu keadaan (state) tujuan dari keadaan saat ini.

·       Non-Deterministic Finite Automata (NFA / NFSA) : Pada setiap input terdapat lebih dari satu keadaan tujuan dari keadaan saat ini.

Deterministic Finite Automata (DFA / DFSA) terdiri atas 5 tupel, yaitu A = (Q, Σ, δ, Q0, F)

Notasi Lain Deterministic Finite Automata (DFA / DFSA) :

1. Diagram Transisi (State Diagram)

·       Tiap keadaan merupakan simpul,

·       Tiap keadaan q ∈ Q dan tiap simbol a ∈ Σ , dituliskan sebagai δ(q,a) = p. Artinya, diagram transisi memiliki panah dari q ke p, yang berlabel a,

·       Keadaan awal (q0) ditandai dengan adanya panah tanpa sumber,

·       Simpul yang menjadi keadaan final ditandai dengan lingkaran bergaris tepi ganda.

2. Tabel Transisi

·       Representasi daftar dari suatu fungsi,

·       Baris menunjukkan keadaan dan kolom menunjukkan input,

·       Isi dari baris menunjukkan keadaan q dan isi dari kolom input a menunjukkan keadaan δ(q,a).

Blog Teori Bahasa Dan Otomata tentang Derivasi Kalimat dan Penentuan Bahasa || Siti Nurul Maghfirah L_ 202131125

                                                                                             Institute Teknologi PLN Jakarta

                                                            Dosen : Dine Tiara Kusuma S.T., M.Kom

Derivasi Kalimat dan Penentuan Bahasa

Grammar

Grammar adalah sebagai kumpulan dari himpunan-himpunan variabel, simbol-simbol terminal, simbol awal, yang dibatasi oleh aturan-aturan produksi. Aturan produksui merupkan pusat dari grammar yang menspesifikasikan bagaimana suatu grammar melakukan transformasi suatu string atau karakter ke bentuk lainnya.

Semua aturan produksi dinyatakan dalam bentuk "ɑ => β" (bisa dibaca ɑ menghasilkan β, atau dibaca ɑ menurunkan β). ɑ merupakan simbol-simbol pada ruas kiri aturan produksi, sedangkan β merupakan simbol-simbol ruas kanan aturan produksi.

• Simbol-simbol tersebut dapat berupa simbol terminal (Vt) atau simbol NON-Terminal (Vn)/Variabel.
• Simbol Vn adalah simbol yang masih dapat diturunkan, biasanya identik dengan huruf besar (‘A’,’B’,’C’)
• Simbol Vt adalah simbol yang sudah tidak dapat diturunkan lagi, biasanya identik dengan huruf kecil (‘a’,’b’,’c’)

Dengan menerapkan aturan produksi, suatu grammar bisa menghasilkan sejumlah string.

Contoh aturan produksi :

1.    E => T | T + E | T * E

2.    T => a

Dari aturan produksi diatas, menghasilkan suatu variabel a atau variabel ekspresi a+a atau a*a.

1. E => T

    T => a

2. E => T + E

    E => a + T

    E => a + a

3. E => T * E

    E => a * T

    E => a * a

Grammar (G) di definisikan sebagai pasangan 4 tupple : Vt, Vn, S, dan Q. Dapat dituliskan sebagai G(Vt, Vn, S, dan Q) dimana :

Vt : Himpunan simbol-simbol terminal (himpunan token-token atau alfabet).

Vn : Himpunan simbol-simbol non terminal.

S : Simbol awal (simbol start).

Q : Himpunan produksi.

Derivarasi Kalimat Dan Penentuan Bahasa 

1. Tentukan bahasa dari masing-masing grammar berikut :

    G1 dengan Q1 = {1. S => aAa,    2. A => aAa,    3. A => b}

    Jawab : 

- Derivasi Kalimat Terpendek :

       S => aAa     (1)

       S => aba      (3)

    - Derivasi Kalimat Umum :

       S => aAa           (1)

       S => aaAaa       (3)

       S => aaaAaaa    (1)

       S => aaabaaa     (3)

    - Dari pola kedua kalimat disimpulkan :

    L₁(G₁) = {aⁿbaⁿ | n >= 1}

 2. Tentukan bahasa dari masing-masing grammar berikut :

    G2 dengan Q2 = {1. S => aS,    2. S => aB,    3. B => bc,    4. C => aC,    5. C => a}

    Jawab : 

    - Derivasi Kalimat Terpendek 1 :

       S => aS           (1)

       S => aaB         (2)

       S => aabC       (3)

       S => aaba        (5)

    - Derivasi Kalimat Terpendek 1 :

       S => aS           (1)

       S => aaB         (2)

       S => aabC       (3)

       S => aabaC     (4)

       S => aabaa      (5)

    - Derivasi Kalimat Umum : 

       S => aS               (1)

       S => aaS             (1)

       S => aaaS           (1)

       S => aaaaB         (2)

       S => aaaabC       (3)

       S => aaaabaC     (4)

       S => aaaabaaC   (4)

       S => aaaabaaa    (5)

    - Dari pola kedua kalimat disimpulkan : 

      L₂(G₂) = {aⁿba^m | n > 1, m >= 1}