Friday 19 May 2017

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}
{ }
{ }
{ }





No comments:

Post a Comment

Note: only a member of this blog may post a comment.