Bahasa Formal Bahasa Bebas Context

Bahasa Formal Bahasa Bebas Context

Pertemuan Ke - 10 Sri Handayaningsih, S.T., M.T. Email : [email protected] Teknik Informatika

TIU dan TIK 1. Memahami tata bahasa bebas konteks, parsing serta penyederhanaan tata bahasa bebas konteks 2. Mampu mengerjakan soal parsing dan penyederhanaan tata bahasa bebas konteks

TEORI BAHASA OTOMATA 2

n n

{a b : n 0}

R

{ww } {ww

Bahasa Regular

a *b *

( a b) *

TEORI BAHASA OTOMATA 3

Bahasa Bebas Context n n

{a b }

R

{ww } {ww

Bahasa Regular

TEORI BAHASA OTOMATA 4

Bahasas Bebas Konteks

Gramer bebas konteks

Pushdown Automata stack automaton

TEORI BAHASA OTOMATA 5

Gramer Bebas Konteks

TEORI BAHASA OTOMATA 6

Gramer

Bahasa pengekspresian Gramer Contoh:

bahasa Inggris

sentence  noun _ phrase noun _ phrase  article

predicate noun

predicate  verb

TEORI BAHASA OTOMATA

7

article  a article  the noun  cat noun  dog verb  runs verb  walks TEORI BAHASA OTOMATA 8

Derivasi dari “the dog walks”: sentence  noun _ phrase

predicate

 noun _ phrase

verb

 article

verb

 the noun

noun verb

 the dog verb  the dog walks TEORI BAHASA OTOMATA 9

Derivasi dari “a cat runs”: sentence  noun _ phrase

predicate

 noun _ phrase

verb

 article

noun

verb

 a noun

verb

 a cat verb  a cat runs TEORI BAHASA OTOMATA 10

Bahasa dari gramer: L = { “a cat runs”, “a cat walks”, “the cat runs”, “the cat walks”, “a dog runs”, “a dog walks”, “the dog runs”, “the dog walks” } TEORI BAHASA OTOMATA 11

Notasi Aturan Produksi noun  cat noun  dog

Variaber

Terminal

TEORI BAHASA OTOMATA 12

Contoh

S  aSb Gramer: S 

ab Derivasi dari kalimat :

:

S  aSb  ab

S  aSb

S 

TEORI BAHASA OTOMATA 13

Apakah Gramer Berikut merupakan Bahasa Gramer:

S  aSb S 

Derivasi dari kalimat :

aabb S  aSb  aaSbb  aabb S  aSb

S 

TEORI BAHASA OTOMATA 14

Derivasi Lain :

S  aSb  aaSbb  aaaSbbb  aaabbb

S  aSb  aaSbb  aaaSbbb  aaaaSbbbb  aaaabbbb TEORI BAHASA OTOMATA 15

Bahasa pada gramer

S  aSb S 

L {a b : n 0} n n

TEORI BAHASA OTOMATA 16

Notasi Lain G  V ,T , S , P Gramer

V:

Himpunan variabel

T:

Himpunan simbol terminal

S : Variabel awal

P:

Himpunan aturan Produksi

TEORI BAHASA OTOMATA 17

Contoh Gramer

G

:

S  aSb S 

G  V ,T , S , P V {S}

T {a, b}

P {S  aSb, S  } TEORI BAHASA OTOMATA 18

Notasi Lain Form Sentensial: sebuah kalimat tersiri dari variabel dan terminal Example:

S  aSb  aaSbb  aaaSbbb  aaabbb Form Sentensial

Kalimat

TEORI BAHASA OTOMATA 19

*

Penulisan:

S  aaabbb

Instead of:

S  aSb  aaSbb  aaaSbbb  aaabbb TEORI BAHASA OTOMATA 20

*

Secara umum dapat ditulis :

Jika :

w1  wn

w1  w2  w3    wn

TEORI BAHASA OTOMATA 21

*

Dengan akhir :

w  w

TEORI BAHASA OTOMATA 22

Gramer

S  aSb S 

Contoh Derivasi *

S  *

S  ab *

S  aabb *

S  aaabbb TEORI BAHASA OTOMATA 23

Contoh Gramer

S  aSb S 



Derivasi

S  aaSbb 

aaSbb  aaaaaSbbbbb

TEORI BAHASA OTOMATA 24

Contoh 1 Gramer :

G

S  Ab A  aAb A

TEORI BAHASA OTOMATA 25

Derivasi S  Ab  aAbb  aaAbbb  aaaAbbbb

 aaaaAbbbbb  aaaabbbbb 

S  aaaabbbbb 

S  aaaaaabbbbbbb 

S a b b n n

TEORI BAHASA OTOMATA 26

Bahasa pada Gramer Untuk sebuah gramer G Dimulai dengan variabel:

S 

L(G ) {w : S  w} String pada terminal TEORI BAHASA OTOMATA 27

Contoh Untuk gramer G :

S  Ab A  aAb A

L(G ) {a b b : n 0} n n

Selama :



S a b b n n

TEORI BAHASA OTOMATA 28

Notasi yang tepat A  aAb A

article  a article  the

A  aAb | 

article  a | the

TEORI BAHASA OTOMATA 29

Contoh Gramer Bebas contek :

G

S  aSb S 

derivasi:

S  aSb  aaSbb  aabb TEORI BAHASA OTOMATA 30

Gramer Bebas Konteks:

G

S  aSb S 

Derivasi lain :

S  aSb  aaSbb  aaaSbbb  aaabbb TEORI BAHASA OTOMATA 31

S  aSb S 

L(G ) {a b : n 0} n n

Describes parentheses:

(((( ))))

TEORI BAHASA OTOMATA 32

Contoh Gramer Bebas Konteks :

G

S  aSa S  bSb S 

Derivasi :

S  aSa  abSba  abba TEORI BAHASA OTOMATA 33

Gramer Bahasa Konteks :

G

S  aSa S  bSb S 

Derivasi Lain :

S  aSa  abSba  abaSaba  abaaba TEORI BAHASA OTOMATA 34

S  aSa S  bSb S 

L(G ) {ww : w {a, b}*} R

TEORI BAHASA OTOMATA 35

Contoh Gramer Bahasa Konteks :

G

S  aSb S  SS S 

Derivasi :

S  SS  aSbS  abS  ab TEORI BAHASA OTOMATA 36

Gramer Bebas Konteks :

G

S  aSb S  SS S 

Derivasi :

S  SS  aSbS  abS  abaSb  abab TEORI BAHASA OTOMATA 37

S  aSb S  SS S  L(G )  {w : na ( w) nb ( w), dan na (v) nb (v ) pada prefix lain v}

TEORI BAHASA OTOMATA 38

S  aSb S  SS S  L(G )  {w : na ( w) nb ( w), dan na (v) nb (v ) pada prefix lain v} Diskripsi sesuai Dengan tanda () Kurung : TEORI BAHASA OTOMATA

((( ))) (( )) 39

Definisi: Grammer Bebas Kontek

G (V ,T , S , P)

Grammar Variable

Simbol Terminal

variabel awal

Produksi dari form : Variable

A  x String dari variabel dan terminal

TEORI BAHASA OTOMATA 40

G (V ,T , S , P)

*

L (G ) {w : S  w, w T *}

TEORI BAHASA OTOMATA 41

Definisi bahasa Bebas Konteks Sebuah Bahasa

L adalah bebas konteks

Jika dan hanya jika

G

Gramer bebas konteks dengan

L L (G )

TEORI BAHASA OTOMATA 42

1. S  AB

Derivasi Order 2. A  aaA

4. B  Bb

3. A  

5. B  

Derivasi dari kiri : 1

2

3

4

5

S  AB  aaAB  aaB  aaBb  aab Derivasi dari kanan: 1

4

5

2

3

S  AB  ABb  Ab  aaAb  aab TEORI BAHASA OTOMATA 43

S  aAB Derivasi Order A  bBb B  A| Derivasi dari kiri :

S  aAB  abBbB  abAbB  abbBbbB  abbbbB  abbbb Derivasi dari kanan :

S  aAB  aA  abBb  abAb  abbBbb  abbbb

TEORI BAHASA OTOMATA

44

Pohon Derivasi

TEORI BAHASA OTOMATA 45

A  aaA | 

S  AB

B  Bb | 

S  AB S

A

B

TEORI BAHASA OTOMATA 46

A  aaA | 

S  AB

B  Bb | 

S  AB  aaAB S

A

a

a

B A

TEORI BAHASA OTOMATA 47

A  aaA | 

S  AB

B  Bb | 

S  AB  aaAB  aaABb S

A

a

a

B A

B

b

TEORI BAHASA OTOMATA 48

A  aaA | 

S  AB

B  Bb | 

S  AB  aaAB  aaABb  aaBb S

A

a

a

TEORI BAHASA OTOMATA

B A

B

b

 49

A  aaA | 

S  AB

B  Bb | 

S  AB  aaAB  aaABb  aaBb  aab Pohon Derivasi

S

A

a

a

TEORI BAHASA OTOMATA

B A

B





b

50

A  aaA | 

S  AB

B  Bb | 

S  AB  aaAB  aaABb  aaBb  aab Pohon Derivasi

S

A

a

a

TEORI BAHASA OTOMATA

B A

B





yield

b

aab aab 51

Parsial Pohon Derivasi

S  AB

A  aaA | 

B  Bb | 

S  AB Parsial pohon derivasi

A

S

B

TEORI BAHASA OTOMATA 52

S  AB  aaAB Parsial pohon derivasi

S

A

a

a

B A

TEORI BAHASA OTOMATA 53

S  AB  aaAB Parsial pohon derivasi

S

A

a

a

form sentensial

B A

yield

aaAB

TEORI BAHASA OTOMATA 54

Tidak masalah derivasi yang akan di pakai Kiri :

S  AB  aaAB  aaB  aaBb  aab kanan:

S  AB  ABb  Ab  aaAb  aab S

Pohon derivasi A a TEORI BAHASA OTOMATA

a

B A

B





b

55

Ambiguiti

TEORI BAHASA OTOMATA 56

E  E E | E E | ( E ) | a a a a E 

E

a

E

a

E  E E  a E  a E E  a a E  a a * a E 

TEORI BAHASA OTOMATA

Derivasi kiri

E

a 57

E  E E | E E | ( E ) | a a a a E  E E  E E E  a E E E  a a E  a a a Derivasi kiri

E TEORI BAHASA OTOMATA

a

E



E



E

a

a 58

E  E E | E E | ( E ) | a a a a Dua pohon derivasi

E E

a



E

a

E E 

TEORI BAHASA OTOMATA

E

E

a

a

E



E



E

a

a 59

E  E E | E E | ( E ) | a Adalah ambigius:

Gramer

string

a a a

Mempunyai dua pohon derivasi E

E E

a



E

E 

a

E

E

a

a

E



E



E

a

a

TEORI BAHASA OTOMATA 60

E  E E | E E | ( E ) | a Adalah ambigius:

Gramer

string

a a a

Mempunyai dua pohon derivasi

E  E E  a E  a E E  a a E  a a * a E  E E  E E E  a E E  a a E  a a a

TEORI BAHASA OTOMATA

61

Definisi: Gramer bebas konteks

G adalah ambigius

Jika beberapa string w L (G )mempunyai : dua atau lebih pohon derivasi

TEORI BAHASA OTOMATA 62

Dengan kalimat yg lain: Gramer bebas kontek

G adalah ambigius

Jika beberapa string w L(G ) mempunyai: dua atau lebih derivasi kiri (atau kanan)

TEORI BAHASA OTOMATA 63

Bagaimana mengetahui ttg ambiguiti?

a a a Berikan

E E

a



E

a

a 2

E 

TEORI BAHASA OTOMATA

E

E

a

a

E E



E



E

a

a 64

2 2 2 E E 2



E 2

E E 

TEORI BAHASA OTOMATA

E

E

2

2

E



E



E

2

2 65

2 2 2 6

2 2 2 8 8 E

6 E

2 E 2



2 E 2

4 E 

TEORI BAHASA OTOMATA

2 E

2 E

2

2

4 E



2 E



2 E

2

2 66

Hasi yg benar:

2 2 2 6 6 E

2 E 2 TEORI BAHASA OTOMATA



2 E 2

4 E 

2 E 2 67

Ambiguiti tidak baik untuk bahasa pemrograman

TEORI BAHASA OTOMATA 68

Membetukan ambigius gramer:

E  E E | E E | ( E ) | a Gramer non-ambiguous baru :

TEORI BAHASA OTOMATA

E  E T E T T  T F T F F  (E ) F a

69

E  E T  T T  F T  a T  a T F  a F F  a a F  a a a

a a a

E

E  E T E T T  T F T F F  (E ) F a

E



T

T

T

F

F

a

a



F a

TEORI BAHASA OTOMATA 70

Pohon derivasi yg unik

a a a

E E



T

T

T

F

F

a

a



F

a

TEORI BAHASA OTOMATA 71

Gramer :

G

E  E T E T T  T F T F F  (E ) F a

non-ambiguous : Untuk setiap string Pohon derivasi yg unik

mempunyai w L(G )

TEORI BAHASA OTOMATA

72

Pustaka 1. 2. 3. 4. 5. 6.

Tedy Setiadi, Diktat Teori Bahasa dan Otomata, Teknik Informatika UAD, 2005 Hopcroft John E., Rajeev Motwani, Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 2rd, Addison-Wesley,2000 Martin C. John, Introduction to Languages and Theory of Computation, McGraw-Hill Internatioanal edition,1991 Linz Peter,Introduction to Formal Languages & Automata, DC Heath and Company, 1990 Dulimarta Hans, Sudiana, Catatan Kuliah Matematika Informatika, Magister Teknik Informatika ITB, 1998 Hinrich Schütze, IMS, Uni Stuttgart, WS 2006/07, Slides based on RPI CSCI 2400

TEORI BAHASA OTOMATA 73