Konsep dan operasi Bahasa otomata

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