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½…
