23 June 2016

Soal dan Jawaban UAS TBO Genap 2015-2016

Sodara-sodara semuanya.  Kali ini saya akan memposting tentang Soal dan Jawaban TBO UAS Semester Genap 2015-2016.

Kalo ada yang merasa sakit hati karena jawaban ngga cocok bisa datang untuk mendiskusikan........(tapi jangan lupa bawa gorengan dan kopi......xixixixiix...)

Soal dan jawaban dari UAS TBO tersebut adalah :
1.      Ubahlah bentuk Reguler Expresion berikut menjadii bentuk Finite Automata :

R = ( 0 È 1 )* 101

Jawaban :

Buat dahulu definisi FA untuk masing-masing 0 dan 1, sebagai berikut :
Gambar 1. 


Gambar 2. Reform dari Reguler Expression ke bentuk Finite State Automata 


2.     Diketahui sebuah Grammar G=(V, ∑, R, S), dimana V, ∑ dan R adalah sebagai berikut :
V = {S, A}
∑ = {a, b }
R =   { S à aAS
            S à a
            A à SbA
            A à SS
            A à ba}.

Buktikan bahwa string ini : aaaaabaa  dan ababaaabaa bisa diselesaikan oleh grammar tersebut !
Gambarkan Derivation Tree-nya !

Jawaban untuk string aaaaabaa adalah :
Parsingnya adalah :
aAS
aSbAS
aaASbAS
aaSSSbAS
aaaaabAS
aaaaabSSS
aaaaabaaa

Gambar 3. Parsing Tree


Jawaban untuk string ababaaabaa adalah :
String tersebut tidak bisa diselesaikan oleh Grammer yang ada, karena :
S à aAS
è aSbaS
Pada S yang depan pilihannya ada 2, yaitu : aAS dan a
Kalau dipilih aAS, maka a pada barisan depan string menjadi aa padahal seharusnya hanya a terus dilanjutkan ke b, sehingga tidak bisa dilanjutkan.
Bila dipakai a, maka a barisan depan string menjadi aa, sehingga alasanya sama dengan yang di atas.
è aSSS
Bila pilihan A menjadi SS, maka minimum a di barisan depan string adalah aa, padahal yang di string input hanya satu a, sehingga ini tidak bisa dilanjutkan.

 3.     Diketahui Sebuah mesin PDA (Pushdown Automata) sebagai berikut :


Gambar 4. Mesin PDA untuk soal nomor 3
Bila input string dan kondisi stack pada saat waktu =0, adalah :
  
Input string :
Gambar 5. Input string untuk mesin PDA pada gambar 4
  • Bacalah semua string dengan mesin PDA tersebut, dan lihatlah bagaimana isi tumpukan setelah semua perintah pada mesin PDA selesai dikerjakan !
  • Diskripsikan secara instan urutan pembacaan mesin PDA tersebut !

Jawaban :
  • Bila semua string seleain semua dibaca  dengan menggunakan mesin PDA tersebut, maka isi dari stack terakhir adalah :
    Gambar 6.  Susunan stack setelah semua string terbaca oleh mesin PDA
  •         Diskripsi secara instan urutan prosesnya adalah sebagai berikut :

(q0,0000111110,$) ® (q1,0000111110,$) ®  (q1,000111110,0$) ®(q1,00111110,00$) ®
(q1,0111110,000$) ®(q1,111110,0000$) ®(q2, 11110,10000$) ®(q3, 1110,0000$) ®
(q2, 110,10000$) ®(q3,10,0000$) ®(q2,0,10000$) ®(q4,e,110000$)







No comments:

Post a Comment