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 :

(q₀,0000111110,$) ® (q₁,0000111110,$) ®  (q₁,000111110,0$) ®(q₁,00111110,00$) ®

(q₁,0111110,000$) ®(q₁,111110,0000$) ®(q₂, 11110,10000$) ®(q₃, 1110,0000$) ®

(q₂, 110,10000$) ®(q₃,10,0000$) ®(q₂,0,10000$) ®(q₄,e,110000$)