Teori Bahasa Dan Otomata
Pengertian Automata
Teori
otomata mempelajari tentang mekanisme komputer abstrak atau mesin
abstrak. Jauh sebelum ada komputer, tahun 1930, Alan Turing mempelajari
mesin abstrak yang punya kemampuan seperti komputer sekarang, dikenal
dengan nama Mesin Turing. Tujuan Turing adalah menggambarkan secara
jelas apa yang dapat dan yang tidak dapat dilakukan mesin komputing. Kemudian
pada tahun 1940 an dan 1950-an, ditemukan mesin abstrak yang lebih
sederhana, yaitu “finite automata”. Automata ini, asalnya diperuntukkan
untuk membentuk fungsi kecerdasan, berubah secara drastis untuk
keperluan lain yang sangat beragam. Tahun 1950-an juga Chomsky
mempelajari tentang “tata bahasa” formal, yang sangat berguna untuk
pengembangan compiler.
Semua pengembangan teori ini secara langsung melahirkan ilmu-ilmu komputer yang sekarang ini. Beberapa
konsepnya, seperti “Finite Automata” dan “grammar”, digunakan untuk
perancangan dan pembuatan bermacam software penting, seperti Pascal dan
C. Konsep lainnya, seperti Mesin Turing, membantu kita memahami apa yang dapat kita harapkan dari perangkat lunak kita.
Kedudukan Teori Bahasa dan Otomata
Ilmu
komputer mempunyai dua komponen utama, pertama : model dan gagasan
mengenai komputasi, dan kedua adalah teknik rekayasa untuk perancangan
sistem komputasi, yang meliputi perangkat keras dan perangkat lunak.
Teori Bahasa dan Otomata merupakan bagian dari komponen pertama.
Finite
State Automata dan ekspresi regular awalnya dikembangkan berdasarkan
pemikiran jaringan syaraf tiruan (neural network) dan rangkaian switch
(switching circuit). Finite State Automata sangat berguna dalam
perancangan lexica l analyzer, yang merupakan bagian dari sebuah
compiler. FSA dan ekspresi regular juga digunakan dalam perancangan text editor, pattern-matching, sejumlah pemrosesan teks, dan program file-searching serta sebagai konsep matematis untuk aplikasi lain.
Mengapa
mempelajari teori? Teori memberikan konsep dan prinsip yang menolong
untuk memahami “perilaku” dari suatu disiplin ilmu. Bidang ilmu komputer
meliputi topik yang sangat luas, dimana sebagian besar mempunyai
prinsip yang umum. Untuk mempelajari prinsip dasar inilah diperlukan
pemodelan secara abstrak dari komputer. Model ini memiliki fungsi-fungsi
yang penting dan umum untuk dapat diterapkan pada perangkat keras
maupun perangkat lunak. Beberapa gagasan yang diutarakan memiliki
penerapan yang penting. Misalkan pada compiler.
Pengantar Model Komputasi
Kuliah
ini membahas model-model komputasi sebagai mesin abstrak yang dapat
didefinisikan secara matematis, mulai dari yang paling sederhana hingga
yang paling powerful.
Model-model
sederhana dibahas agar formalisasi matematis dapat terbentuk secara
bertahap, selain itu tetap masih ada hubungannya dengan situasi-situasi
dunia nyata.
Secara
umum model-model digambarkan sebagai mesin untuk menjawab masalah
keputusan berdasarkan masukan string x dengan memberikan keluaran berupa
: ya atau tidak misalnya :
· Apakah x bilangan ganjil
· Apakah sebuah kata s anggota bahasa B
Masalah
komputasi memang lebih umum daripada masalah keputusan, namun pada
dasarnya suatu model untuk masalah keputusan memerlukan komponen yang
dapat melakukan komputasi yang terkait, misalnya : Untuk suatu (x,y),
“apakah y = f(x)?” hanya dapat dijawab jika f(x) dapat dikomputasi.
Model-model
mesin yang akan dibahas pada kuliah ini adalah Finite Automata (FA),
PushdownAutomata(PDA), Mesin Turing (TM). Teori dan model komputasi ini
telah berkembang jauh sebelum ditemukan perangkat komputer itu sendiri.
Konsep Bahasa
Simbol. Simbol merupakan elemen unik terkecil dari bahasa. Dalam sebuah bahasa terdapat sejumlah berhingga simbol-simbol.
Abjad / Alfabet. Merupakan himpunan dari simbol-simbol yang digunakan dalam suatu bahasa. Biasanya dinotasikan dengan S. Misalkan S = {0,1}.
String / word / kata / untai. Adalah barisan berhingga dari simbol-simbol dalam suatu alfabet. Misalkan : S = {0,1} maka 01, 00, 111 merupakan string yang dibentuk berdasarkan alfabet S. Dalam pembahasan, seringkali suatu untai/string dinyatakan dengan suatu variabel, yang biasanya berupa huruf kecil. Contoh : w = “01”; x = “aba”, dst.
Panjang String. Suatu string disusun dari sejumlah n simbol, dengan n³0. Banyaknya simbol yang menyusun sebuah string disebut panjang string, yang disimbolkan dengan |x|. contoh : x = aba , maka |x| = 3.
Untai hampa. Sebuah string dengan panjang nol (n=0) disebut untai hampa dan dinotasikan dengan l. Untai hampa (l) merupakan untai yang dibentuk berdasarkan abjad apa saja. Sehingga l merupakan himpunan bagian dari sembarang himpunan.
Bahasa. Bahasa merupakan himpunan string/kata dari alfabet bahasa itu. Misal untuk
- S1 = {0,1} maka L1 = {00,01,11,111} merupakan bahasa yang dibentuk berdasarkan abjad S1 .
- S2 = {a,b} maka L2 = {a, ab, aab, aaab, … } merupakan bahasa berdasarkan abjad S2
Misalkan S suatu abjad dan w adalah untai yang dibentuk berdasarkan abjad S. Jika terdapat L yang merupakan bahasa berdasar abjad S dan jika w ada di dalam L, kita tuliskan w Î L, yang berarti w elemen dari L.
Bahasa kosong. Merupakan bahasa yang tidak terdiri dari untai apapun. Dinotasikan dengan {} atau Æ.
Bahasa Universal. Adalah bahasa yang terdiri dari semua kata yang dapat dibentuk berdasarkan suatu abjad S. Misalkan S = {1} maka bahasa universal, dinotasikan S*, adalah S* = {l, 1, 11, 111, 1111, …}
Operasi pada String
Perangkaian (Concatenation). Jika w dan z adalah untai, perangkaian w dengan z merupakan untai yang diperoleh dengan merekatkan z ke w. Contoh : w = “abang” dan z = “none” maka wz atau w.z = “abangnone”. Panjang kata wz, |wz| = |w| + |z|=9.
Sebarang kata jika dirangkai dengan l, tidak akan merubah kata tersebut. wl=lw=w. Jadi l merupakan identitas (identity) terhadap operasi perangkaian.
Pangkat (Exponentiation). Misalkan w merupakan sebuah kata, untuk n Î bilangan asli, didefinisikan :
Misalkan , S = {0,1} dan w = 110, diperoleh :
w0 = l
w1 = w.w0 = 110.l = 110
w2 = w.w1 = 110.110 = 110110
w3 = w.w2 = 110.110110 = 110110110
Sama Dengan (Equal). Jika w dan z adalah untai, dikatakan w sama dengan z jika keduanya terdiri dari simbol-simbol yang sama dan panjangnya sama, dinotasikan w = z.
Awalan (prefix). Jika w dan x adalah kata, maka x merupakan awalan dari w jika untuk suatu untai y, berlaku w = xy. Contoh w = 121 dan x = 12, maka x merupakan awalan dari w, dimana dalam hal ini y = 1.
Subuntai (substring). Sebuah untai w merupakan subuntai dari untai lain z jika terdapat untai-untai x dan y, sehingga berlaku z = xwy.
Pembalikan (reversal / transpose). Transpose dari sebuah untai w, yaitu wR, didefinisikan sebagai :
Contoh : w = “able”,
wR = (able)R = (ble)R a
= (le)Rba
= (e)R lba
= (l)Relba
= l. elba
= elba
Operasi Pada Bahasa
Concatenation. Misal A dan B adalah bahasa berdasarkan suatu abjad. Didefinisikan perangkaian dari bahasa A dan B sebagai :
A.B = { w.x | w Î A dan x Î B}
Jadi
A.B terdiri dari semua untai yang dibentuk dengan mengambil setiap
untai di A dan merangkaikannya dengan setiap untai di B. Contoh : A =
{bird, dog} dan B = { house} maka AB = {birdhouse, doghouse}
Eksponensiasi. Misalkan A bahasa berdasarkan abjad S, didefinisikan :
Jadi, jika misalkan A = {ab,a} berdasarkan abjad S = {a,b} maka :
A0 = { l }
A1 = A.A0 = {ab,a}{l} = {ab,a}
A2 = A.A1 = {ab,a}{ab,a} = {abab,aba,aab,aa}
A3 = A.A2 = {ab,a}{abab,aba,aab,aa} = {ababab,ababa,abaab,abaa,aabab,aaba, aaab,aaa}
Gabungan (Union). Jika A dan B adalah bahasa berdasarkan abjad S maka gabungan dari A dan B, A È B, terdiri dari semua kata yang muncul sekurang-kurangnya sekali di dalam A dan B.
A È B = {x | x Î A atau xÎB}
Irisan (intersection). Irisan dari bahasa A dan B terdiri dari kata-kata yang muncul di A sekaligus di B. Dinotasikan sebagai : A Ç B,
A Ç B = {x | x Î A dan x Î B}
Selisih (Difference). Jika A dan B bahasa berdasarkan abjad S, didefinisikan selisih antara bahasa-bahasa tersebut sebagai :
A – B = {x | x Î A dan x Ï B}
Komplemen. Komplemen dari suatu bahasa A berdasarkan abjad S didefinisikan sebagai : .
Subbahasa (sublanguage). Jika A dan B bahasa berdasarkan abjad S, dan jika semua untai di A juga merupakan untai di B maka A disebut subbahasa dari B. (A Í B)
Equal. Dua bahasa A dan B dikatakan sama atau equal, A = B, jika kedua bahasa tersebut secara persis mempunyai untai-untai yang sama.
Pembalikan (Transpose/Reversal). Pembalikan dari suatu bahasa A dapat didefinisikan sebagai :
AR = { xR | x Î A }
Contoh : A = { dog, bog} maka AR = {god, gob}.
Kleene Closure / Star Closure. Jika A sebuah bahasa maka penutup kleene dari bahasa A didefinisikan sebagai : A* = .
Contoh : A = {a} maka A* = {l,a,aa,aaa,…}
Positive Closure / Plus Closure. Jika A sebuah bahasa maka penutup kleene dari bahasa A didefinisikan sebagai : A+ = .
Contoh : A = {a} maka A+ = {a,aa,aaa,…}.
Teorema : A+ = A. A* = A*. A
Soal-Soal
1. Misalkan A = {the,my} dan B = {horse,house,hose} merupakan bahasa-bahasa berdasarkan alfabet bahasa inggris. Carilah A.B, A.A
2. Misalkan A = {l,a}. Carilah An untuk n = 0,1,2,3. Berapa banyaknya elemen An untuk sembarang n?
3. Misalkan A = {l}. Carilah A*.
4. Misalkan A = {l,ab} dan B = {cd}. Tentukan untai-untai dalam A*B.
5. Misalka A = {a,b} Carilah A*
6. Misalkan A = {l}, B = {aa,ab,bb}, C = {l,aa,ab} , dan D = {}. Carilah AÈB, AÈC, AÈD, BÈD dan AÇB, BÇC, CÇD, AÇD. Misalkan F sebarang bahasa carilah FÈD dan FÇD.
7. Misalkan bahasa S = {a,b} dan S* merupakan star closure dari bahasa S. Ada berapa kata di S* yang punya panjang 2? Panjang 3? Panjang n?
8. Misalkan bahasa S = {aa,b} dan S* merupakan star closure dari bahasa S. Ada berapa kata di S* yang punya panjang 4? Panjang 5? Panjang 6? (Jelaskan secara umum)
9. Misalkan bahasa S = {ab,ba} dan S* merupakan star closure dari bahasa S. Tuliskan semua kata di S* yang panjangnya kurang atau sama dengan 7. Mungkinkan ada kata dalam S* yang mempunyai substring aaa atau bbb?
10. Misalkan bahasa S = {a, ab,ba} dan S* merupakan star closure dari bahasa S. Apakah string abbba ada di S*? Tuliskan semua kata di S* yang panjangnya kurang atau sama dengan 6!
Reference
[1] Hopcroft,John E; Motwani, Rajeev; Ullman, Jeffrey D.; Introduction to Automata Theory, Language and Computation; Second Edition; Addison-Wesley, 2001.
[2] Kelley, Dean; Otomata dan Bahasa Formal, Sebuah Pengantar; PT. Prenhallindo, 1999
coba sring dengan nama saya
BalasHapusjawabannya apa ya buat belajar
Hapus