pda yang diterima bahasa bebas konteks

Bahasa FormalPDA yang Diterima Bahasa Bebas Konteks

Pertemuan Ke-13

Sri Handayaningsih, S.T., M.T.

Email : ning_s12@yahoo.com

Teknik Informatika

TIU & TIK

Memahami konsep PDA yang diterima olehCFG antara lain :

1. PDA untuk CFG2. Deterministik PDA

2

Bahasabebas konteks

(Gramer)

Bahasa ygditerimaOleh PDA

Teorema:

3

Bahasabebas konteks

(Gramer)

Bahasa ygditerimaOleh PDA

Pembuktian - langkah 1:

4

Konversikan gramer bebas konteksPada PDA dengan

GM )()( MLGL

Bahasabebas konteks

(Gramer)

Bahasa ygditerimaOleh PDA

Pembuktian - langkah 2:

5

Konversikan PDA ke grammer bebaskonteks dengan :G

M)()( MLGL

Konversikan

Grammer bebas kontekske

Pembuktian - langkah 1

6

kePDA

Bahasabebas konteks

(Gramer)

Bahasa ygditerimaOleh PDA

7

Konversikan grammer bebas konteksPada PDA dengan

GM )()( MLGL

Ke PDA sebagai berikut :M

Konversi grammer G

8

M Simulasi menggunakan derivasi kiriPada G

Produksi pada

wATerminal pada

aG G

Konversi grammer ke PDAG M

9

q0 q1 2qS, , $ $

wA, aa,

S

GrammerDerivasi kiri

$),,(

,$),(

111

110

Sq

q

nkk

nkk

Komputasi PDASimulasi grammerDerivasi kiri

10

nkk

mk XX

11

11

,$),(

$),,(

2

111

q

XXq mnk

Variabel kiri

Grammer

PDA

bSaSTbS

,,

TTaTbSaSTbS

Contoh

11

q0 q1 2qS, , $ $

TTaTbS

,,,T

bbaa

,,

abTbaSTb

S

$),,($),,($),,(

$),,(,$),(

1

1

1

0

TbabqbTbbabqSTbbabq

Sababqababq

Derivsi Grammer Komputasi PDA

12

abababTab

,$),(,$),(

$),,(

$),,($),,(

$),,(

2

1

1

1

1

1

qq

bbq

ababqTababqTbabq

bSaSTbS

,,

Input

Stack

$

a ab

Time 0

b

Derivasi:

130q q1 2qS, , $ $

TTaTbS

,,,

bbaa

,,

Stack

bSaSTbS

,,

Input

Stack

$

a ab bS

Time 0

Derivasi: S

14

q0 q1 2qS, , $ $

TTaTbS

,,,

bbaa

,,

Stack

bSaSTbS

,,

Input

Stack

$

a ab b

a

b

ST

Time 1

Derivasi: aSTbS

15

q0 2qS, , $ $

TTaTbS

,,,

bbaa

,,

Stack

q1

bSaSTbS

,,

Input

Stack

$

a ab b

a

b

ST

Time 2

aSTbS Derivasi:

16

q0 2qS, , $ $

TTaTbS

,,,

bbaa

,,

Stack

q1

bSaSTbS

,,

Input

Stack

$

a ab b

bTb

Time 3

Derivasi : abTbaSTbS

17

q0 2qS, , $ $

TTaTbS

,,,

bbaa

,,

Stack

q1

bSaSTbS

,,

Input

Stack

$

a ab b

bTb

Time 4

Derivasi: abTbaSTbS

18

q0 2qS, , $ $

TTaTbS

,,,

bbaa

,,

Stack

q1

bSaSTbS

,,

Input

Stack

$

a ab b

b

Ta

Time 5

Derivasi: abTababTbaSTbS

19

q0 2qS, , $ $

TTaTbS

,,,

bbaa

,,

Stack

q1

bSaSTbS

,,

Input

Stack

$

a ab b

b

Ta

Time 6

Derivasi: abababTababTbaSTbS

20

q0 2qS, , $ $

TTaTbS

,,,

bbaa

,,

Stack

q1

bSaSTbS

,,

Input

Stack

$

a ab b

ba

Time 7

Derivasi: abababTababTbaSTbS

21

q0 2qS, , $ $

TTaTbS

,,,

bbaa

,,

Stack

q1

bSaSTbS

,,

Input

Stack

$

a ab b

b

Time 8

Derivasi: abababTababTbaSTbS

22

q0 2qS, , $ $

TTaTbS

,,,

bbaa

,,

Stack

q1

bSaSTbS

,,

Input

Stack

$

a ab b

Time 9

Derivasi: abababTababTbaSTbS

23

q0 q1 2qS, , $ $

TTaTbS

,,,

bbaa

,,

Stack

diterima

Grammerdgnstring

GPDAmenerima

M

Secara Umum, dapat dilihat :

w wJika danHanya jika

24

wS*

,$),(,$),( 20 qwq

Hanya jika

sehingga )()( MLGL

Kesimpulan :

Untuk setiap bahasa bebas konteksmaka PDA dapat menerima

LL

25

Bahasabebas konteks

(Gramer)

Bahasa ygditerimaOleh PDA

Konversi

PDAke

Pembuktian - langkah 2

26

keGrammers Bebas konteks

Bahasabebas konteks

(Gramer)

Bahasa ygditerimaOleh PDA

27

Konversika PDA ke grammer bebaskonteks denganG

M)()( MLGL

Konversikan PDA keM

Grammer bebas konteks sbg berikut:G

Komputasikan Simulasi dari

28

MKomputasikan Simulasi dariDengan derivasi kiri

G

Beberapa Modifikasi Penting

1. stack tdk pernah kosong selama komputasi

2. Jika hanya ada satu state yg diterimadan stack kosong ketika stack menerima string

29

3. Mempunyai transisi tanpa popping

1. stack tdk pernah kosong selama komputasi

Stack

30

$a

OK

$

OK NOT OK

$a

$

Penyelesain :Perkebalkan simbol baru utk menandaiStack paling bawah

#

31

$a

#$# #

PDA asli

Menambahkan pada awal PDA#

initial statebaru

32

$#,$

asliinitial state

baru

iq jqs,

Konversikan seluruh transisisetelah popping pada automata ygtdk selesai

$

}{#x

pop $

33

iq jqs,

halting state

xx ,}{#x

pop $

PDA x,

Stack kosong}{#x

2. Modifikasi PDA pada akhir stack dgnstack kosong danmenerima state yg unik

34

fq

x,

menerima states lama

#,

MenerimaStatebaru

3. Modifikasikan PDA yg tidak adatransisi popping :

iq jqy,

35

iq jq y,

}{#

a, $ 0$ b, $1$

)}()(:},{{)( * wnwnbawML ba

Contoh :(modifikasi yg tidak perlu)

36

$,0q fq

a, 0 00a,1

b, 111b, 0

Kontruksi Grammer

A

Pada grammer :G

Terminal :

simbols stack PDAVariabel :

a simbols input PDA

37

Terminal : a simbols input PDA

Variabel Awal : simbol bawah Stack#or$

q 1qAa,transisi PDA

38

produksi Grammer aA

transisi PDA q 1qmBBBAa 21,

39

produksi Grammer mBBaBA 21

S

DerivasiGrammerkiri

,$),( 111 q nkk

Komputasi PDA

40

nkk

mk XX

11

11

),,(

),,(

2

111

q

XXq mnk

Variabel kiri

Contoh PDA:

$,0q fq

a, $ 0$a, 0 00a,1

b, $1$b, 111b, 0

41

0q fq

Grammer: $0$ a000 a

a1

$1$ b111 b

b0 $

a $0$

DerivasiKiriGrammer :

KomputasiPDA:

$)0,,(,$),(

0

0

bbaqabbaq

42

abbaabbaabb

ab

$$1

$

),,(

,$),(

$)1,,(

,$),(

0

0

0

fq

q

aq

baq

a, $ 0$ b, $1$

$Derivasi:

a ab b Time 0

43

$,0q fq

a, $ 0$a, 0 00a,1

b, $1$b, 111b, 0

a, $ 0$ b, $1$

$Derivasi:

a ab b Time 1

0

$0a

44

$,0q fq

a, $ 0$a, 0 00a,1

b, $1$b, 111b, 0 Stack

$

a, $ 0$ b, $1$

$Derivasi:

a ab b Time 2

$0a $ab

45

$,0q fq

a, $ 0$a, 0 00a,1

b, $1$b, 111b, 0 Stack

$

a, $ 0$ b, $1$

$Derivasi:

a ab b Time 3

$0a $ab

1

$1abb

46

$,0q fq

a, $ 0$a, 0 00a,1

b, $1$b, 111b, 0 Stack

$

a, $ 0$ b, $1$

Derivasi:

a ab b Time 4

$ $0a $ab $1abb$abba

47

$,0q fq

a, $ 0$a, 0 00a,1

b, $1$b, 111b, 0 Stack

$

a, $ 0$ b, $1$

Derivasi:

a ab b Time 5

kosong

abba

$ $0a $ab $1abb$abba

48

$,0q fq

a, $ 0$a, 0 00a,1

b, $1$b, 111b, 0 Stack

kosong

Bagaimanapun juga, konversi grammerTdk dpt bekerja pada seluruh PDAs:

Ab,$$, Aa $, AAa

49

0q fqAb,1q $,

}1:{)( nbaML nn

Ab,

0q fq

$$, Aa $, AAa

Ab,1q $,

50

Grammer: $$ aA $aAAbA$

Derivasi yg buruk:

)($$$ MLaabaabaaAaAS

51

Grammer: $$ aA $aAAbA$

Kontruksi Grammer Yg Benar

)( ji Aqq

Pada grammer :Gsimbol stack PDA

Variabel:

52

Terminals: simbol input pada PDA

PDA states

q 1qAa,Transisi PDA

53

produksi Grammer aqAq )( 1

Transisi PDA

q 1qmBBBAa 21,

54

Produksi Grammer

)())(()( 1322211 mmmm qBqqBqqBqaqAq

Utk seluruh state yg mungkinpada PDA

12 ,, mqq

+1

Variabel awal : )( foZqq

Simbol stack bawah#or$

55

State awal State yg diterima

Contoh ::

a, $ 0$a, 0 00a,1

b, $1$b, 111b, 0

56

$,0q fq

aqq )1( 00Produksi Grammar:

Contoh :

a, $ 0$a, 0 00a,1

b, $1$b, 111b, 0

57

$,0q fq

)$)(1(|)$)(1()$(

)$)(1(|)$)(1()$(

00000

00000000

fffff

ff

qqqqbqqqqbqq

qqqqbqqqqbqq

Produksi Grammer :

Contoh:

a, $ 0$a, 0 00a,1

b, $1$b, 111b, 0

58

$,0q fq

Produksi Grammer: )$( 0 fqq

)$)(1(|)$)(1()$(

)$)(1(|)$)(1()$(

00000

00000000

fffff

ff

qqqqbqqqqbqq

qqqqbqqqqbqq

)1)(1(|)1)(1()1( 00000000 ff qqqqbqqqqbqq

Kesimpulan Grammer: ablestart vari:)$( 0 fqq

59

)1)(1(|)1)(1()1(

)1)(1(|)1)(1()1(

00000

00000000

fffff

ff

qqqqbqqqqbqq

qqqqbqqqqbqq

)$)(0(|)$)(0()$(

)$)(0(|)$)(0()$(

00000

00000000

fffff

ff

qqqqaqqqqaqq

qqqqaqqqqaqq

)0)(0(|)0)(0()0(

)0)(0(|)0)(0()0(

00000

00000000

fffff

ff

qqqqaqqqqaqq

qqqqaqqqqaqq

bqq

aqq

)0(

)1(

00

00

60

bqq )0( 00

)$( 0 fqq

)$( 0 fqq)$)(0( 000 fqqqqa

)$( qqab ,$),($)0,,(

,$),(

0

0

baqbbaq

abbaq

DerivasiGrammarKiri

KomputasiPDA

61

)$( 0 fqqab)$)(1( 000 fqqqqabb

)$( 0 fqqabba

abba ),,(

,$),(

$)1,,(

,$),(

0

0

0

fq

q

aq

baq

a, $ 0$ b, $1$

)$( 0 fqqDerivasi:

a ab b Time 0

62

$,0q fq

a, $ 0$a, 0 00a,1

b, $1$b, 111b, 0

a, $ 0$ b, $1$

)$( 0 fqqDerivasi:

a ab b Time 1

0

)$)(0( 000 fqqqqa

63

$,0q fq

a, $ 0$a, 0 00a,1

b, $1$b, 111b, 0 Stack

$

a, $ 0$ b, $1$

)$( 0 fqqDerivasi:

a ab b Time 2

)$)(0( 000 fqqqqa )$( 0 fqqab

64

$,0q fq

a, $ 0$a, 0 00a,1

b, $1$b, 111b, 0 Stack

$

a, $ 0$ b, $1$

)$( 0 fqqDerivasi:

a ab b Time 3

)$)(0( 000 fqqqqa )$( 0 fqqab

1

)$)(1( 000 fqqqqabb

65

$,0q fq

a, $ 0$a, 0 00a,1

b, $1$b, 111b, 0 Stack

$

a, $ 0$ b, $1$

)$( 0 fqqDerivasi:

a ab b Time 4

)$)(0( 000 fqqqqa )$( 0 fqqab)$)(1( 000 fqqqqabb )$( 0 fqqabba

66

$,0q fq

a, $ 0$a, 0 00a,1

b, $1$b, 111b, 0 Stack

$

a, $ 0$ b, $1$

)$( 0 fqqDerivasi:

a ab b Time 5

)$)(0( 000 fqqqqa )$( 0 fqqab)$)(1( 000 fqqqqabb )$( 0 fqqabba abba

kosong

67

$,0q fq

a, $ 0$a, 0 00a,1

b, $1$b, 111b, 0 Stack

kosong

Secara Umum:

wBAqq

)(

Jika danHanya

Grammer PDA

),,(),,( BqAwq

68

wBAqq ji )(Hanyajika ),,(),,( BqAwq ji

Thus:

Jika danHanya

Grammer dggeneral PDA menerima

),,(,$),( qwq

w w

69

wqq f

)$( 0

Hanyajika ),,(,$),( 0 fqwq

sehingga:

Untuk setiap PDAMerupakan grammer bebas kontekAkan menerima bahasa yg sama

70

BahasaBebas konteks

(Grammer)

bahasaditerimaOleh PDA

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 Theoryof Computation, McGraw-Hill Internatioanal edition,1991

4. Linz Peter,Introduction to Formal Languages &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