Finite Automata (Teori Bahasa dan Otomata)

Finite Automata (Teori Bahasa dan Otomata)

1. FiniteAutomata
Aji Purwinarko

2. ElemenBahasa
•Elemen-elemenBahasa adalahAlphabet, Grammar (Tata Bahasa)
•Alphabet adalahhimpunanterhinggadaritoken-token dimanakalimat
dibentukdalamsuatubahasa
•Grammar (Tata Bahasa) himpunandariaturan-aturanstructural yang
didefinisikanyang berlakudalamsuatukalimatpada token-token
•Semantic adalahhimpunanaturan-aturanyang didefinisikanyang
mempunyaiefekoperasionalpada setiapprogram yang ditulisdalamsuatu
bahasaapabiladi translasidan dieksekusipada suatumesin
•Contoh: KalimatdalambahasaInggrisdikonstruksidarihimpunankarakter
yang terdiridarihuruf, angka, spasidan tandabaca. Karakter-karakterini
disusunmenjadikata melaluiaturanejaandan kamus, kemudiankata disusunmenjadikalimatberdasarkanGrammar.

3. Token dan Alphabet
•Alphabet merupakanhimpunanterhinggadaritoken-token
•Alphabet darisuatuBahasa pemrogramandapatberupahimpunandari
karakter-karakterpada keybord(huruf, angka, symbol-symbol khusus) yang
merupakantoken-token.
•KemungkinandalamsuatuBahasa pemrogramanbeberapatoken dapat
digabungmenjadisebuahtoken
•Misal
•Pada “Pascal” penggunaan“:=“ merepresentasikanassignment
•Pada “Fortran” penggunaankarakterDO digunakanuntukinisialisasi
strukturloop
•!digunakanuntukmelambangkansuatualphabet
•Misalhimpunandaritoken-token yang terdiridarikaraktera, b, c dituliskan
!= {a, b, c}

4. HirarkiChomsky
Chomsky tahun2017
LahirAvram Noam Chomsky
7 Desember1928(umur93)
Philadelphia,Pennsylvania, A.S.
PendidikanUniversitas Pennsylvania

5. FiniteState Automata
•FiniteState Automatadapat digunakan untuk menggambarkan suatu sistem elektronik yang kompleks menjadi suatu model yang sederhana dan mudah
dimengerti
•Suatu sistem digital dipandang sebagai suatu yang dapat berubah dari satu
stateke statelain
•Setiap transisi ditentukan oleh statesaat ini bersama-sama dengan input
stringnya
•Contoh:
•State pada perangkat keras sistem digital: himpunan terhingga dari
voltase yang diinterprestasikansecara diskrit(highatau low)
•State pada software: himpunan nilai nilai pada register

6. •SebagaicontohseorangmenontonTV di kamarnya. TV dalamkeadaanon. Saatdimatikan, TV beralihkestatus off. Ketika dihidupkan, itukembalike
status on. Hal inidapatdiwakilioleh gambarberikut.
Gambar di atasdisebutdiagram keadaan.

7. •Automatadapat dikatakan sebagai suatu sistem yang terdiri dari sejumlah state(keadaan/status) yang terhingga, dengan transisi dari satu stateke state
lain, sehingga disebut juga dengan finitestatesystem
•Kontrol dapat berupa Deterministicyang berarti bahwa otomatisasi tidak
dapat berada di lebih dari satu keadaan pada satu waktu, atau Non-
Deterministic, yang berarti bahwa ia dapat berada di beberapa keadaan
sekaligus. Ini membedakan kelas automatasebagai DFA atau NFA.
•DFA (DeterministicFiniteAutomata): tidak dapat berada di lebih dari
satu keadaan pada waktu yang sama.
•NFA (Non-DeterministicFiniteAutomata): dapat berada di lebih dari
satu keadaan pada satu waktu.

8. •Mesinfinitestatedigunakandalamaplikasidalamilmukomputerdan jaringandata.
•Misalnya:
1.mesinfinite-state adalahdasaruntukprogram pemeriksaanejaan,
2.pengindeksan,
3.pemeriksaantata bahasa,
4.pencarianteksdalamjumlahbesar,
5.mengenaliucapan,
6.mengubahteksmenggunakanbahasamarkup sepertiXML &
HTML, dan
7.protokoljaringanyang menentukancarakomputerberkomunikasi.

9. Deterministic Finite Automata
•Sebuah akseptorhinggadeterministikatauDFA didefinisikanoleh kuintupel(5 tupel)
"=(%,!,',(!,))
%= himpunanberhinggadarikeadaaninternal,
Σ= adalahhimpunanberhinggadarisimbol-simbolalphabet,
'∶Q×Σ→Q= fungsitotal yang disebutfungsitransisi,
(!∈%= keadaanawal,
)⊆%= keadaanakhir,

