slide ke-4 dfa

DFADefinisi OtomataFinete Automata/Finite State Automata (FSA)Deterministic Finite Automata (DFA)

Otomata adalah:

Suatu bentuk/model matematika yang memiliki fungsi-fungsi dari komputer digital yaitu

menerima input,menghasilkan output,bisa memiliki penyimpanan

sementara, mampu membuat keputusan dalam

mentransformasikan input ke output

Otomata (lanjutan)Terdiri dari sejumlah berhingga

state (kedudukan)Perpindahan state satu ke yang

lain berdasar input dan fungsi transisi

Input pada otomata => bahasa yang harus dikenali

Otomata membuat keputusan apakah input diterima atau tidak.

Contoh 1: otomata

Memiliki 6 state: q0, q1, q2, q3, q4, q5

State awal: q0

◦ditandai dengan panah masuk tanpa state sebelumnya

State akhir: {q3. q4}◦ditandai dengan lingkaran dobel

Himpunan input: {a, d, u}

Contoh 2: Mesin jaja

Finite State Automata (FSA)Finite State Automata (Otomata dengan state

berhingga) merupakan suatu model matematika dari suatu sistem yang menerima input dan menghasilkan output

berfungsi sebagai alat untuk mengenali bahasa (Language Recognition Device

bermanfaat pada compiler, terutama pada fase Analisis Lexical

Memiliki state yang banyaknya berhingga dan dapat berpindah-pindah dari suatu state ke state lain

Perubahan state ini dinyatakan dengan fungsi transisi

tidak memiliki tempat penyimpanan

Prinsip kerja FSAMenerima masukan stringFA mempunyai kontrol berhingga serta stateFA membaca karakter-karakter (substring yang

di depan) awal dengan kontrol berada pada state awal.

Dengan control tersebut dan membaca karakter-karakter awal, state berubah ke state baru (state awal menyerap substring)

Proses dilanjutkan sampai string terserap habisJika state akhir berada dalam himpunan state

akhir yang ditentukan, maka string tersebut diterima/dikenali oleh FA tersebut

Definisi formal FSA

M = (Q,Σ,δ,S,F) di mana :Q = himpunan stateΣ = abjad, himpunan simbol

input/masukanδ = fungsi transisi, δ : Q x Σ QS = state awal / initial stateF = himpunan state akhir/final

state

Contoh (slide 4)Q = {q0, q1, q2, q3, q4, q5}Σ = {a, d, u}S = q0

F = {q3, q4}δ fungsi transisi

◦δ(q0, a) = q1

◦δ(q1, d) = q2

◦δ(q2, a) = q3

◦δ(q2, u) = q4

◦δ(q2, d) = q5

FSA terbagi 2:Deterministic (DFA)Non deterministic (DFA)

Deterministic Finite Automata (DFA)

Deterministic Finite Automata (DFA)Dari suatu state ada tepat satu

state berikutnya untuk setiap simbol masukan yang diterima

Contoh 3: DFAΣ = {0,1}Q = {a, b, c, d}S = {a}F = {b, c}Fungsi transisi δ : Q x Σ Q, yang

didefinisikan sebagai :δ = {((a,0),b), ((a,1),d), ((b,0),c), ((b,1),d), ((c,0),d), ((c,1),c), ((d,0),a), ((d,1),b)}

Fungsi transisi dapat ditulis dalam bentuk tabel

δ 0 1a b db c dc d cd a b

Transition State diagramPenyajian DFA/NFA secara grafikalDalam state diagram:

◦Lingkaran simpul menyatakan state◦Label pada lingkaran adalah nama state

tersebut◦Lingkaran didahului sebuah busur tanpa

label menyatakan state awal/Initial state◦Lingkaran ganda menyatakan state

akhir/final state◦Busur/penghubung simpul menyajikan abjad

yang menyatakan transisi yaitu perpindahan state

State diagram untuk contoh 3

?

Contoh 4

Buatlah suatu DFA yang dapat menerima string yang berakhir dengan 00. Asumsikan himpunan alfabetnya {0,1}.

Tuliskan definisi formal (5-tuple) beserta diagram transisinya.

Contoh 5

Buatlah DFA yang dapat menerima semua string yang mengandung substring 101


Contoh 6

Buatlah DFA yang dapat menerima semua string yang mengandung simbol 0 berjumlah genap. (Contoh: 001, 1010, 110000)


PR No 3-4, peroranganTulis tangankumpul minggu depan saat awal

kuliah

slide ke-4 dfa

Education