pertemuan 11 - penyederhanaan cfg [compatibi · 1. tedy setiadi, diktat teori bahasa dan otomata,...
TRANSCRIPT
Penyederhanaan CFG
Sri Handayaningsih, S.T., M.T.Email : [email protected]
Teknik Informatika
Pertemuan Ke - 11
TIU & TIK
1. Mengetahui proses penyederhanaanCFG
2
Aturan Substitusi
aaAAaBS
Substitusi
Gramer ygEquivalent
abaBS |
3
bBaABabBcAaaAA
Substitusi
aABabbcabBcA
aaAA
|bB
Aturan Substitusi
aABabbcabBcA
aaAAabaBS
|
|
4
GramerEquivalent
abaAcabbcabBcAaaAA
aaAabaBS
||
||
Substitusi
aAB
Secara Umum :
1yB
xBzA
Substitute
5
zxyxBzA 1|
1yB
GramerEquivalent
Variabel Kosong/Null
:produksi A
6
Variabel Kosong /null: A
Memindahkan Variabel Kosong
Contoh Gramer:
aMbMaMbS
7
MaMbM
Variabel Kosong
aMbS
Substitusi abSaMbS
Gramer Akhir
8
M
MaMbM Substitusi
abMaMbM
abS
Unit-Produksi
BAUnit Produksi:
9
(variabel tunggal pada dua sisi)
Memindahkan Unit Produksi
Observasi:
AA
10
Apakah berpindah immediately
Contoh Gramer:
aAaAS
11
bbBABBA
aAaAS
Substitusi aAaBaAS
|
12
bbBABBA
Substitusi
BA
bbBBAB
aA
|
BerpindahaAaBaAS
|
aAaBaAS
|
13
Berpindah
bbBBAB
aA
|bbBABaA
BB
aAaBaAS ||aAaBaAS
|
14
SubstitusiAB
bbBaA
bbBABaA
Pengulangan pemindahan produksi
aBaAS |aAaBaAS ||
Gramer akhir
15
bbBaA
aBaAS
|
bbBaA
Produksi yang tidak berguna
ASS
aSbS
16
aAA
aAaaaaAaAAS
Beberapa derivasi tidak akan berakhir...
ProduksiTdk berguna
AaAAAS
Gramer lain :
Produksi
17
bAB
Tidak dapat tercapai dari S
ProduksiTdk berguna
Secara Umum:
Jika wxAyS
)(GLw
Hanyaterminal
18
kemudian variabel digunakanA
kecuali, variabel tidak dugunakanA
produksi tidak digunakanJika variabel tidak digunakanxA
ASS
aSbS
Produksi
Tidak digunakan
19
DCCBaAAAS
Tidak digunakan
Tidak digunakan
Tidak digunakan
Tidak digunakan
Variabel
Tidak digunakan
Tidak digunakan
Tidak digunakan
20
Memindahkan produksi yg tdkdigunakan
Pertama: Temukan Semua variabel yg dapatMemproduksi string yg hanya terminal
CAaSS || },{ BAputaran 1:
21
aCbCaaBaA
CAaSS
||
AS
},,{ SBAputaran 2:
Simpan hanya variabelYg memproduksi simbol terminal:
CAaSS ||
},,{ SBA
(variabel lain tdk digunakan)
22
aCbCaaBaA
CAaSS
||
aaBaA
AaSS
|
Pindahkan produksi yg tdk digunakan
Kedua : Temukan semua variabelYg tdk tercapai dari
Gunakan graf Dependensi
S
23
aaBaA
AaSS
|
S A B
tdktercapai
Temukan semua variabelYg tdk tercapai dari S
AaSS |AaSS |
Gramer Akhir
(variabel lain tdk digunakan)
24
aaBaA
aAAaSS
|
Pindahkan produksi yg tdk digunakan
Pindahkan semua
Langkah 1: pindahkan variabel kosong
25
Langkah 2: pindahkan Unit-Produksi
Langkah 3: pindahkan variabel yg tdkberguna
Tugas1. Pindahkan Produksi yg tdk digunakan
aACAaSS
||
26
aCbCaaBaA
Pustaka1. Tedy Setiadi, Diktat Teori Bahasa dan Otomata,
Teknik Informatika UAD, 20052. Hopcroft John E., Rajeev Motwani, Jeffrey D. Ullman,
Introduction to Automata Theory, Languages, andComputation, 2rd, Addison-Wesley,2000
3. Martin C. John, Introduction to Languages and Theory ofComputation, McGraw-Hill Internatioanal edition,1991
TEORI BAHASA OTOMATA27
3. Martin C. John, Introduction to Languages and Theory ofComputation, McGraw-Hill Internatioanal edition,1991
4. Linz Peter,Introduction to Formal Languages & Automata,DC Heath and Company, 1990
5. Dulimarta Hans, Sudiana, Catatan Kuliah MatematikaInformatika, Magister Teknik Informatika ITB, 1998
6. Hinrich Schütze, IMS, Uni Stuttgart, WS 2006/07,Slides based on RPI CSCI 2400