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

-          S₁ = {0,1} maka L1 = {00,01,11,111} merupakan bahasa yang dibentuk berdasarkan abjad S₁   .

-          S₂ = {a,b} maka L2 = {a, ab, aab, aaab, … } merupakan bahasa berdasarkan abjad S₂

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 :

            w_­⁰ = l

            w¹ = w.w⁰ = 110.l = 110

            w² = w.w¹ = 110.110 = 110110

            w³ = w.w² = 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 w^R, didefinisikan sebagai :

                

Contoh : w = “able”,

                w^R = (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 :

            A⁰ = { l }

            A¹ = A.A⁰ = {ab,a}{l} = {ab,a}

            A² = A.A¹ = {ab,a}{ab,a} = {abab,aba,aab,aa}

A³ = A.A² = {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 :

            A^R = { x^R | x Î A }

Contoh : A = { dog, bog} maka A^R = {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 Aⁿ untuk n = 0,1,2,3. Berapa banyaknya elemen Aⁿ 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

[3]    Cohen, Daniel I.A; Introduction to Computer Theory;  John Wiley & Sons, Inc, 1991.