Pages

Subscribe Twitter

Selasa, 27 Maret 2012

LP TBO Pert 1 - 4

LP TBO Pert 1

MATERI : Pengenalan Automata

1.Sebutkan pengertian dari Automata !
2.Sebutkan 4 klasifikasi tipe grammar & cirri-cirinya menurut Noam Chomsky !
3 .Sebutkan dan jelaskan dua jenis Automata Hingga!

*jawaban*

1. Automata adalah mesin abstrak yang dapat mengenali (recognize), menerima (accept), atau membangkitkan (generate) sebuah kalimat dalam bahasa tertentu.

2. Berdasarkan komposisi bentuk ruas kiri dan ruas kanan produksinya (α → β), Noam Chomsky mengklasifikasikan 4 tipe grammar :
1. Grammar tipe ke-0 : Unrestricted Grammar (UG)
. Ciri : α, β
(VT | VN) *, α> 0
2. Grammar tipe ke-1 : Context Sensitive Grammar (CSG)
. Ciri : α, β
(VT | VN) *, 0 < α ≤ β
3. Grammar tipe ke-2 : Context Free Grammar (CFG)
. Ciri : α
VN, β (VT | VN) *
4. Grammar tipe ke-3 : Regular Grammar (RG)
. Ciri : α
VN, β { VT , VT VN} atau α VN, β { VT , VN VT}

3. Ada dua jenis automata hingga : deterministik (AHD, DFA = deterministic finite automata) dan non deterministik (AHN, NFA = non deterministik finite automata).
- AHD : transisi stata AH akibat pembacaan sebuah simbol bersifat tertentu.
. σ (AHD) : Q × V T → Q
- AHN : transisi stata AH akibat pembacaan sebuah simbol bersifat tak tentu.
. σ (AHN) : Q × V T → 2Q

. σ (AHN) : Q × V T → 2Q
---------------------------------------------------------------------------------------------

LP TBO Pert 2

1. Apa yg kamu ketahui tentang mesin turing?
2. Apa yg kamu ketahui tengtang MSH (Mesin Stata Hingga)?

*jawaban*
1. Mesin Turing adalah model komputasi teoritis yang ditemukan oleh Alan Turing, berfungsi sebagai model ideal untuk melakukan perhitungan matematis. mesin turing terdiri atas barisan sel tersusun berupa pita yang dapat bergerak maju mundur, komponen aktif baca/tulis pita yang memiliki status perhitungan serta dapat mengubah/menulisi sel aktif yang ada di pita tadi, dan suatu kumpulan instruksi bagaimana komponen baca/tulis ini harus melakukan modifikasi terhadap sel aktif pada pita, serta bagaimana menggerakkan pita tersebut.

2. Mesin Stata Hingga (MSH)
§  MSH atau FSM (Finite State Machine) adalah sebuah varians automata hingga. MSH sering juga disebut sebagai automata hingga beroutput atau mesin sekuensial.
§  MSH didefinisikan sebagai pasangan 6 tupel F(K, V, S, Z, f, g) dimana :
K : himpunan hingga stata,
V : himpunan hingga simbol input (alfabet)
S Î K : stata awal
Z : himpunan hingga simbol output
f : K ´ V ® K disebut fungsi next state
g : K ´ V ® Z disebut fungsi output

---------------------------------------------------------------------------------------------

LP TBO Pert 3

1. apa yang kalian ketahui tentang CFG?
2. sebutkan dan jelaskan jenis2 metode parsing!
3. apa yang kalian ketahui ttg metode brute force ?

*jawaban*


1. CFG ( Context Free Grammar )

   CFG / Bahasa Bebas Konteks adalah sebuah tata bahasa dimana tidak terdapat pembatasan pada hasil produksinya, Contoh Pada aturan produksi :
a b
batasannya hanyalah ruas kiri (a) adalah sebuah simbol variabel. Sedangkan contoh aturan produksi yang termasuk CFG adalah seperti di bawah :
B CDeFg
D BcDe
Tata bahasa bebas konteks ( CFG ) adalah tata bahasa yang mempunyai tujuan sama seperti halnya tata bahasa regular yaitu merupakan suatu cara untuk menunjukkan bagaimana menghasilkan suatu untai-untai dalam sebuah bahasa.

2. #Ada 2 metoda parsing : 
>> Parsing top-down : Diberikan kalimat x sebagai input. Parsing dimulai dari simbol awal  S sampai kalimat x nyata (atau tidak nyata jika kalimat x memang  tidak bisa diturunkan dari S) dari pembacaan semua leaf dari pohon  parsing jika dibaca dari kiri ke kanan. 
>>Parsing bottom-up : Diberikan kalimat x sebagai input. Parsing dimulai dari kalimat x  yang nyata dari pembacaan semua leaf pohon parsing dari kiri ke  kanan sampai tiba di simbol awal S (atau tidak sampai di S jika kalimat x memang tidak bisa diturunkan dari S)

3.Metoda Brute-Force
         Kelas metoda dengan backup, termasuk metoda Brute-Force, adalah kelas metoda  parsing yang menggunakan produksi alternatif, jika ada, ketika hasil penggunaan sebuah  produksi tidak sesuai dengan simbol input. Penggunaan produksi sesuai dengan nomor urut  produksi . 
            Metoda Brute-Force tidak dapat menggunakan grammar rekursi kiri, yaitu grammar yang  mengandung produksi rekursi kiri (left recursion) : A
A. Produksi rekursi kiri akan  menyebabkan parsing mengalami looping tak hingga.

0 komentar:

Posting Komentar

