Ekuivalensi Non-Deterministik Finite Automata (NFA) 1 ke Deterministik Finite Automata (DFA) 2

Perhatikan dan ingat kembali NFA pada Design Non-Deterministic Finite Automata 2

 

Design the NFA

                                                     Transition Table

 

 

Dari diagram dan tabel NFA, maka kita bisa mendapatkan DFA yang ekuivalen dengan menambahkan lagi 1 state dengan input Ø ,  

Equivalance NFA to DFA 1

Please remember...on Design Non-Deterministic Finite Automata 1

 

Equivalance

 

Equivalance Non-deterministic Finite Automata (NFA) - Deterministic Finite Automata (DFA)

Buatlah DFA yang ekuivalen dengan NFA berikut :
Q   = { p, q, r, s }

∑   = { 0, 1 }
S    = p
F   = { q, s }

Fungsi Transisi

ᵟ	0	1
p	q,s	q
q	r	q,r
r	s	p
s	—	p

Jawab:
pencarian DFA yang ekuivalen dengan NFA diatas dapat dilakukan dengan langkah mudah sebagai berikut:
"perhatikan, pengerjaan dilakukan dengan tabel transisi. diagram DFA digambar setelah semua selesai."
Step 1: membuat tabel transisi NFA:

ᵟ	0	1
{p}	{q,s}	{q}
{q}	{r}	{q,r}
{r}	{s}	{p}
{s}	{ }	{p}

berdasarkan tabel step1 dapat diidentifikasi sbb;

• ({p},0) = ( {q,s})
• ({p},1) = ( {q})
• ({q},0) = ( {r})
• ({q},1) = ( {q,r})
• ({r},0)  = ( {s})
• ({r},1)  = ( {p})
• ({s},0) =  ( { })
• ({s},1) =  ({p})

perhatikan muncul state baru (diwarnai merah) yang belum diketahui tujuannya, sebagai contoh {q,s} maka diselesaikan dengan cara berikut;
({q,s})?
({q},0)    ={r}
({s},0)    ={ }
---------------
({q,s},0) ={r}
dan,
({q},1)    ={q,r}
({s},1)    ={ p}
---------------
({q,s},1) ={p,q,r}

dengan cara yang mudah kita dapat menyelesaikan dengan tabel transisi DFA sebagai berikut:

ᵟ	0	1
p	{q,s}	{q}
q	{r}	{q,r}
r	{s}	{p}
s	{ }	{p}
({q,s})	{r}	{p,q,r}
({q,r})	{r,s}	{p,q,r}
({p,q,r})	{q,r,s}	{p,q,r}
({r,s})	{s}	{p}
({q,r,s})	{r,s}	{p,q,r}
{ }	{ }	{ }