The Sampah's Blog

Non-Determistic Finete Aoutomata

Posted on: June 15, 2010

Definisi

  • Sebuah NFA dirumuskan mirip dengan DFA

A= (Q, å, d, q0, F)

  • Q : himpunan State
  • å : himpunan input symbol
  • d : Fungsi Transisi
  • q0 : Start state
  • F   : himpunan final state
  • Perbedaan NFA dan DFA adalah pada karakteristik fungsi transisi-nya
    • DFA: Satu simbol untuk satu transisi
    • NFA: Satu simbol dapat memiliki beberapa transisi

Bahasa NFA

  • Suatu bahasa yang diterima oleh sebuah NFA A didefinisikan sbb.: L(A)= {w|d(q0,w) Ç F ¹ Æ}

Contoh: NFA


Contoh: Tabel Transisi


Contoh: Memproses Input


Ekuivalensi NFA dan DFA

  • Setiap bahasa yang dapat dideskripsikan oleh suatu NFA dapat pula dideskripsikan oleh suatu DFA

–      DFA terkecil memiliki state berjumlah 2n

–      NFA terkecil untuk bahasa yang sama memiliki state berjumlah n

–      Subset construction

Ekuivalensi NFA dan DFA

  • Subset Construction

–      Dari sebuah NFA N= (QN, åN, dN, q0, FN). Maka tujuannya adalah mencari sebuah DFA D = (QD, åD, dD, q0, FD) sehingga L(D)=L(N)

  • QD adalah himpunan dari subset dari QN
  • FD adalah himpunan dari subset S dari QN sehingga S Ç FN = Æ

Contoh: Subset Construction

Contoh: Renaming


Contoh: DFA Ekuivalen


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


  • Mr WordPress: Hi, this is a comment.To delete a comment, just log in, and view the posts' comments, there you will have the option to edit or delete them.

Categories

%d bloggers like this: