Ekuivalensi Antar Deterministic Finite Automata || Nur Anisah Fadhilah - 202131020

                                                                                                      Institut Teknologi PLN Jakarta

Dosen : DINE TIARA KUSUMA, S.T., M.Kom

EKUIVALENSI ANTAR DETERMINISTIC FINITE AUTOMATA

Sasaran kita disini adalah mengurangi jumlah state dari suatu Finite State Automata, dengan tidak mengurangi kemampuannya semula untuk menerima suatu bahasa. Ada dua istilah baru yang perlu kita ketahui yaitu : 

1. Distinguishable, artinya berarti dapat dibedakan.

2. Indistinguishable, artinya berarti tidak dapat dibedakan.

Reduksi Jumlah State Pada FSA

Reduksi dilakukan untuk mengurangi jumlah state tanpa mengurangi kemampuan untuk menerima suatu bahasa seperti semula (efisiensi). State pada FSA dapat direduksi apabila terdapat Useless State. Hasil dari FSA yang direduksi merupakan ekuivalensi dari FSA semula.

Pasangan State dapat dikelompokkan berdasarkan :

1. Distinguishable State (dapat dibedakan)

• Dua state p dan q dari suatu DFA dikatakan indistinguishable apabila :
•  δ(q,w) ∈ F dan δ(p,w) ∈ F atau δ(q,w) ∉ F dan δ(p,w)  ∉ F
•  Untuk semua w ∈ S*

2. Indistinguishable State (tidak dapat dibedakan)

• Dua state p dan q dari suatu DFA dikatakan distinguishable jika ada string w ∈ S* hingga :
• δ(q,w) ∈ F  dan δ(p,w)  ∉ F

Reduksi Jumlah State Pada FSA - Relasi

Pasangan dua buah state memiliki salah satu kemungkinan : distinguishable atau indistinguishable, tetapi tidak kedua-duanya. Dalam hal ini terdapat sebuah relasi :

Jika p dan q indistinguishable, dan q dan r indistinguishable maka p, r indistinguishable dan p,q,r indistinguishable.

Dalam melakukan evaluasi state, didefinisikan suatu relasi : Untuk Q yang merupakan himpunan semua state.

• D adalah himpunan state-state distinguishable, dimana D ⊂ Q
• N adalah himpunan state-state indistinguishable, dimana N ⊂ Q
• maka, x ∈ N jika x ∈ Q dan x ∉ D

Contoh :

Lakukan Reduksi state pada DFA dibawah ini?

1. State q5 tidak dapat dicapai dari state awal dengan jalan apapun (useless state).  Hapus state q5.

2. Catat state-state distinguishable, yaitu : q4 ∈ Fsedang q0, q1, q2, q3 ∉ sehingga pasangan-pasangan state :

(q0, q1)

(q0, q2)

(q0, q3)

(q0,q4)

(q1,q2)

(q1,q3)

(q1,q4)

(q2,q3)

(q2,q4)

(q3,q4)

3. Reduksi jumlah state pada FSA - Step

Pasangan state :

(q0, q1)

(q0, q2)

(q0, q3)

(q0, q4) => Distuingishable

(q1, q2)

(q1, q3)

(q1, q4) => Distuingishable

(q2, q3)

(q2, q4) => Distuingishable

(q3, q4) => Distuingishable

4. Cari status pasangan lainnya, dengan memperhatikan inputan yang tersedia yaitu 0 dan 1 :

Pasangan (q0, q1)

• δ(q0, 0) = q1 dan  δ(q1, 0) = q2,  => (q1, q2) belum terdefinisi
• δ(q0, 1) = q3 dan δ(q1, 1) = q4, => (q3, q4) Distinguishable
• Maka (q0, q1) adalah Distinguishable

Finite State Otomata || Nur Anisah Fadhilah - 202131020

                                                                                                   Institut Teknologi PLN Jakarta

Dosen : DINE TIARA KUSUMA, S.T., M.Kom

FINITE STATE OTOMATA

Finite State Automata (FSA)

Finte State Automata merupakan tool yang sangat berguna dalam perancangan lexical analyzer, yaitu bagian dari kompilator yang mengelompokkan karakter - karakter kedalam 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

• Finite State Automata (FSA) atau Automata Hingga (AH) di definisikan sebagai pasangan 5 tupel => M = (Q, Σ, δ, S, F), dimana : 

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

Pada gambar FSA dibawah : 

1. Mesin ini memiliki 6 state yaitu (q0, q1, q2, q3, q4, q5)
2. State awal yaitu q0
3. Sedangkan state akhir yaitu q3, q
4. Simbol input adalah (a, d, u)

Contoh Finite State Automata (FSA) Untuk Mengecek Parity Ganjil 

Keterangan :

• Q : { Gnp, Gjl }
• Σ : { 0, 1 }
• S : Gnp
• F : Gjl

Digram Transisinya :

Definisi Formal Finite State Automata

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).

Grammar Dan Bahasa || Nur Anisah Fadhilah - 202131020

Institut Teknologi PLN Jakarta

Dosen : DINE TIARA KUSUMA, S.T., M.Kom

GRAMMAR DAN BAHASA

Grammar

Grammar adalah sebagai kumpulan dari himpunan-himpunan variabel, simbol-simbol terminal, simbol awal, yang dibatasi oleh aturan-aturan produksi. Aturan Produksi merupakan pusat 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/Variabel (Vn).
• Simbol Vn adalah simbol yang masih dapat diturunkan, biasanya identik dengan huruf besar/kapital 'A', 'B', 'C'.
• Simbol Vt adalah simbol yang sudah tidak dapat diturunkan, 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}

 

