Bahasa Regular yang Didefinisikan Deterministic Finite Automata (DFA)
Boby Satria1, Erma Wati2, Ferniawan3, Jhonny Roberto Saragih4, Miftahul Ghifrah5, Syahril Hasbi6
TATA BAHASA FORMAL NOAM CHOMSKY unrestricted sensitive context free context REGULAR
MESIN Aotomata
Nondeterministic Finite Automata (NFA)
Finite Automata (FA)
Deterministic Finite Automata (DFA)
perbandingan Nondeterministic Finite Automata (NFA)
untuk satu simbol masukan dapat mentransisikannya ke satu atau lebih state yang berbeda
maka
Deterministic Finite Automata (DFA)
untuk satu simbol masukan hanya bisa mentransisikan ke satu state
semua DFA merupakan bagian dari NFA, namun bukan sebaliknya.
diagram Nondeterministic Finite Automata (NFA)
Deterministic Finite Automata (DFA)
BAHASA REGULER Deterministic Finite Automata (DFA)
BAHASA REGULER Bahasa disebut bahasa regular jika himpunan string di bahasa itu adalah himpunan regular. Bahasa regular ini merupakan bahasa yang sangat banyak digunakan karena sifat-sifat dan properti-propertinya yang telah sangat diketahui dan telah ditemukan algortima yang efisien untuk pengoahannya. Bahasa regular pada dasarnya sangat baik jika diekspresikan menggunakan ekspresi regular.
BAHASA REGULER Himpunan Reguler Bahasa disebut bahasa reguler jika himpunan string di bahasa itu adalah himpunan reguler. Kelasa bahasa adalah sekumpulan bahasa yaitu himpunan dari himpunan-himpunan string. Bila VT adalah alphabet berhinga. Sehingga devinisi himpunan reguler pada VT adalah: 3. Ø (himpunan kosong) adalah himpunan regular pada VT. 4. {e} adalah himpunan reguler pada VT. 5. {a} adalah himpunan reguler pada VT. 6. Jika P dan Q adalah himpunan reguler pada VT, maka begitu juga dengan a. P ∪ Q b. PQ c. P*
BAHASA REGULER Ekspresi Reguler
Ekspresi regular adalah rumus yang berbentuk bagus (well-formed formula) pada operasi gabungan (union, dilambangkan dengan +), penyambungan (concatenation, dilambangkan dengan simbol satu bersebelahan dengan simbol berikutnya, xy), dan Kleene closure (dilambangkan dengan *). Bila VT adalah alphabet berhingga. Ekpresi regular pada VT dan himpunan regular yang dilambangkannya didefinisikan sebagai berikut: Ø adalah ekspresi regular yang menunjukkan himpunan regular Ø. e adalah ekspresi regular yang menunjukkan himpunan regular e. a pada VN adalah ekspresi regular yang menunjukkan himpunan regular { a }.
BAHASA REGULER Jika p dan q adalah ekspresi regular yang menunjukkan himpunan regular P dan Q, maka: (p+q) adalah ekspresi regular yang menunjukkan P ∪ Q. (pq) adalah ekpresi regular yang menunjukkan PQ. (p)* adalah ekpresi regular yang menunjukkan P*. Tidak ada yang selain itu yang merupakan ekspresi regular. Bahasa pada alphabet V adalah bahasa regular jika terdapat suatu ekspresi regular pada V yang berkorespodensi dengan bahasa itu.
BAHASA REGULER
Finite Automata
Dalam Arti Bahasa Finite
Automata
Terhingga
Otomatis
Batasan sudah ditentukan sehingga terlihat seakan otomatis
Deskripsi Finite Automata
Finite automata >> model matematika sistem dengan masukan dan keluaran diskrit.
State >> Sistem dapat berada di salah satu dari sejumlah berhingga konfigurasi internal.
State Sistem >> ringkasan informasi yg berkaitan dengan masukan-masukan sebelumnya yg diperlukan utk menentukan perilaku sistem pada masukan berikutnya.
Contoh sistem dgn state berhingga
>> sistem elevator >> vending machine (mesin minuman kaleng) >> traffic light regulator >> sirkit switching di komputer daan telkomunikasi >> protokol komunikasi >> lexival analyzer >> Neuron nets >> sistem computer
Finite State Diagram komputerisasi
Sistem diskrit dinamis
FA
FSD
Finite State Automata/Acceptor (FSA) Sifat-sifat FSA >>Memory ‘infinite’-nya adalah null, atau tidak ada memory sementara. >>Hanya berisi satu memory masukan berupa tape berisi string masukan dan sejumlah kendali berhingga. >>head hanya bergerak satu arah atau tidak dapat mundur. >>Mempunyai sejumlah berhingga status, setiap saat FSA berada pada status tertentu
Spesifikasi FA dgn mendefinisikan properti-properti berikut: >>Memiliki finite number of state atau satu himpunan state kendali berhingga. >>Simbol-simbol masukan yang dibolehkan/diijinkan. >>Memiliki state sebagai state mula (initial state). >>Memiliki himpunan state akhir (set of final state), yaitu state-state yang menandai diterimanya masukan (accepted state). >>Mesin menerima input simbol yang datang secara sekuensial.
>>Mesin akan bertransisi dari state satu ke state yang lain sesuai input. >>Mesin mungkin saja menerima string kosong (ε), jika ini terjadi maka initial state adalah sekaligus sebagai accepted state. >>Terdapat fungsi transisi state (state transition function) yaitu diberikan state saat itu (current state) dan simbol masukan saat itu (current input symbol), fungsi memberikan/menyatakan semua state berikutnya yang dimungkinkan. Semua kemungkinan transisi dipandang dijalankan secara pararel. Bila terdapat transisi yang menuju/sampai state akhir, berarti string masukan diterima automata tersebut.
Definisi formal DFA
>> FA adalah sebuah mesin dgn sebuah head baca dan kotak kendali state berhingga. >>mesin membaca memori masukan berupa tape >>satu karakter tiap satu saat >>pada mesin terdapat sejumlah state beringga >>Perubahan state terjadi pada mesin ketika sebuah karakter berikutnya dibaca sesuai dengan fungsi transisi.
DETERMINISTIC FINITE AUTOMATA (DFA)
Pernah Bermain
ULAR TANGGA
?!
Komponen-komponen permainannya apa saja? n x n kotak, Dadu, Penanda, Pemain
Bagaimana karakteristik permainannya?
Pola/arah perpindahan kotak/state dalam permainan tersebut bersifat tertentu/mutlak Jumlah kotak, jumlah dan jenis karakter input terbatas/berhingga Pergerakan pemain (seolah2) bersifat otomatis, ditentukan oleh hasil lemparan dadu
Deterministic Finite Automata
Deterministic finite Automata adalah 5 tupel =(Q, ∑, δ, qo, qn), dimana: ♣Q adalah himpunan state yang berhingga. ♣∑ adalah himpunan berhingga simbol/karakter masukan yang diijinkan. ♣ δ sebagai himpunan berhingga fungsi transisi untuk memindahkan kendali mesin. ♣ qo adalah keadaan mula dari kendali keadaan berhingga, dan ♣ qn adalah himpunan keadaan akhir.
DFA hanya mempunyai paling banyak satu transisi pada masingmasing state pada sembarang masukan.
Mula-mula DFSA akan berada pada status q0, kepala pita pada simbol pertama pada pita, selanjutnya kepala pita akan membaca simbol-simbol dari pita dan bergeser maju. Untuk setiap simbol, DFSA akan berpindah status sesuai dengan fungsi δ. Proses akan berakhir bila simbol masukan pada pita sudah habis, bila pada akhir proses dicapai status akhir maka string masukan diterima (dikenali sebagai string dari bahasa regular), dan bila tidak maka string masukan ditolak (tidak dikenali).
δ 0
Stat q e o A
δ
δ
1
2
δ 3
q n
Stat e A
Contoh DFA Yang Ekivalen Q = {q0, q1, q2} δ diberikan dalam tabel berikut :
Kalimat yang diterima oleh DFA : a, b, aa, ab, ba, aba, bab, abab, baba. Kalimat yang dittolak olehDFA : bb, abb, abba. DFA ini menerima semua kalimat yang tersusun dari simbol a dan b yang tidak mengandung substring bb.
abababaa aaaabab aaabbaba
diterima diterima ditolak
♣ δ (q0,abababaa) δ (q0,bababaa) δ (q1,ababaa) δ (q0,babaa) δ (q1,abaa) (q1,aa) δ (q0,a) q0 Tracing berakhir di q0 (state AKHIR) kalimat abababaa diterima ♣ δ (q0, aaaabab) δ (q0,aaabab) δ (q0,aabab) q1 Tracing berakhir di q1 (state AKHIR)
δ (q0,abab)
δ (q0,bab)
δ (q0,baa)
δ (q1,ab)
δ (q0,b)
kalimat aaaababa diterima
♣ δ (q0, aaabbaba) δ (q0, aabbaba) δ (q0, abbaba) δ (q0, bbaba) δ (q1,bbaba) δ (q2,baba) δ (q2,aba) δ (q2,ba) δ(q2,a) q2 Tracing berakhir di q2 (bukan state AKHIR) kalimat aaabbaba ditolak
δ
Algoritma DFA
Masukan
masukan X yang diakhiri dengan karakter (eos)
DFA D dimulai dari state dan himpunan state F
keluaran
Ya, jika D diterima x
Tidak, jika Dtidak diterima x
Algoritma fungsi
Fungsi move(s, c)
Fungsi nextchar()
Langkah-langkah algoritma: s ← so c ← next char() while c ≠ eos s ←” move(s, c) c ← nextchar() if s in F then return “YA” else return “TIDAK”
PENUTUP Finite Automata biasanya mengacu pada Deterministic Finite Automata (DFA)
Deterministic Finite Automata (DFA) adalah finite automata dengan aturan-aturan yang sangat ketat.
Semua DFA merupakan bagian dari NFA
Kedua FA tersebut mampu mengenali himpunan regular secara presisi kedua FA tersebut dapat mengenali string-string yang ditunjukkan dengan ekspresi regular secara tepat.
DFA dapat menuntun recognizer lebih cepat dibanding NFA
Lebih mudah membangun NFA dibanding DFA untuk suatu bahasa, namun lebih mudah mengimplementasikan DFA dibanding NFA.