Alphabet dan Konkatenasi pada teori bahasa otomata

1.      ALPHABET

• Sebuah alphabet adalah himpunan berhingga dan tak kosong dari simbol.  Alphabet disimbolkan oleh ∑. 
• Contoh:

•              ∑ = {0, 1} alphabet biner

•           ∑ = {a, b,..., z}, himpunan semua huruf kecil.

•            Himpunan semua karakter ASCII.

String

• Sebuah string (atau word) adalah deretan simbol berhingga yang dipilih dari alphabet. 
• Contoh : 011011 dan 1111 adalah string dari alphabet biner ∑ = {0, 1}. 
• String kosong adalah string dimana tidak ada kemunculan simbol.
• String tersebut dinotasikan oleh e.
• Panjang dari string adalah banyaknya posisi untuk simbol dalam string. 
• Contoh, 01101 memiliki panjang 5. 
• Umumnya panjang dari string adalah banyaknya simbol dalam string.
• Pernyataan tersebut tidak sepenuhnya benar, sebagai contoh terdapat 2 simbol dalam string 01101 yaitu 0 dan 1, tetapi terdapat 5 posisi untuk simbol, dan panjangnya adalah 5.
• Notasi standar untuk panjang string w adalah |w|.  Contoh: |011| = 3 dan |e| = 0.
• x adalah sebuah substring dari string lain y jika ada string w dan z, keduanya dapat berupa string kosong, sedemikian sehingga y = wxz. 
• Sebagai contoh, car adalah substring dari carry, car, vicar.

Pangkat dari Alphabet

•   Jika  adalah alphabet, dapat dinyatakan himpunan dari semua string dengan panjang tertentu dari alphabet tersebut dengan menggunakan notasi eksponensial. 

•   Kita mendefinisikan ∑^k sebagai himpunan dari string dengan panjang k, setiap string tersebut memiliki simbol dalam ∑.

• Perhatikan bahwa ∑⁰  = {e}, untuk alphabet apapun. 
• Bahwa e adalah string yang memiliki panjang 0.  Jika ∑ = {a, b, c} maka

∑¹  = {a,b,c }

∑²  =  {aa, ab, ac, ba, bb, bc, ca, cb, cc}

∑³  = {{aaa, aab, aac, aba, abc, aca, acb, aca, bbb, bac, bca, ccc, cba, ccb, cca, abb, baa, bab, bba, acc, cac, caa, cab, cbc, bcb, ccc,ccb}

2.      KONKATENASI

Didefinisikan suatu operasi biner, dinamakan konkatenasi (gabungan), dalam S* , sbb:

• Jika a₁a₂a₃…a_n dan b₁b₂…b_m berada dalam S*, maka a₁a₂a₃...a_n.b₁b₂…b_m = a₁a₂a₃…a_nb₁b₂…b_m

• Sehingga, string yang satu dapat digabungkan dengan string lainnya:

• Jika x , y dan z  merupakan dua buah string, maka x.y,z diartikan sebagai gabungan dari x y dan z, hasilnya, string yang baru terbentuk dengan menulis x diikuti dengan menuliskan y diikuti dengan menuliskan z .

Contoh:

x = aku y= belajar dan z = pusing

Maka

•   x . y= aku belajar

•  (x . y ).z)=aku belajar pusing

•   (y.z).x= belajar pusing aku