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