Skip to main content

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.

1. Buatlah Deterministic Finite Automata yang ekuivalen dengan Non-Deterministic Finite Automata berikut.

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:
  • Q = Himpunan state
  • ∑ = Himpunan simbol input
  • ծ = Fungsi transisi
  • S = State awal (Initial State)
  • F = Himpunan Finish state
Non-Deterministic Finite Automata (NFA) juga memiliki 5 tupel seperti FSA. Bedanya dengan FSA yang hanya memiliki satu simbol input di setiap state-nya, Non-Deterministic Finite Automata bisa memiliki lebih dari satu simbol input di setiap state-nya.

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
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!
Materi bahasa automata dan konversi, pengertian, contoh soal NFA ekuivalen dengan DFA dan jawabannya, logika ekspresi

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!
Finite State Automata (FSA) dan NFA soal dan jawaban

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!

ծ a b
q0 {q1, q2) {q2}
q1{q1){q2}
q20{q0, q2}

Berikut jawaban contoh soal NFA di atas!
1. Buatlah Deterministic Finite Automata yang ekuivalen dengan Non-Deterministic Finite Automata berikut.

Demikianlah materi tentang teori bahasa dan automata lengkap dengan contoh soal dan jawaban NFA. Semoga bermanfaat.
  March 01, 2019
Semoga Sukses: 1 Kalimat Terbaik dari Anda Adalah Motivasi Bagi Saya!
Bagaimana Pendapat Anda?
Terima Kasih!
close