automata hingga (ah)

8/18/2019 Automata Hingga (AH)

1/18

Automata Hingga (AH)


2/18

• AH didefnisikan sebagai pasangan 5tupel : (Q, V T , σ, q0, F):

•

• Q : i!punan ingga stata• VT : i!punan ingga si!b"l input(al#abet)• σ : #ungsi t$ansisi,

!engga!ba$kan t$ansisi stata AHakibat pe!ba%aan si!b"l input&


3/18

• Fungsi t$ansisi ini biasan'a dibe$ikandala! bentuk tabel&

•

• q0 Q : stata aal• F * Q : i!punan statapene$i!a


4/18

• Ada dua +enis aut"!ata ingga :dete$!inistik (AH, FA - deterministicfnite automata) dan n"n dete$!inistik (AH.,.FA - non deterministik fnite automata)&

• / AH : t$ansisi stata AH akibat pe!ba%aansebua si!b"l be$si#at te$tentu&& σ (AH) : Q V T 1 Q/ AH. : t$ansisi stata AH akibat pe!ba%aan

sebua si!b"l be$si#at tak tentu&& σ (AH.) : Q V T 1 2Q


5/18

Automata HinggaDeterministik (AHD)

• 3e$ikut ini sebua %"nt" AH F(Q, V T , σ, q0, 4), di!ana :

•

Q - q0, q6, q27 σ dibe$ikandala! tabel be$ikut :


6/18

8lust$asi g$a# untuk AH Fadala sebagai be$ikut :

/9a!bang stata aal adala n"de dengan anak pana&

/9a!bang stata aal adala n"de ganda&

/"nt" kali!at 'ang dite$i!a AH : a, b, aa, ab, ba, aba, bab,abab, baba

/"nt" kali!at 'ang tidak dite$i!a AH : bb, abb, abba


7/18

Automata HinggaNondeterministik (AHN)

• 3e$ikut ini sebua %"nt" AH. F(Q, V T , σ, q0, 4), di!ana :

•

Q - q 0 , q6, q 2 ,q ; , q < 7 σdibe$ikan dala! tabel be$ikut :


8/18

8lust$asi g$a# untuk AH. Fadala sebagai be$ikut :

"nt" kali!at 'ang dite$i!a AH. di atas : aa, bb, %%,aaa, abb, b%%, %bb"nt" kali!at 'ang tidak dite$i!a AH. di atas : a, b, %, ab, ba,a%, b%


9/18

Ekuivalensi AHN, AHD,dan GR

/AH bisa dibentuk da$i AH.&

/=> bisa dibentuk da$i AH& AH.AH. bisa dibentuk da$i =>& AH =>


10/18

?e!bentukan AH da$i AH.:

• ibe$ikan sebua AH. F - (Q, V T , σ, q0,4)& Akan dibentuk sebua AH F@ - (Q@,VT @, σ@, q0@, 4@) da$i AH. F te$sebut&

Alg"$it!a pe!bentukann'a adala sbb& :• 6& Tetapkan : q0@ - q0 dan V T @ - V T• 2& "p'kan tabel AH. F sebagai tabel

AH F@& ula/!ula Q@ - Q dan σ@ - σ


11/18

• ;& Betiap stata q 'ang !e$upakan nilai(atau peta) da$i #ungsi σ dan q C Q,ditetapkan sebagai ele!en ba$u da$i Q@&

Te!patkan q te$sebut pada k"l"! Btataσ@, lakukan pe!etaan be$dasa$kan #ungsiσ&


12/18

%"nt" AH. F - (Q, V T , σ, q0,

4) dengan :• Q - A, 3, 7, V T - a, b7, q0 - A,

4 - 7, dan σ dide#inisikan sebagaibe$ikut:

=a!ba$ : Tabel AH. 'ang akan

dik"ne$sikan !en+adi AH


13/18

Ekspressi reguler

• 3aasa disebut $egule$ +ika te$dapatFBA 'ang dapat !ene$i!an'a&

• 3aasa $egule$ din'atakan se%a$asede$ana dengan eksp$esi$egule$G$egula$ ep$essi"n (>E)&

• "nt" pene$apan : sea$%ing st$ingpada fle

• >E /I .FA dengan J "e /I FA


14/18

efnisi eksp$esi $egule$

• Kika L !e$upakan i!punan si!b"l,!aka :

• 6& M , N , dan a L adala eksp$esi$egule$ dasa$

• 2& +ika $ dan t !asing !asing!e$upakan eksp$esi $egule$ !akak"!p"sisi be$ikut !e$upakaneksp$esi $egule$ :


15/18

Ekspesi Makna

r+t i!punan st$ing gabungan >OT

rt "pe$asi pen'a!bungan st$ing td

i!punan

R* Pleene %l"su$e da$i >

(r) $


16/18

Conto ekspresi reguler

• (06)R : i!punan selu$u st$ing 'angdapat dibentuk da$i si!b"l S0@ dan S6@

• (06)R00(06)R : i!punan st$ingbine$ 'ang !engandung paling sedikitsatu subst$ing S00@

• (06)R00 : i!punan st$ing bine$

'ang diaki$i dengan S00@ 3aasa>egule$


17/18

Conto

Tentukan baasa $egule$ 'angdibentuk "le $-(aa)R

Kaab :

9($) - 9( (aa)R )

- N, aa, aaaa, aaaaaa, &&& 7

- a2n n U 0 7


18/18

automata hingga (ah)

Documents