pertemuan 11 - penyederhanaan cfg [compatibi · 1. tedy setiadi, diktat teori bahasa dan otomata,...

Penyederhanaan CFG

Sri Handayaningsih, S.T., M.T.Email : ning_s12@yahoo.com

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