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.

Pengertian, Contoh Soal NFA dan Jawabannya

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!

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!

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.

Berbagi :