Regular expressions

contoh soal dan pengerjaan :

Buatlah RE dari DFSA berikut 

 

 

 

Demikianlah salah satu contoh di atas untuk Regular expressions semoga dapat membantu teman-teman semua.

NDFA (Non Deterministik Finite Automata)

NDFA (Non Deterministik Finite Automata)

Dari suatu state ada 0, 1 atau lebih state    berikutnya untuk setiap simbol masukan yang diterima.
Non-Deterministic Finite Automata:

• Otomata berhingga yang tidak pasti untuk setiap pasangan state input, bisa memiliki 0 (nol) atau lebih pilihan untuk state berikutnya.

•   Untuk setiap state tidak selalu tepat ada satu state berikutnya untuk setiap simbol input yang ada.

• Dari suatu state bisa terdapat 0,1 atau lebih busur keluar (transisi) berlabel simbol input yang sama.

• Untuk NFA harus dicoba semua kemungkinan yang ada sampai terdapat satu yang mencapai state akhir.

• Suatu string x dinyatakan diterima oleh bahasa NFA, M= (Q, _, d, S, F) bila {x | d (S,x) memuat sebuah state di dalam F}

Kedua finite automata di atas mampu mengenali himpunan reguler secara presisi. Dengan demikian kedua finite automata itu dapat mengenali string-string yang ditunjukkan dengan ekspresi reguler secara tepat.

DFA dapat menuntun recognizer(pengenal) lebih cepat dibanding NDFA. Namun demikian, DFA berukuran lebih besar dibanding NDFA yang ekivalen dengannya. Lebih mudah membangun NDFA dibanding DFA untuk suatu bahasa, namun lebih mudah mengimplementasikan DFA dibanding NDFA.

Contoh pengerjaan NDFA :

Diketahui sebuah mesin A = ({q0,q1,q2,q3,q4}, {a,b}, δ,q0,{q0,q2,q3}) dengan  dengan State diagram sebagai berikut: :

 Pada gbr di atas bila Mesin A diinputkan string ababa, maka
      (q0,ababa)      ├A (q1,baba)
                             ├A (q2,aba)
                             ├A (q3,ba)
                             ├A (q2,a)
                             ├A (q3,e)
Karena (q0,ababa)├*A (q3,e), maka string ababa diterima oleh mesin A

2. Tabel Transisinya seperti gambar berikut :

3.  Pembuktian string ababaabba :

        (q0,ababaabba)      ├A (q1,babaabba)
                                      ├A (q2,abaabba)
                                      ├A (q3,baabba)
                                      ├A (q2,aabba)
                                      ├A (q3,abba)
                                      ├A (q1,bba)
                                      ├A (q2,ba)
                                      ├A (q4,a)
                                      ├A (q4,e)                             

Karena (q0,ababa)├*A (q4,e), maka string ababa ditolak oleh mesin A

4. tree path   sebagai berikut :