OTOMATA

ABJAD, KATA DAN BAHASA

•   ABJAD(ALPHABET)

Abjad (alphabet) adalah : himpunan berhingga(finite)tak kosong

Contoh : jika ∑={a,b,c,d,1,3,7} maka a c ∑, I ϵ ∑.  

• kata

Kata adalah barisan yang berhingga symbol-simbol dari suatu abjad. 
Contoh : dari contoh diatas maka kata adalah baca dada 137, a13 dan lain-lain.

• Kata = string

Kata(string) kosong adalah barisan kosong dari symbol-symbol ≈{ϵ}empityword.

Bahasa adalah sebuah kumpulan kata-kata dimana sebuah bahasa string itu sendiri. Bahasa kosong* adalah bahasa yang terdiri dari string kosong.

Bahasa kosong yaitu bahasa yang tidak terdiri dari untai-untai. Sedangkan bahasa yang terdiri dari string kosong adalah { ϵ}

Symbol bahasa kosong ≠Ǿ

Misalkan V adalah suatu abjad, dan W suatu String berdasarkan V : . jika L sebuah bahasa yang terdiri dari beberapa string berdasarkan V danW adalah sebuah string di dalam L, maka {ditulis ≈}WϵL. 

Contoh :  121 ϵ {1,12,121,1212,12121 dan seterusnya}

Jika ∑ = {1} maka,∑^m  : {∑ ,1,11,111,1111……} bersifat tak berhingga dan disebut ( close) star.

Penjelasan :

Bahasa formal artinya bahasa kaku adalah bahasa yang di gunakan oleh mesin computer. Contohnya : C++, java, Delphi,Php dan lain-lain.

Bahasa alami adalah bahasa yang fleksibel.

Bahasa kosong tidak sama dengan bahasa yang mengandung kata kosong.

Ǿ = length/panjang.

Contoh 1:         V= a,p,e,l ,h

W = apel,hapal

L= { hapal,apel}

                        Contoh2 :         saya pergi ke kampus (benar)

                                                Saűa pergi ke kampus. (salah)

Kata kuliah berasal dari bahasa araf artinya Kuliatul.

OPERASI-OPERASI PADA STRING

PENJELASANNYA

1.      LENGTH(PANJANG KATA)

W=apel                  v=ϵ

|w|=4                    |v|=0

2.      CONCAT.

Adalah pengabungan beberapa string menjadi satu string.

w.z=wz

w.v.z=wvz

contoh :

w = tanggung

z = jawab

jadi, w.z = tanggungjawab } wz ≠ zw                z.w= jawab tanggung

                               w.v= w = tanggung

v = ϵ

                               v.w= w = tanggung.

3.      OPERASI PANGKAT.

w⁰= ϵ

w¹=w

w²=ww

w³=www

w⁴=wwww=w.w³

4.      EQUAL(OPERASI SAMA DENGAN).

w = z : |w|=|z|

            w|i|= z |i|

5.      PREFIX AND SUFIX(AWAL DAN AKHIR).

Jika, v = wz maka, prefix(v)= w

                              Suffix(v)= z

Contoh :

Jika, v = apel,

maka, prefix (v)=ϵ,a,ap,ape,apel.

Sedangkan, suffix (v)=ϵ,l,el,pel,apel.

6.      REVERSAL/TRASPOSE/INVERS.

w^R = w^T = w¹ :

ð  w = jika, w = ϵ

ð  y^R.a jika w = ay.

Contoh :

W = apel = ay

W^R = (apel)^R.a

W^R = (pel)^R.pa

W^R = (el)^R.epa

W^R = (lϵ)^R.lepa

W^R = (ϵ)^R.lepa

      = ϵ.lepa

      = lepa.

7.      CONCATINATION.

A.B = { w.x |wϵA, xϵB|}

Contoh 1 :

Question

 A = {dog,cat}

B = {head,tail}

Answer

A.B = {doghead,dogtail,cathead,cattail}

B.A = {headdog,headcat,taildog,tailcat}

Aⁿ = {ϵ}, n = 0

      A.A^n-1.1,  n = 1,2,3……….

Contoh 2 :

Question

A = {dog,cat}

Answer

A⁰ ={ϵ}

A¹ = A ={dog,cat}

A² = A. A¹ = {dogdog,dogcat,catdog,catcat}

A³ = A. A² = {dogdogdog,dogdogcat,dogcatdog,dogcatcat,catdogdog,catdogcat,catcatdog,catcatcat}