Soal-Jawab FAutomata (Add2) [PDF]

Citation preview

Nama NIM



: Putri Usriyatul Fauziah : 2502027296 Tugas Personal ke-2 Minggu 7



1. Pada diagram deterministic finite automata (DFA) berikut ini :



a. Gambarkan tabel transisi (next state table)



Q : {S0, S1, S2, S3, S4} ∑ : {0, 1} S : S0 F : {S2, S3}



ᵟ



0



1



S0 S1 S2 S3 S4



S1 S2 S2 S4 S0



S3 S1 S1 S2 S3



b. Buatlah 3 contoh string yang diterima dari DFA tersebut. String



Status



010 11101 00111 01101 101010100 1100101



Diterima Diterima Diterima Ditolak Ditolak Diterima



MATH6184 – Discrete Mathematics and Linear Algebra



2. Desainlah sebuah finite state automata (DFA) sederhana dengan input {a,b) dan menerima himpunan semua string dengan panjang (jumlah input) paling sedikit dua dimana dua terakhir simbol mempunyai input yang sama. b



b



q0



Q : {q0, q1, q2, q3, q4}



q1



∑ : {a, b} a b



S : q0



a



a



F : {q1, q4}



b



q4



q3



a



q2 b



a



Tabel Transisi



Input String



ᵟ



a



b



String



Status



q0 q1 q2 q3 q4



q2 q2 q3 q0 q4



q1 q1 q4 q4 q1



abbab baba abbaabb ababb aababab bababaabab abbabbababb babaabbb



Ditolak Ditolak Diterima Diterima Ditolak Ditolak Diterima Diterima



MATH6184 – Discrete Mathematics and Linear Algebra