FINITE STATE AUTOMATA

Otomata (Automata)

• Otomata adalah mesin abstrak yang dapat mengenali (recognize), menerima (accept), atau membangkitkan (generate) sebuah kalimat dalam bahasa tertentu.

Beberapa Pengertian Dasar :

·         Simbol adalah sebuah entitas abstrak (seperti halnya pengertian titik dalam geometri). Sebuah huruf atau sebuah angka adalah contoh simbol.

·         String adalah deretan terbatas (finite) simbol-simbol. Sebagai contoh, jika a, b, dan c adalah tiga buah simbol maka abcb adalah sebuah string yang dibangun dari ketiga simbol tersebut.

·         Jika w adalah sebuah string maka panjang string dinyatakan sebagai ïwï dan didefinisikan sebagai cacahan (banyaknya) simbol yang menyusun string tersebut. Sebagai contoh, jika w = abcb maka ïwï= 4.

·         String hampa adalah sebuah string dengan nol buah simbol. String hampa dinyatakan dengan simbol e (atau ^) sehingga ïeï= 0. String hampa dapat dipandang sebagai simbol hampa karena keduanya tersusun dari nol buah simbol.

·         Alfabet adalah hinpunan hingga (finite set) simbol-simbol

DFA (Deterministic Finite Automata)

·            – otomata berhingga yang pasti (tetap/tertentu)

·            – setiap rancangan state input selalu tepat ada satu state berikutnya

·            – dari suatu state ada tepat satu state berikutnya untuk setiap simbol

·              masukan yang diterima

·            – Untuk sebuah state dan input yang berlaku bisa ditentukan tepat satu

·             state berikutnya.

·            – Suatu string x dinyatakan diterima bila _(S,x) berada pad state akhir.

·              Dengan kata lain secara formal bila M adalah sebuah bahasa FSA,

·              M = (Q, _, d, S, F) menerima bahasa yang disebut L(M) yang

·      merupakan himpunan {x | d (S,x) di dalam F}.

NDFA (Non-Deterministic Finite Automata)

·            – otomata berhingga yang tidak pasti

·            – untuk setiap pasangan state input, bisa memiliki 0 (nol) atau lebih

·               pilihan untuk state berikutnya

·            – Untuk setiap state tidak selalu tepat ada satu state berikutnya untuk

·               setiap simbol input yang ada

·            – Dari suatu state bisa terdapat 0,1 atau lebih busur keluar (transisi)

·               berlabel simbol input yang sama

·            – Untuk NFA harus dicoba semua kemungkinan yang ada sampai

·               terdapat satu yang mencapai state akhir.

·    – Suatu string x dinyatakan diterima oleh bahasa NFA, M= (Q, _, d, S, F)

·         bila {x | d (S,x) memuat sebuah state di dalam F}

Operasi Dasar String

Diberikan dua string : x = abc, dan y = 123

·         Prefik string w adalah string yang dihasilkan dari string w dengan menghilangkan nol atau lebih simbol-simbol paling belakang dari string w tersebut.

Contoh :abc, ab, a, dan e adalah semua Prefix(x)

·         ProperPrefix string w adalah string yang dihasilkan dari string w dengan menghilangkan satu atau lebih simbol-simbol paling belakang dari string w tersebut.

Contoh :ab, a, dan e adalah semua ProperPrefix(x)

·         Postfix (atau Sufix) string w adalah string yang dihasilkan dari string w dengan menghilangkan nol atau lebih simbol-simbol paling depan dari string w tersebut.

Contoh :abc, bc, c, dan e adalah semua Postfix(x)

·         ProperPostfix (atau PoperSufix) string w adalah string yang dihasilkan dari string w dengan menghilangkan satu atau lebih simbol-simbol paling depan dari string w tersebut.

Contoh :bc, c, dan e adalah semua ProperPostfix(x)

·         Head string w adalah simbol paling depan dari string w.

Contoh : a adalah Head(x)

·         Tail string w adalah string yang dihasilkan dari string w dengan menghilangkan simbol paling depan dari string w tersebut.

Contoh : bc adalah Tail(x)

·         Substring string w adalah string yang dihasilkan dari string w dengan menghilangkan nol atau lebih simbol-simbol paling depan dan/atau simbol-simbol paling belakang dari string w tersebut.

Contoh : abc, ab, bc, a, b, c, dan e adalah semua Substring(x)

·         ProperSubstring string w adalah string yang dihasilkan dari string w dengan menghilangkan satu atau lebih simbol-simbol paling depan dan/atau simbol-simbol paling belakang dari string w tersebut.

Contoh : ab, bc, a, b, c, dan e adalah semua Substring(x)

·         Subsequence string w adalah string yang dihasilkan dari string w dengan menghilangkan nol atau lebih simbol-simbol dari string w tersebut.

Contoh : abc, ab, bc, ac, a, b, c, dan e adalah semua Subsequence(x)

·         ProperSubsequence string w adalah string yang dihasilkan dari string w dengan menghilangkan satu atau lebih simbol-simbol dari string w tersebut.

Contoh : ab, bc, ac, a, b, c, dan e adalah semua Subsequence(x)

·         Concatenation adalah penyambungan dua buah string. Operator concatenation adalah concate atau tanpa lambang apapun.

Contoh : concate(xy) = xy = abc123

·         Alternation adalah pilihan satu di antara dua buah string. Operator alternation adalah alternate atau ½.

Contoh : alternate(xy) = x½y = abc atau 123

·         Kleene Closure : x* = e½x½xx½xxx½… = e½x½x½x½…

·         Positive Closure : x = x½xx½xxx½… = x½x½x½…