Pengertian, Contoh Soal NFA dan Jawabannya
Pengertian dan contoh soal equivalen NFA - Teori Bahasa dan Automata merupakan salah satu mata kuliah jurusan Teknik Informatika. Tujuan utama dari mata kuliah bahasa automata adalah memperkenalkan teori awal yang dapat dimanfaatkan dalam mempraktiskan Teknik Kompilasi.
Dalam teori bahasa Automata, kita akan menemukan beberapa materi seperti Hierarki Chomsky (Tata bahasa regular, bebas konteks/context free, context sensitive, unrestricted/natural language). Saya tidak membahasnya di sini.
Finite State Automata (FSA) adalah contoh mesin otomata bahasa regular yang dinyatakan dalam 5 tupel, yaitu:
Reduksi Jumlah State Finite State Automata berfungsi untuk memilih state otomata praktis yang ditandai dengan jumlah state yang paling sedikit.
Reduksi artinya mengurangi jumlah state pada FSA tanpa mengurangi kemampuan dari suatu mesin otomata dengan cara menentukan distinguishable (Bisa dibedakan) dan indistinguishable (tidak bisa dibedakan).
Ekuivalensi Non-Deterministic Finite Automata(NFA) ke Deterministic Finite Automata (DFA)
Ekuivalensi atau bersesuaian pada mesin automata artinya mesin tersebut dapat menerima bahasa yang sama.
Untuk lebih mudahnya, kita lihat saja contoh soal dari ekuivalen FSA dengan NFA.
1. Buatlah Deterministic Finite Automata yang ekuivalen dengan Non-Deterministic Finite Automata berikut.
Q = {p, q, r, s}
∑ = {0, 1}
S = p
F = {s}
s
s
Berikut jawaban dari soal di ekuivalen NFA di atas.
2. Buatlah Deterministic Finite Automata yang ekuivalen dengan Non-Deterministic Finite Automata berikut.
Q = {p, q, r, s}
∑ = {0, 1}
S = p
F = {q, s}
Fungsi transisi seperti pada tabel di bawah!
Jawabannya!
3. Buatlah Deterministic Finite Automata yang ekuivalen dengan Non-Deterministic Finite Automata berikut.
Q = {q0, q1, q2}
∑ = {0, 1}
S = q0
F = {q1}
Fungsi transisi seperti pada tabel di bawah!
Jawaban di dalam gambar!
4. Buatlah Deterministic Finite Automata yang ekuivalen dengan Non-Deterministic Finite Automata berikut.
Q = {q0, q1, q2}
∑ = {a, b}
S = q0
F = {q1}
Fungsi transisi seperti pada tabel di bawah!
Berikut jawaban contoh soal NFA di atas!
Lihat juga Cara mencari KPK dan FPB
Demikianlah materi tentang teori bahasa dan automata lengkap dengan contoh soal dan jawaban NFA. Semoga bermanfaat.
![]() |
Pengertian, Contoh Soal NFA dan Jawabannya |
Finite State Automata (FSA) adalah contoh mesin otomata bahasa regular yang dinyatakan dalam 5 tupel, yaitu:
- Q = Himpunan state
- ∑ = Himpunan simbol input
- ծ = Fungsi transisi
- S = State awal (Initial State)
- F = Himpunan Finish state
Reduksi Jumlah State Finite State Automata berfungsi untuk memilih state otomata praktis yang ditandai dengan jumlah state yang paling sedikit.
Reduksi artinya mengurangi jumlah state pada FSA tanpa mengurangi kemampuan dari suatu mesin otomata dengan cara menentukan distinguishable (Bisa dibedakan) dan indistinguishable (tidak bisa dibedakan).
Ekuivalensi Non-Deterministic Finite Automata(NFA) ke Deterministic Finite Automata (DFA)
Ekuivalensi atau bersesuaian pada mesin automata artinya mesin tersebut dapat menerima bahasa yang sama.
Untuk lebih mudahnya, kita lihat saja contoh soal dari ekuivalen FSA dengan NFA.
1. Buatlah Deterministic Finite Automata yang ekuivalen dengan Non-Deterministic Finite Automata berikut.
Q = {p, q, r, s}
∑ = {0, 1}
S = p
F = {s}
ծ | 0 | 1 |
p | {p, q) | {p} |
q | {r) | {r} |
r | {s} | - |
s |
s
s
Berikut jawaban dari soal di ekuivalen NFA di atas.
![]() |
Pengertian, Contoh Soal NFA dan Jawabannya |
2. Buatlah Deterministic Finite Automata yang ekuivalen dengan Non-Deterministic Finite Automata berikut.
Q = {p, q, r, s}
∑ = {0, 1}
S = p
F = {q, s}
Fungsi transisi seperti pada tabel di bawah!
ծ | 0 | 1 |
p | {q, s) | {q} |
q | {r) | {q, r} |
r | {s} | {p} |
s | - | {p} |
Jawabannya!
![]() |
Contoh Soal NFA |
3. Buatlah Deterministic Finite Automata yang ekuivalen dengan Non-Deterministic Finite Automata berikut.
Q = {q0, q1, q2}
∑ = {0, 1}
S = q0
F = {q1}
Fungsi transisi seperti pada tabel di bawah!
ծ | 0 | 1 |
q0 | {q0) | {q2} |
q1 | {q1) | 0 |
q2 | {q0, q1} | {q1} |
Jawaban di dalam gambar!
![]() |
Contoh Soal NFA Lengkap dengan Jawaban |
Q = {q0, q1, q2}
∑ = {a, b}
S = q0
F = {q1}
Fungsi transisi seperti pada tabel di bawah!
ծ | a | b |
---|---|---|
q0 | {q1, q2) | {q2} |
q1 | {q1) | {q2} |
q2 | 0 | {q0, q2} |
Berikut jawaban contoh soal NFA di atas!
![]() |
Contoh Soal NFA dan Jawabannya |
Lihat juga Cara mencari KPK dan FPB
Demikianlah materi tentang teori bahasa dan automata lengkap dengan contoh soal dan jawaban NFA. Semoga bermanfaat.
Posting Komentar untuk "Pengertian, Contoh Soal NFA dan Jawabannya"