OTOMATA part 1

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.