1. Masalah: Membuat dan menjelaskan konsep dasar serta penyelesaian soal menggunakan diagraph finite state automata (FSA). 2. Konsep Dasar: Finite State Automata adalah model matematika yang digunakan untuk merepresentasikan mesin dengan sejumlah keadaan (states) terbatas dan transisi antar keadaan berdasarkan input. 3. Komponen FSA: - States (Q): Kumpulan keadaan yang mungkin. - Alphabet (\Sigma): Kumpulan simbol input. - Transition function (\delta): Fungsi yang menentukan transisi dari satu state ke state lain berdasarkan input. - Start state (q_0): Keadaan awal. - Accept states (F): Keadaan yang menandakan penerimaan input. 4. Penyelesaian Soal: Misalkan kita ingin membuat FSA yang menerima string biner yang berakhiran dengan '01'. - States: Q = \{q_0, q_1, q_2\} - Alphabet: \Sigma = \{0,1\} - Start state: q_0 - Accept state: q_2 - Transition function: \delta(q_0,0) = q_1 \delta(q_0,1) = q_0 \delta(q_1,0) = q_1 \delta(q_1,1) = q_2 \delta(q_2,0) = q_1 \delta(q_2,1) = q_0 5. Penjelasan: - q_0 adalah keadaan awal, menerima input 1 tetap di q_0, input 0 pindah ke q_1. - q_1 menandakan bahwa input terakhir adalah 0, jika input berikutnya 1 maka pindah ke q_2. - q_2 adalah keadaan penerimaan yang menandakan string berakhiran '01'. 6. Diagram: - q_0 --0--> q_1 - q_0 --1--> q_0 - q_1 --0--> q_1 - q_1 --1--> q_2 - q_2 --0--> q_1 - q_2 --1--> q_0 Diagram ini menggambarkan transisi antar state berdasarkan input. Jawaban akhir: FSA yang menerima string biner berakhiran '01' dengan states dan transisi seperti di atas.