Saturday, January 31, 2015

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.
luvne.com resepkuekeringku.com desainrumahnya.com yayasanbabysitterku.com

0 comments:

Post a Comment

ICT (information and communications technology - or technologies) is an umbrella term that includes any communication device or application, encompassing: radio, television, cellular phones, computer and network hardware and software, satellite systems and so on, as well as the various services and applications associated with them, such as videoconferencing and distance learning