Teori Bahasa Dan Otomata serta Hirarki Chomsky || Nur Anisah Fadhilah - 202131020

 

Institut Teknologi PLN Jakarta

Dosen : DINE TIARA KUSUMA, S.T., M.Kom

PENJELASAN TEORI BAHASA DAN OTOMATA SERTA HIRARKI CHOMSKY

Bahasa 

Bahasa disebut sebagai rangkaian simbol - simbol yang mempunya makna.

Otomata 

• Otomata merupakan suatu sistem yang terdiri atas sejumlah state, di mana state menyatakan informasi mengenai input.
• Otomata juga dianggap sebagai mesin otomatis (bukan mesin fisik) yang merupakan suatu model matematika dari suatu sistem yang menerima input dan menghasilkan output

Bahasa & Otomata 

Hubungan di antara bahasa dan otomata adalah bahasa dijadikan sebagai input oleh suatu mesin otomata. Selanjutnya mesin otomata akan membuat keputusan yang mengindikasikan apakah input itu diterima atau ditolak. 

Penjelasan : 

• Sebuah string input diterima bila mencapai state akhir (final state) yang ada pada contoh disamping digambarkan dengan lingkaran ganda.
• Mesin ini memiliki 6 state yaitu q0, q1, q2, q3, q4, q5. State awal yaitu q0. q3 dan q4 adalah state akhir, sedangkan simbol input nya yaitu a,  d, u. 

1. ada : diterima
2. adu : diterima
3. add : ditolak

Konsep Teori Bahasa & Otomata 

• Teori Bahasa adalah konsep-konsep pada "string alpabet - dalam penyambungan karakter-karakter alpabet untuk membentuk suatu makna (bahasa).
• Alpabet adalah himpunan simbol (karakter) tidak kosong dan berhingga Alpabet dilambangkan dengan Zigma.
• String adalah deretan simbol dari alphabet dimana perulangan simbol diijinkan.

Contoh : 

V = (a, b, c, d)

String pada alpabet V antara lain -> "a", "abcd", "bbba".

• Panjang String adalah jumlah simbol di dalam string bukan pada alpabet dan pengulangan. Kemunculan simbol dihitung.

Contoh :

|c| = 0

|a| = 1

|aa| = 2

|aaa| = 3

|aaab| = 4

• Empty String (null string) adalah string yang tidak mengandung simbol apapun. Lambang nya ɛ atau 𝛌.

• Regular Expression adalah cara untuk mengekspresikan bahasa dengan hanya menggunakan operasi :

- Concatenation (Penyambungan)

  Contoh : 'a' o 'b' = 'ab'

- Superscript (Perkalian)

  Contoh : V o V = VV = V2

- Kleene Closure (String Tanpa Simbol)

  Contoh :

  ɛ mempunyai sifat identitas, yaitu :

  ɛ o x = x

  x o ɛ = x

- Positif Closure (Tidak Ada String Kosong Didalamnya)

  Vt = V1 U V2 U V3 U ......

Hirarki Chomsky

Secara umum tata bahasa dirumuskan sebagai berikut :

ɑ => β, yang berarti ɑ menghasilkan β, atau ɑ menurunkan β.

• Simbol Variabel (Non Terminal) adalah simbol yang masih bisa diturunkan dan ditandai dengan huruf besar seperti A, B, C, dst.
• Simbol Terminal adalah simbol yang sudah tidak bisa diturunkan dan ditandai dengan huruf kecil seperti a, b, c, dst.

Contoh Aturan Produksi

- T => ɑ

dibaca "T menghasilkan a"

- E => T | T + E

dibaca "E menghasilkan T" atau "E menghasilkan T dan E"

- Simbol | menyatakan 'atau', digunakan untuk mempersingkat penulisan aturan produksi yang mempunyai ruas kiri yang sama.

• Tipe 0 / Unrestricted / Natural Language

Aturan :

- Simbol pada ruas sebelah kiri harus minimal ada sebuah simbol variabel.

- Tidak ada batasan pada aturan produksinya.

Contoh :

Abc => De (diterima)

ABC => b (diterima)

abc => GHI (ditolak, karena simbol pada sebelah kiri tidak ada sebuah simbol variabel)

• Tipe 1 / Konteks Sensitive

Aturan :

- Simbol pada ruas sebelah kiri harus minimal ada sebuah simbol variabel.

- Panjang string pada ruas kiri <= panjang string pada ruas kanan. |ɑ| <= |β|.

Contoh :

Ab => DeF (diterima)

CD => eF (diterima)           exception : S => ɛ (diterima)

ABC => DE (ditolak, karena jumlah simbol pada ruas sebelah kiri lebih banyak dari jumlah simbol pada ruas kanan)

• Tipe 2 / Bebas Konteks / Context Free

Aturan :

- Simbol pada sebelah kiri harus berupa sebuah simbol variabel

Contoh :

B => CDeFG (diterima)

D => BcDe (diterima)

a => b (ditolak, karena simbol pada sebelah kiri harus berupa sebuah simbol variabel)

• Tipe 3 / Reguler Aturan

Aturan :

- Simbol pada sebelah kiri harus berupa sebuah simbol variabel

- Simbol pada sebelah kanan maksimal hanya memiliki sebuah simbol variabel dan bila ada terletak di posisi paling kanan.

Contoh :

A => e (diterima)

A => fgh (diterima)

A => eH (diterima)

C => D (diterima)

A => Bc (ditolak, karena simbol variabel pada sebelah kanan harus berada pada posisi paling kanan)