10. •Mekanisme input hanyadapatbergerakdarikirikekanandan membacatepatsatusimbolpada setiaplangkah. Transisidarisatukeadaaninternal ke
keadaaninternal lainnyadiaturoleh fungsitransisi. Misalnya, jika
'((!,2)=(",
•kemudianjikaDFA dalamkeadaan(!dan simbolinput saatiniadalah2,
makaDFA akanmasukkekeadaan(".
•Fungsitransisi'yang menggunakanargumenstatus dan simbolinput dan
mengembalikanstatus. 'diwakilioleh busurantarakeadaandan label pada busur.
•(!=3;("=)

11. General Notations of DFA
•Ada duanotasiyang lebihdisukaiuntukmenggambarkankelasautomata, yaitudenganTabelTransisidan Diagram Transisi
•Tabeltransisiadalahrepresentasitabular konvensionaldarifungsitransisiδ
yang mengambilargumendariQ ×Σ & mengembalikannilaiyang
merupakansalah satustatus otomatisasi. Baris tabelsesuaidenganstatus
sementarakolomsesuaidengansimbolinput. Keadaanawaldalamtabel
diwakilioleh -> diikutioleh keadaanyaitu->q, untukq keadaanawal,
sedangkankeadaanakhirsebagai*q, untukq keadaanakhir.
•Entriuntukbaris yang berhubungandengankeadaanq dan kolomyang
berhubungandenganmasukana, adalahkeadaan(q, a).

12. •DFA Q = {q0, q1, q2, q3}
•Σ = {0, 1}
q0 = q0
F = {q0}
δ = Q ×Σ -> Q
•TabeltransisiuntukDFA di atasadalahsebagaiberikut:
•DFA inimenerimastring yang memilikiangka0 & angka1.

13. •Diagram transisidariDFA adalahrepresentasigrafisdi mana; (ataumerupakangrafik)
•Untuksetiapstate di Q, adanode yang diwakilioleh lingkaran,
•Untuksetiapkeadaanq dalamQ dan setiapmasukana dalamΣ, jika
δ(q, a) = p makaterdapatbusurdarisimpulq kep berlabela pada
diagram transisi. Jika lebihdarisatusimbolinput menyebabkantransisi
darikeadaanq kep makabusurdariq kep diberilabel dengandaftar
simbol-simboltersebut.
•Status awaldiberilabel oleh panahyang ditulisdengan'mulai' pada node.
•Status akhirataupenerimaanditandaidenganlingkaranganda.

14. •BerdasarkancontohDFA sebelumnya, makadiagram transisinyaadalah

15. Nondeterministic Finite Accepters
•Sebuahnon-deterministic finite automaton adalahmodel matematikayang terdiridari:
•HimpunankeadaanQ, (terhingga)
•Satu set terbatassimbolinput Σ, (alphabets)
•Fungsitransisiyang memetakanpasangansimbolkeadaanke
himpunankeadaan.
•Suatukeadaanq0 ∈Q, yang dibedakansebagaikeadaanawal(initial).
•Satu himpunanstatus akhirF dibedakansebagaistatus penerimaan
(final). F ⊆Q.

16. •NFA didefinisikanoleh kuintupel"=(%,!,',(!,)), di mana %,!,',)didefinisikansebagaiNFA, tetapi
'∶%Σ⋃6→2#
•Jika, misalnya, keadaansaatiniadalah(", simbol2dibaca, dan
'(",2={(!,($}:
•maka(!atau($bisamenjadikeadaannfaberikutnya. Juga, kita
mengizinkan6sebagaiargumenkeduadari'. Iniberartibahwanfadapat
melakukantransisitanpamenggunakansimbolinput.

17. NFA menerimasemuastring yang diakhiri01
•Di sini, darikeadaanq1, tidakadabusuruntuksimbolinput 0 & tidakadabusurkeluardariq2 untuk0 & 1. Jadi, kitadapatmenyimpulkandalamNFA, mungkinadanoltidak. busurkeluardarisetiapstate untuksetiapsimbolinput. Sementaradi DFA, iamemilikitepatsatubusurdarisetiapstatus untuksetiapsimbolinput.
•δ, fungsitransisiadalahfungsiyang mengambilstatus di Q dan simbol∑ input di sebagaiargumendan mengembalikansubset dariQ. Satu-satunyaperbedaanantaraNFA dan DFA adalahpada jenisnilaiyang dikembalikan. DalamNFA, mengembalikanhimpunanstatus dan dalamkasusDFA mengembalikansatustatus.

18. Latihan
•DFA atauNFA?Inputanapayang dapatdi terima?Apasajayang diterima?

19. •DFA atauNFA?Inputanapayang dapatdi terima?Apasajayang diterima?

20. •DFA atauNFA?Inputanapayang dapatdi terima?Apasajayang
diterima?

21. •DFA atauNFA?Inputanapayang dapatdi terima?Apasajayang diterima?