BAB I. PENGENALAN TEORI BAHASA DAN OTOMATA
Otomata merupakan suatu system yang terdiri atas sejumlah state, dimana state menyatakan informasi mengenai input. Namun, otomata juga dapat diartikan sebagai suatu bentuk (model matematika) dari suatu system yang dapat menerima input, menghasilkan output bisa memiliki penyimpanan sementara dan mampu membuat keputusan dalam mentransformasikan input ke output. Input pada mesin otomata dianggap sebagai Bahasa yang harus dikenali oleh mesin. Sedangkan Bahasa dapat diartikan sebagai himpunan string dari rangkaian symbol-simbol yang mempunyai makna (membentuk suatu makna). Hubungan di antara Bahasa dan otomata adalah Bahasa dijadikan sebagai input oleh suatu mesin otomata, lalu mesin otomata akan membuat keputusan yang mengindikasikan apakah input tersebut diterima atau ditolak.
Contoh penerapan Teori Bahasa dan Otomata dapat yang dapat ditemukan di kehidupan sehari-hari adalah Vending Machine. Vending Machine atau biasa dikenal dengan istilah mesin otomatis merupakan suatu untaian teknologi yang konsepnya membuat kegiatan yang sifatnya manual menjadi otomatis agar kegiatan tersebut bisa lebih cepat dan efisien. Vending machine ini juga dapat diartikan sebagai mesin yang dapat menjual kebutuhan manusia secara otomatis (tidak membutuhkan operator) sehingga pembeli dapat memilih sendiri barang yang di inginkan dengan cara menekan tombol yang tersedia. Selain itu juga ada mesin EDC (Electronic Data Capture) yang memiliki fungsi sebagai sarana penyedia transaksi dan alat pembayaran.
Pada umumnya, kita hanya mengetahui Bahasa Inggris atau Bahasa Indonesia.
Pada pengertian di atas dikatakan bahwa Bahasa adalah himpunan string dari
rangkaian symbol-simbol yang akan membetuk makna. String adalah deretan symbol
dari alpabet. String yang tidak memiliki symbol apapun disebut dengan Empty
String dan dilambangkan dengan simbol ε.
Contohnya V = {a,b,c,d} berarti string pada alpabet V adalah a, b, c, dan d.
Jumlah symbol di dalam string atau
kemunculan symbol dapat disebut dengan Panjang String. Panjang string
dilambangkan dengan |w|. Misalnya |aa| = 3, |aaab| = 4, dan | ε |= 0.
Misalnya, kita memiliki sebuah mesin sederhana yang dapat menerima input kata dalam Bahasa Indonesia. Apabila digambarkan pemodelan bahasanya akan menjadi sebagai berikut.
Gambar di atas merupakan mesin otomata yang hanya dapat menerima inputan
berupa Bahasa Indonesia, jika mesin mendapat string input :
1. ada : diterima
2. adu : diterima
3. add : ditolak
Suatu string input diterima bila mencapai state akhir (final state), biasa digambarkan dengan lingkaran ganda. Mesin ini memiliki 6 himpunan state yaitu {q0, q1, q2, q3, q4, q5}, dengan state awal adalah q0 dan state akhir adalah {q3 dan q4}. Sedangkan himpunan symbol input adalah {a,d,u}.
A. GRAMMAR DAN BAHASA
Tata Bahasa (grammar) didefinisikan sebagai kumpulan dari himpunan-himpunan variable, simbol-simbol terminal, simbol awal yang dibatasi oleh aturan produksi. Aturan produksi merupakan pusat dari grammar yang menspesifikasikan bagaimana suatu grammar melakukan transformasi suatu string atau karakter ke bentuk lainnya. Suatu aturan produksi dapat dinyatakan dalam bentuk α→β (dibaca : α menghasilkan β atau dibaca : α menurunkan β). Dimana α menyatakan simbol-simbol pada ruas kiri aturan produksi dan β menyatakan simbol-simbol pada ruas kanan aturan produksi. Beberapa istilah dalam aturan produksi adalah sebagai berikut.
² Simbol variable/nonterminal (VN) : simbol yang masih dapat diturunkan, biasanya dilambangkan menggunakan abjad capital (huruf besar), huruf Sebagai symbol awal, dan string yang tercetak miring.
² Simbol terminal (VT) : simbol yang tidak dapat diturunkan kembali, biasanya dilambangkan menggunakan abjad non-capital (huruf kecil), symbol operator, symbol tanda baca dan string yang tercetak tebal (seperti if, then, else).
² S : simbol awal (start)
² Q : himpunan produksi
Contoh penggunaan aturan
produksi adalah sebagai berikut.
² T → a 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.
B. HIRARKI CHOMSKY
Pada tahun 1959, Noam Chomsky menggolongkan tingkatan bahasa menjadi empat yang disebut sebagai Hirarki Chomsky. Penggolongan Hirarki Chomsky adalah sebagai berikut.
² Tipe 0 – Unrestricted atau Natural Languange. Memiliki aturan :
- Simbol pada ruas sebelah kiri harus minimal ada sebuah symbol Variabel.
- Tidak ada Batasan pada aturan produksinya.
Contoh : Abc → De (diterima), ABC → b (diterima), abc → GHI (ditolak)
² Tipe 1 – Context Sensitive. Memiliki aturan :
- Simbol pada ruas sebelah kiri harus minimal ada sebuah symbol Variabel.
- Panjang string pada ruas kiri ≤ panjang string pada ruas kanan |α | ≤ |β|
Contoh : Ab → DeF (diterima), CD → eF (diterima), exception : S → ε (diterima), ABC → DE (ditolak)
² Tipe 2 – Context Free. Memiliki aturan :
- Simbol pada ruas sebelah kiri harus berupa sebuah symbol Variabel.
- Tidak ada Batasan pada aturan produksinya.
Contoh : B → CDeFG (diterima), D → BcDe (diterima), a → b (ditolak)
² Tipe 3 – Regular grammar. Memiliki aturan :
- Simbol pada ruas sebelah kiri harus berupa sebuah symbol Variabel.
- Simbol pada sebelah kanan maksimal hanya memiliki sebuah symbol variable dan bila ada terletak di posisi paling kanan
Contoh : A → e (diterima), A → fgh (diterima), A → eH (diterima), C → D (diterima), A → Bc (ditolak)
CONTOH PENENTUAN HIRARKI CHOMSKY DENGAN ATURAN PRODUKSI
- A → xyz Grammar ini masuk dalam aturan produksi Natural Language, Regular Grammar, Context Sensitive, dan Context Free.
- A → B Grammar ini masuk dalam aturan produksi Natural Language, Regular Grammar, Context Sensitive, dan Context Free.
- S → aZ Grammar ini masuk dalam aturan produksi Natural Language, Regular Grammar, Context Sensitive, dan Context Free.
- SATU → Bangsa Grammar ini masuk dalam aturan produksi Natural Language dan Context Sensitive.
- banGsa → satu Grammar ini masuk dalam aturan produksi Natural Language.
- a → B Grammar ini masuk dalam aturan produksi Natural Language, Regular Grammar, Context Sensitive, dan Context Free.
- Diketahui G1 : Vt = {I, want, need, You}, Vn = {S, A, B, C}, P = {S → ABC, A → I, B → want | need, C → YOU} S → ABC, maka Bahasa yang dapat di bentuk dari grammar di atas adalah : I need You dan I want You.
NOTED :
- Jika di sebelah kiri tidak ada symbol terminal, maka otomatis tidak dapat masuk ke dalam aturan produksi mana saja. Misal satu → NUSA.
- Jika sudah masuk ke aturan Regular Grammar maka otomatis masuk ke aturan produksi mana saja.
- Jika masuk ke aturan produksi Context Sensitive, sudah pasti masuk ke Natural Languange.
C. DERIVASI KALIMAT
DAN PENENTUAN BAHASA
Tentukan bahasa dari masing-masing gramar berikut :
G3 dengan Q3 = { 1. S → aSBC, 2. S → abC,
3. bB → bb, 4. bC → bc, 5. CB → BC, 6. cC → cc}. Tentukan Pola kalimatnya!
Penyelesaian :
² Derivatif kalimat terpendek
S → abC (2)
S → abc (4)
² Derivatif kalimat terpanjang
S → aSBC (1)
aaSBCBC (1)
aaabCBCBC (2)
aaabBCCBC (5)
aaabBCBCC (5)
aaabBBCCC (5)
aaabbBCCC (3)
aaabbbCCC (3)
aaabbbcCC (4)
aaabbbccC (6)
aaabbbccc (6)
BAB II. FINITE STATE OTOMATA
Finite State Automata atau yang dikenal dengan istilah FSA merupakan suatu model mesin otomata dari bahasa reguler. Suatu Finite State Automata dapat memiliki state banyak berhingga yang dapat berpindah-pindah dari suatu state ke state lainnya. FSA dapat disebut juga dengan AH (Automata Hingga) didefinisikan sebagai pasangan 5 tupel, yaitu :
² Q : Himpunan State.
² ∑ : Himpunan hingga simbol input (alfabet), biasanya berada di antara state satu dengan state lainnya, di posisi tanda panah.
² δ : fungsi transisi, menggambarkan transisi state. Transisi state berarti berpindahnya suatu nilai input dari satu state ke state lainnya. Fungsi ini biasanya dalam bentuk table (diagram transisi).
² S Î Q : Himpunan state AWAL (ditandai dengan panah)
² F Í Q : Himpunan state AKHIR (ditandai dengan *)
Contoh penerapan Finite State Automata adalah untuk Pengecek parity ganjil.
² Diagram Transisi
² Tabel Transisi
|
A |
0 |
1 |
|
Gnp |
Gnp |
Gjl |
|
Gjl |
Gjl |
Gnp |
Sehingga di ketahui :
- Q ={Gnp, Gjl} - S = Gnp
- ∑ = {0,1} - F = Gjl
A. DETERMINISTIC FINITE STATE AUTOMATA (DFA)
Deterministic Finite State Automata berarti pada setiap input, hanya ada satu keadaan (state) tujuan dari keadaan saat ini. Berikut adalah notasi dari Deterministic Finite State Automata (DFA).
² Diagram Transisi (State Diagram)
- Tiap keadaan merupakan simpul
- Tiap keadaan q Î Q dan tiap simbol a Î S, dituliskan sebagai d (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.
² 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 d (q,a).
CONTOH 1 .
2. DIKETAHUI
- Σ = {0,1} - Q = {a, b, c, d} - S = {a} • F = {b, c}
- Fungsi transisi δ : Q x Σ → Q,
|
d |
0 |
1 |
|
a |
b |
d |
|
b |
c |
d |
|
c |
d |
c |
|
d |
a |
b |
penyelesaian :
SRING INPUT :
² 11010
(a,11010)
(d,1010)
(b,010)
(c,10)
(c,0)
(d,e) – karena tidak berhenti di b atau c, maka 11010 tidak diterima oleh
mesin DFA.
² 11100
(a, 11100)
(d, 11100)
(b,100)
(d,00)
(a,0)
(b,e) – karena berhenti di b maka 11100
diterima oleh mesin DFA.
² 11111
(a,11111)
(d,1111)
(b,111)
(d,11)
(b,1)
(d,e) – karena tidak berhenti di b atau c, maka 11010 tidak diterima oleh
mesin DFA.
² 00001
(a,00001)
(b,0001)
(c,001)
(d,01)
(a,1)
(d,e) – karena tidak berhenti di b atau c, maka 00001 tidak diterima oleh
mesin DFA.
² 00110
(a,00110)
(b,0110)
(c,110)
(c,10)
(c,0)
(d,e) – karena tidak berhenti di b atau c, maka 00001 tidak diterima oleh mesin DFA.
- Diagram transisi
B. NON - DETERMINISTIC FINITE STATE AUTOMATA (DFA)
Non - Deterministic Finite State Automata (DFA) berarti pada setiap input terdapat lebih dari satu keadaan tujuan dari keadaan saat ini.
CONTOH.
C. EKUIVALENSI ANTAR DFA
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. Useless State adalah state yang memberikan nilai input ke state lain namun tidak menerima input dari state manapun. Hasil dari FSA yang direduksi merupakan ekivalensi dari FSA semula. Ada 2 istilah yang digunakan yaitu sebagai berikut.
- Distinguishable, berarti dapat dibedakan.
- Indistinguishable, berarti tidak dapat dibedakan.
Pasangan state dikelompokkan berdasarkan istilah diatas.
- Jika state berpasangan dengan final state maka berstatus distinguishable.
- Jika pasangan berstatus distinguishable maka pasangan tersebut tetap berstatus distinguishable.
- Jika pasangan tersebut belum terdefenisi maka keep sampai menemukan status atau hingga selesai. Namun jika sampai proses selesai salah satunya distinguishable maka statusnya distinguishable. Dan jika belum terdefenisi juga atau keduanya berstatus indistinguishable maka statusnya dapat ditulis sebagai indistinguishable.
CONTOH.
- State q5 tidak dapat dicapai dari state awal dengan jalan apapun (useless state), maka state q5 dihapus.
- Input yang tersedia adalah 0 dan 1.
- Final state berada di q3 dan q4
- State-state distinguishable, yaitu : q4 Î F sedang q0, q1, q2, q3 ÏF. Sehingga dapat diketahui bahwa pasangan-pasangan state yang dapat dicari adalah :
² (q0,q1) Distinguishable
² (q0,q2) Distinguishable
² (q0,q3) Distinguishable
² (q0,q4) Distinguishable
² (q1,q2) Indistinguishable
² (q1,q3) Distinguishable
² (q1,q4) Distinguishable
² (q2,q3) Distinguishable
² (q2,q4) Indistinguishable
² (q3,q4) Distinguishable
penyelesaian :
- 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) = q2 dan δ(q1, 1) = q3 ➔ (q2 , q3) Distinguisable
² Pasangan (q0,q2)
➢ δ(q0, 0) = q1 dan δ(q2, 0) = q2 ➔ (q1 , q2) belum terdefinisi
➢ δ(q0, 1) = q2 dan δ(q1, 1) = q4 ➔ (q2 , q4) Distinguisable
² Pasangan (q0,q3)
➢ δ(q0, 0) = q1 dan δ(q3, 0) = q2 ➔ (q1 , q2) belum terdefinisi
➢ δ(q0, 1) = q2 dan δ(q3, 1) = q3 ➔ (q2 , q3) Distinguisable
² Pasangan (q1,q2)
➢ δ(q1, 0) = q2 dan δ(q2, 0) = q2 ➔ (q2 , q2) belum terdefinisi
➢ δ(q1, 1) = q3 dan δ(q2, 1) = q4 ➔ (q3 , q4) belum terdefinisi
² Pasangan (q1,q3)
➢ δ(q1, 0) = q2 dan δ(q3, 0) = q3 ➔ (q2 , q3) Distinguisable
➢ δ(q1, 1) = q3 dan δ(q3, 1) = q3 ➔ (q3 , q3) belum terdefinisi
² Pasangan (q1,q4)
➢ δ(q1, 0) = q2 dan δ(q4, 0) = q4 ➔ (q2 , q4) Distinguisable
➢ δ(q1, 1) = q3 dan δ(q4, 1) = q4 ➔ (q3 , q4) belum terdefinisi
² Pasangan (q2,q3)
➢ δ(q2, 0) = q2 dan δ(q3, 0) = q3 ➔ (q2 , q3) Distinguisable
➢ δ(q2, 1) = q4 dan δ(q3, 1) = q3 ➔ (q4 , q3) belum terdefinisi
² Pasangan (q2,q4)
➢ δ(q2, 0) = q2 dan δ(q4, 0) = q4 ➔ (q2 , q4) Distinguisable
➢ δ(q2, 1) = q4 dan δ(q4, 1) = q4 ➔ (q4 , q4) belum terdefinisi
² Pasangan (q3,q4)
➢ δ(q3, 0) = q3 dan δ(q4, 0) = q4 ➔ (q3 , q4) belum terdefinisi
➢ δ(q3, 1) = q3 dan δ(q4, 1) = q4 ➔ (q3 , q4) belum terdefinisi
Setelah semua pasangan state dipasangkan dengan setiap input yang ada maka terdapat state-state yang Distinguishable yaitu : (q0,q1) (q0,q2) (q0,q3) (q1,q3) (q1,q4) (q2,q3) (q2,q4). Karena berdasarkan relasi-relasi yang ada, tidak dapat dibuktikan (q1, q2) dan (q3, q4) distinguishable, sehingga disimpulkan pasangan-pasangan state tersebut indistinguishable.
Karena q1 indistinguishable dengan q2 dan q3 indistinguishable q4 maka hasil dari DFA yang direduksi menjadi :
Komentar
Posting Komentar