Selasa, 27 Maret 2012

LP TBO Pert 1 - 4


LP TBO Pert 1

MATERI : Pengenalan Automata

1.Sebutkan pengertian dari Automata !
2.Sebutkan 4 klasifikasi tipe grammar & cirri-cirinya menurut Noam Chomsky !
3 .Sebutkan dan jelaskan dua jenis Automata Hingga!

*jawaban*

1. Automata adalah mesin abstrak yang dapat mengenali (recognize), menerima (accept), atau membangkitkan (generate) sebuah kalimat dalam bahasa tertentu.

2. Berdasarkan komposisi bentuk ruas kiri dan ruas kanan produksinya (α → β), Noam Chomsky mengklasifikasikan 4 tipe grammar :
1. Grammar tipe ke-0 : Unrestricted Grammar (UG)
. Ciri : α, β
(VT | VN) *, α> 0
2. Grammar tipe ke-1 : Context Sensitive Grammar (CSG)
. Ciri : α, β
(VT | VN) *, 0 < α ≤ β
3. Grammar tipe ke-2 : Context Free Grammar (CFG)
. Ciri : α
VN, β (VT | VN) *
4. Grammar tipe ke-3 : Regular Grammar (RG)
. Ciri : α
VN, β { VT , VT VN} atau α VN, β { VT , VN VT}

3. Ada dua jenis automata hingga : deterministik (AHD, DFA = deterministic finite automata) dan non deterministik (AHN, NFA = non deterministik finite automata).
- AHD : transisi stata AH akibat pembacaan sebuah simbol bersifat tertentu.
. σ (AHD) : Q × V T → Q
- AHN : transisi stata AH akibat pembacaan sebuah simbol bersifat tak tentu.
. σ (AHN) : Q × V T → 2Q

. σ (AHN) : Q × V T → 2Q
---------------------------------------------------------------------------------------------

LP TBO Pert 2

1. Apa yg kamu ketahui tentang mesin turing?
2. Apa yg kamu ketahui tengtang MSH (Mesin Stata Hingga)?

*jawaban*
1. Mesin Turing adalah model komputasi teoritis yang ditemukan oleh Alan Turing, berfungsi sebagai model ideal untuk melakukan perhitungan matematis. mesin turing terdiri atas barisan sel tersusun berupa pita yang dapat bergerak maju mundur, komponen aktif baca/tulis pita yang memiliki status perhitungan serta dapat mengubah/menulisi sel aktif yang ada di pita tadi, dan suatu kumpulan instruksi bagaimana komponen baca/tulis ini harus melakukan modifikasi terhadap sel aktif pada pita, serta bagaimana menggerakkan pita tersebut.

2. Mesin Stata Hingga (MSH)
§  MSH atau FSM (Finite State Machine) adalah sebuah varians automata hingga. MSH sering juga disebut sebagai automata hingga beroutput atau mesin sekuensial.
§  MSH didefinisikan sebagai pasangan 6 tupel F(K, V, S, Z, f, g) dimana :
K : himpunan hingga stata,
V : himpunan hingga simbol input (alfabet)
S Î K : stata awal
Z : himpunan hingga simbol output
f : K ´ V ® K disebut fungsi next state
g : K ´ V ® Z disebut fungsi output

---------------------------------------------------------------------------------------------

LP TBO Pert 3

1. apa yang kalian ketahui tentang CFG?
2. sebutkan dan jelaskan jenis2 metode parsing!
3. apa yang kalian ketahui ttg metode brute force ?

*jawaban*


1. CFG ( Context Free Grammar )

   CFG / Bahasa Bebas Konteks adalah sebuah tata bahasa dimana tidak terdapat pembatasan pada hasil produksinya, Contoh Pada aturan produksi :
a b
batasannya hanyalah ruas kiri (a) adalah sebuah simbol variabel. Sedangkan contoh aturan produksi yang termasuk CFG adalah seperti di bawah :
B CDeFg
D BcDe
Tata bahasa bebas konteks ( CFG ) adalah tata bahasa yang mempunyai tujuan sama seperti halnya tata bahasa regular yaitu merupakan suatu cara untuk menunjukkan bagaimana menghasilkan suatu untai-untai dalam sebuah bahasa.

2. #Ada 2 metoda parsing : 
>> Parsing top-down : Diberikan kalimat x sebagai input. Parsing dimulai dari simbol awal  S sampai kalimat x nyata (atau tidak nyata jika kalimat x memang  tidak bisa diturunkan dari S) dari pembacaan semua leaf dari pohon  parsing jika dibaca dari kiri ke kanan. 
>>Parsing bottom-up : Diberikan kalimat x sebagai input. Parsing dimulai dari kalimat x  yang nyata dari pembacaan semua leaf pohon parsing dari kiri ke  kanan sampai tiba di simbol awal S (atau tidak sampai di S jika kalimat x memang tidak bisa diturunkan dari S)

3.Metoda Brute-Force
         Kelas metoda dengan backup, termasuk metoda Brute-Force, adalah kelas metoda  parsing yang menggunakan produksi alternatif, jika ada, ketika hasil penggunaan sebuah  produksi tidak sesuai dengan simbol input. Penggunaan produksi sesuai dengan nomor urut  produksi . 
            Metoda Brute-Force tidak dapat menggunakan grammar rekursi kiri, yaitu grammar yang  mengandung produksi rekursi kiri (left recursion) : A
A. Produksi rekursi kiri akan  menyebabkan parsing mengalami looping tak hingga.

0 komentar on " LP TBO Pert 1 - 4 "

Posting Komentar