Pengertian, Contoh Soal NFA dan Jawabannya

"Materi bahasa automata dan konversi, pengertian, contoh soal NFA ekuivalen dengan DFA dan jawabannya, logika ekspresi"

5 min read

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.

Pengertian dan contoh soal equivalen NFA

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

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!

Finite State Automata (FSA) dan NFA soal dan jawaban

Contoh Soal NFA Lengkap dengan 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}
q2	0	{q0, q2}

Berikut jawaban contoh soal NFA di atas!

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

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.