The Sampah's Blog

Finite Automata

Posted on: June 15, 2010

Definisi

–  Sebuah deterministic finite automaton terdiri dari:

–  States (Q)

–  Input symbols ()

–  Fungsi transisi (δ)

–  State awal (q0)

–  State final (F) – state penerima

–  Deterministic finite automaton disingkat: DFA

–  DFA direpresentasikan oleh 5 tuple, yaitu:

A = (Q, ,δ, q0, F)

DFA memproses String

–  Bahasa” dari sebuah DFA adalah kumpulan semua string yang diterima DFA tersebut

–  Misal a1,a2,..,an adalah deretan dari input symbol

–  DFA diawali dari state awal q0, Lihat δ(q0,a1)=q1

–  State berikutnya adalah q1, Lihat δ(q1,a2)=q2

–  Begitu seterusnya hingga an. Dan δ(qn-1,an)=qn

–  Jika qn adalah anggota dari F, maka deretan input tersebut diterima, dan jika tidak maka ditolak

Notasi Sederhana DFA

–  Diagram transisi

— Tabel transisi

Contoh

–  Desain sebuah DFA yang menerima bahasa:  L= {w | w memiliki symbol 0 dan 1 berjumlah genap}


Extended Fungsi Transisi


Bahasa dari DFA

n  Bahasa dari sebuah DFA A = (Q, ,δ, q0, F) adalah L(A), dan didefinisikan oleh: L(A)={ w | δ(q0,w) adalah anggota F}

n  Jika L adalah L(A) untuk suatu DFA A, maka dikatakan L adalah bahasa reguler

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


  • Mr WordPress: Hi, this is a comment.To delete a comment, just log in, and view the posts' comments, there you will have the option to edit or delete them.

Categories

%d bloggers like this: