VIRLAB

Virtual Lab ATA 2006 – 2007

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.      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)

<ekspresi>

<suku>

                                                           <suku>               <mdop>                         <faktor>

                                  

                               <faktor>                                               <ekspresi>

                                                        <ekspresi>                                                <suku>                 

                         <ekspresi>              <asop>             <suku>         <suku>       <mdop>     <faktor>

                                 

     <ekspresi> <asop>   <suku>                               <faktor>      <faktor>                        <operand>

                     

       <suku>               <suku><mdop><faktor>     <operand> <operand>                           

      <faktor>          <faktor> <operand>                  

    <operand>      <operand>            

                                              

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

<ekspresi>

<suku>

                                   <suku>                                    <mdop>                                        <faktor>

   <suku>                 <mdop>           <faktor>                                                      <operand>

                                                                                      

  <faktor>                                         <ekspresi>                                                                     

 <operand>         <ekspresi>                  <asop>             <suku>

              <suku>            <mdop>  <faktor>                                <faktor>

              <faktor>                  <operand>                           <operand>

           <operand>                                                                

                  

                                                                                                                                                       

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

<ekspresi>

           <suku>

                                    <suku>                                                <mdop>                                     <faktor>

 

                                                       <ekspresi>                

       <suku>            <mdop>          <faktor>

      <faktor>          *                 <ekspresi>                                                  <ekspresi>       <asop>           <suku>

                                                                                                                          

   <operand>            <ekspresi>   <asop>       <suku>                                  <suku>                                      <faktor>

                                  <suku>                           <faktor>                <suku>   <mdop>   <faktor>           <operand>

                                   <faktor >                     <operand>            <faktor>                          <operand>              

                                 <operand>                                                 <operand>                      

                                                                                                      

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

<ekspresi>

                                                     <ekspresi>            <asop>                                         <suku>

                                                      <suku>                                                            <faktor>

                                                      <faktor>                                                       <ekspresi>                  

                                                     <ekspresi>                                        <suku>              <mdop>     <faktor>

                            <suku >             <mdop>      <faktor>                               <faktor>                     <operand>

              <suku>            <faktor>                     <operand>                    <ekspresi>

           <faktor>                      <operand >                                     <ekspresi> <asop>        <suku>       

           <operand>                                                                    <suku>                             <factor>

                                                                                          <factor>                          <operand>

                                                                                    <operand>        

                                                                                                                                                             

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)