Welcome to Chaky Blogspot

Selasa, 05 April 2011


Tugas PengantarTeknik Kompilasi ( PTK )

1.      Jelaskan apa yang dimaksud dengan Otomata dan Finite Automata (otomata berhingga)!
jawab : Otomata merupakan mesin abstrak yang dapat mengenali (recognize), menerima (accept) atau membangkitkan (generate) sebuah kalimat dalam bahasa tertentu . Sedangkan Finite Automata merupakan mesin abstrak yang terdiri dari Head Pembaca dan Kontak Kontrol Stata Hingga.


2.      Jelaskan apa yang di maksud dengan Regular Expresion (RE) !
jawab : RE (Regular Expresion) adalah bahasa regular dapat dinyatakan sebagai ekspresi regular dengan menggunakan 3 operator : concate, alternate, dan closure.

3.      Diketahui Grammar, dengan himpuinan simbol terminal { a, b} dan produksi sebagai berikut ( huruf kecil menyatakan simbol terminal )
S à a
S à Sa
S à b
S à bS
Jelaskan bagaimana bentuk umum dari untai yang dibentuk oleh Grammar tersebut.
jawab : Grammar diatas terdiri dari produksi berbentuk :
α  à β dengan │α│ ß│β│. Dimana α ialah string dan │α│ ialah panjang dari string α demikian juga  β ialah string  dan│β│ ialah panjang dari string β. String disini adalah merupakan deretan simbol baik terminal maupun non terminal.

4.    
4.      Buatlah pohon derivasi untuk ekspresi bentuk berikut :
·            ( x – y * 2 + z ) div ( x div z )
·           a * ( 2 * c – b ) * 2
·           x * ( y – 5 ) * ( y div 4 + x )
·           ( x * 2 * y ) – ( ( z + 32 ) div y )
Jawab :








·          (x-y*2+z) div (x div z)








                                                                                                   
Oval: divv                                  
                                                                              









Oval: (
Oval: )
Oval: (
Oval: )


                                                                                                                         

                                                                         
Oval: +                                 
Oval: divv                                                                      
Oval: zOval: -                     
                                                       





Oval: z
Oval:  x


Oval:  2                                   

Flowchart: Connector: *                      





Oval:  x
Oval:   y


                                              







·         a*(2*c-b)*2




                                                                                                               


Flowchart: Connector: *


                                                                                     
Oval: )Oval: (                                                                                      
Flowchart: Connector: *Oval:  2                                                                                                                

                                        

Oval:  aOval:  -                                                            

Flowchart: Connector: *                                                           

Oval:  cOval:  b                                                                           

Oval:  2                  






                                                                                                                                                       

·         **(y-5) * (y div 4+*)


          


                                    <suku>                                                <mdop>                                     <faktor>
Flowchart: Connector: )Flowchart: Connector: ( 
Flowchart: Connector: *                                                       <ekspresi>                
       <suku>            <mdop>          <faktor>





Flowchart: Connector: (
Flowchart: Connector: )


Flowchart: Connector: *      <faktor>          *                 <ekspresi>                                                  <ekspresi>       <asop>           <suku>
                                                                                                                          
Flowchart: Connector: +               <ekspresi>   <asop>       <suku>                                  <suku>                                      <faktor>

Flowchart: Connector: *Flowchart: Connector:   -                                  <suku>                           <faktor>                <suku>   <mdop>   <faktor>           

Oval: divvFlowchart: Connector: *                                   <faktor >                                 <faktor>                                        

Flowchart: Connector:  4Flowchart: Connector:   5                                                                                                        

Flowchart: Connector:  yFlowchart: Connector:  y                                                                                                      





·         (x*2*y)-((z+32) div y)



                                                                                                          

Oval:  -                                                                                                                  





Oval: (
Oval: )


                                                                                                                               





Oval: (
Oval: )


                                                                                                               

Oval: div ddivdiv                                                                                                   








Oval: (

Flowchart: Connector: *

Oval: )



Oval: yFlowchart: Connector: *                                                                   

Oval:  y                                                                                      

Oval:  +Oval:  2                                                                                                            


Oval:  x


                                                                                                                   

Oval: 322                                                                                            


Oval:  z


                                                                                                                                                             




5.      jawablah pertanyaan dibawah ini :
a.  Gambarkan diagram transisi dari Deterministic Finite Automata berikut :
Q : {q0, q1, q2, q3}
∑ : {a, b}
S : q0
F : {q0, q1, q2}, dengan fungsi transisi dari DFA tersebut adalah :
Δ
a
b
q0
q0
q1
q1
q0
q2
q2
q0
q3
q3
q3
q4
    
 b.  Buatlah tabel transisi dari Deterministic Finite Automata berikut, dan tentukan apakah string berikut dapat diterima oleh Deterministic Finite Automata :
1101
0101
1001



                       
                  Jawab :


a.    
 









stata
0
1
q0
q2
q1
q1
q3
q0
q2
q0
q3
q3
q1
q2









b. 

              Penelusuran string 1101 :                                          Penelusuran string
              M(q0, 1101)=M(q1, 101)                                          M(q0, 0101) =M(q2, 101)
                                  =M(q0, 01)                                                                 =M(q3, 01)
                                  =M(q2, 1)                                                                   =M(q1, 1)
                                  =M(q3, ^)                                                                   =M(q0, ^)
                                  =q3(ditolak)                                                               =q0(diterima)
             






              Penelusuran string 1001 :
  M(q0, 1001) =M(q1, 001)
                       =M(q3, 01)
                       =M(q1, 1)
                       =M(q0, ^)
                       =q0(diterima)

Tidak ada komentar:

Poskan Komentar