Pengertian Dasar
ü Bahasa
§ Suatu
sistem yang meliputi pengekspresian gagasan, fakta, konsep, termasuk sekumpulan
simbol – simbol dan aturan untuk melakukan manipulasinya.
§ Himpunan
string – string dari simbol – simbol untuk suatu alphabet.
§ Rangkaian
simbol – simbol yang mempunyai makna.
ü Otomata
§ Suatu
sistem yang terdiri atas sejumlah state (menyatakan informasi mengenai input
yang lalu, atau dapat dianggap pula sebagai memori mesin) berhingga.
§ Suatu
sistem untuk menerima input, menghasilkan output, bisa memiliki tempat
penyimpanan sementara, dan mampu membuat keputusan dalam mentransformasikan
input ke output.
Contoh :
· Lingkaran
menyatakan state / keadaan.
· Label
pada lingkaran menyatakan nama state.
· Busur
menyatakan transisi / perubahan state.
· Label
pada busur menyatakan input yang diproses.
· Lingkaran
yang didahului busur tanpa keterangan, adalah state awal.
· Lingkaran
ganda menyatakan state akhir.
FINITE STATE AUTOMATA ( FSA )
- Model matematika yang dapat menerima input dan mengeluarkan output
- Memiliki state yang berhingga banyaknya dan dapat berpindah dari satu state ke state lainnya berdasar input dan fungsi transisi
- Tidak memiliki tempat penyimpanan/memory, hanya bisa mengingat state terkini
Finite
State Automata dinyatakan oleh 5 tuple
M=(Q , S
, d , S , F )
Q= himpunan state
S = himpunan simbol input
d = fungsi transisi d
: Q ´ S
S
= state awal / initial state , S Î
Q
F
= state akhir, F Í
Q
DETERMINISTIC FINITE AUTOMATA ( DFA
)
è Jenis otomata yang hanya
memiliki tepat satu next state untuk setiap masukan yang diterima.
Contoh :
Merupakan DFA untuk mengecek variabel pada Pascal.
