Bahasa Formal PDA yang Diterima Bahasa Bebas Konteks. Pertemuan Ke-13. Sri Handayaningsih, S.T., M.T. Teknik Informatika

Bahasa Formal PDA yang Diterima Bahasa Bebas Konteks

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

TIU & TIK Memahami konsep PDA yang diterima oleh CFG antara lain : 1. PDA untuk CFG 2. Deterministik PDA

2

Teorema: Bahasa bebas konteks (Gramer)

Bahasa yg diterima Oleh PDA

3

Pembuktian - langkah 1: Bahasa bebas konteks (Gramer)

Bahasa yg diterima Oleh PDA

Konversikan gramer bebas konteks G Pada PDA M dengan L(G ) L ( M )

4

Pembuktian - langkah 2: Bahasa bebas konteks (Gramer)

Bahasa yg diterima Oleh PDA

Konversikan PDA M ke grammer bebas konteks G dengan : L(G ) L ( M )

5

Pembuktian - langkah 1

Konversikan Grammer bebas konteks ke PDA

6

Bahasa bebas konteks (Gramer)

Bahasa yg diterima Oleh PDA

Konversikan grammer bebas konteksG Pada PDA M dengan L(G ) L ( M )

7

Konversi grammer Ke PDA

G

M sebagai berikut :

M Simulasi menggunakan derivasi kiri Pada

G

8

Konversi grammer G ke PDA M Produksi pada G

Terminal pada

A w

a

, A  w

q0

,  S

G

a, a  

q1

, $  $

q2

9

Grammer Derivasi kiri

Komputasi PDA

Simulasi grammer Derivasi kiri

(q0 , 1 kk 1 n ,$)

S   1 k X 1  X m

(q1 , 1 kk 1 n , S $)

  1 kk 1 n

 (q2 , ,$)

 (q1 , k 1 n , X 1  X m $)

Variabel kiri 10

Grammer

S S T T

Contoh

 aSTb PDA b , S  aSTb  Ta , S  b  a, a   , T  Ta b, b   , T  

q0

,  S

q1

, $  $

q2

11

Derivsi Grammer

S  aSTb  abTb  abTab  abab

Komputasi PDA ( q0 , abab,$) ( q1 , abab, S $) ( q1 , bab, STb$) ( q1 , bab, bTb$) ( q1 , ab, Tb$) ( q1 , ab, Tab$) ( q1 , ab, ab$) ( q1 , b, b$) ( q1 , ,$) ( q2 , ,$) 12

Derivasi: Input

Time 0

q0

a b a

b

, S  aSTb $ , S  b Stack a, a   , T  Ta b, b   , T   ,  S

q1

, $  $

q2

13

Derivasi: Input

Time 0

q0

S

a b a

b

S $

, S  aSTb , S  b Stack a, a   , T  Ta b, b   , T   ,  S

q1

, $  $

q2

14

Derivasi: Input

Time 1

q0

S  aSTb

a b a

a S T b $

b

, S  aSTb , S  b Stack a, a   , T  Ta b, b   , T   ,  S

q1

, $  $

q2

15

Derivasi: Input

Time 2

q0

S  aSTb

a b a

a S T b $

b

, S  aSTb , S  b Stack a, a   , T  Ta b, b   , T   ,  S

q1

, $  $

q2

16

Derivasi : Input

Time 3

q0

S  aSTb  abTb

a b a

b T b $

b

, S  aSTb , S  b Stack a, a   , T  Ta b, b   , T   ,  S

q1

, $  $

q2

17

Derivasi: Input

Time 4

q0

S  aSTb  abTb

a b a

b T b $

b

, S  aSTb , S  b Stack a, a   , T  Ta b, b   , T   ,  S

q1

, $  $

q2

18

Derivasi: Input

Time 5

q0

S  aSTb  abTb  abTab

a b a

T a b $

b

, S  aSTb , S  b Stack a, a   , T  Ta b, b   , T   ,  S

q1

, $  $

q2

19

Derivasi: Input

Time 6

q0

S  aSTb  abTb  abTab  abab

a b a

T a b $

b

, S  aSTb , S  b Stack a, a   , T  Ta b, b   , T   ,  S

q1

, $  $

q2

20

Derivasi: Input

Time 7

q0

S  aSTb  abTb  abTab  abab

a b a

b

a b $

, S  aSTb , S  b Stack a, a   , T  Ta b, b   , T   ,  S

q1

, $  $

q2

21

Derivasi: Input

Time 8

q0

S  aSTb  abTb  abTab  abab

a b a

b

b $

, S  aSTb , S  b Stack a, a   , T  Ta b, b   , T   ,  S

q1

, $  $

q2

22

Derivasi: Input

Time 9

S  aSTb  abTb  abTab  abab

a b a

b

, S  aSTb $ , S  b Stack a, a   , T  Ta b, b   , T   diterima

q0

,  S

q1

, $  $

q2

23

Secara Umum, dapat dilihat : Grammer dgn string w *

S w

G Jika dan Hanya jika

PDA M menerima

w

(q0 , w,$) (q2 , ,$)

sehingga L(G) L(M ) 24

Kesimpulan : Untuk setiap bahasa bebas konteks maka PDA dapat menerima L

Bahasa bebas konteks (Gramer)

L

Bahasa yg diterima Oleh PDA 25

Pembuktian - langkah 2

Konversi PDA ke Grammers Bebas konteks

26

Bahasa bebas konteks (Gramer)

Bahasa yg diterima Oleh PDA

Konversika PDA M ke grammer bebas konteks G dengan L(G ) L ( M )

27

Konversikan PDA

M ke

Grammer bebas konteks

G

G sbg berikut:

Komputasikan Simulasi dari M Dengan derivasi kiri

28

Beberapa Modifikasi Penting 1.

stack tdk pernah kosong selama komputasi

2. Jika hanya ada satu state yg diterima dan stack kosong ketika stack menerima string 3. Mempunyai transisi

 tanpa popping

29

1. stack tdk pernah kosong selama komputasi

Stack

a $

$

OK

OK

NOT OK 30

Penyelesain : Perkebalkan simbol baru Stack paling bawah

# utk menandai

a $

$

a $

$

#

#

# 31

Menambahkan

# pada awal PDA PDA asli

initial state baru

,$  $#

asli initial state 32

Konversikan seluruh transisi setelah popping $ pada automata yg tdk selesai

pop $

qi

,  s q j

x {# }

pop

$

qi

, x  x

,  s

qj

halting state 33

2. Modifikasi PDA pada akhir stack dgn stack kosong dan menerima state yg unik Stack kosong PDA

x {# }

, x   , #   q menerima states lama

f

Menerima State baru 34

3. Modifikasikan PDA yg tidak ada transisi popping  :

qi

qi

,  y

,  y

qj

qj

{# } 35

Contoh : (modifikasi yg tidak perlu)

L( M ) {w {a, b} : na ( w) nb ( w)} *

a, $  0$ a, 0  00 a, 1  

b, $  1$ b, 1  11 b, 0  

q0

, $  

qf 36

Kontruksi Grammer Pada grammer

G:

Variabel :

A

simbols stack PDA

Terminal :

a

simbols input PDA

Variabel Awal :

$ or # simbol bawah Stack 37

transisi PDA

produksi Grammer

q a, A   q1

Aa

38

transisi PDA

produksi Grammer

q a, A  B1 B2  Bm q1

A  aB1B2  Bm

39

Derivasi Grammer kiri

Komputasi PDA

S   1 k X 1  X m

(q1 , 1 kk 1 n ,$)  (q1 , k 1 n , X 1  X m )

  1 kk 1 n

 (q2 , , )

Variabel kiri 40

Contoh PDA:

a, $  0$ a, 0  00 a, 1  

b, $  1$ b, 1  11 b, 0  

q0 Grammer:

, $  

qf

$  a0$ $  b1$ 0  a 00 1  b11 $ 1 a 0b 41

Derivasi Kiri Grammer :

Komputasi PDA:

$  a 0$  ab$

(q0 , abba,$)

 abb1$  abba $  abba

( q0 , a,1$)

( q0 , bba,0$) ( q0 , ba,$) ( q0 , ,$) ( q f , , ) 42

Derivasi:

$

Time 0

a b b a a, $  0$ a, 0  00 a, 1  

b, $  1$ b, 1  11 b, 0  

q0

, $  

qf 43

Derivasi:

$



a 0$

Time 1

a b b a a, $  0$ a, 0  00 a, 1  

b, $  1$ b, 1  11 b, 0  

q0

, $  

0 $ Stack

qf 44

Derivasi:

$

 a0$  ab$ Time 2

a b b a a, $  0$ a, 0  00 a, 1  

b, $  1$ b, 1  11 b, 0  

q0

, $  

$ Stack

qf 45

Derivasi:

$

 a0$  ab$  abb1$ Time 3

a b b a a, $  0$ a, 0  00 a, 1  

b, $  1$ b, 1  11 b, 0  

q0

, $  

1 $ Stack

qf 46

Derivasi:

$

 a0$  ab$  abb1$

abba$

Time 4

a b b a a, $  0$ a, 0  00 a, 1  

b, $  1$ b, 1  11 b, 0  

q0

, $  

$ Stack

qf 47

Derivasi:

 a0$  ab$  abb1$ abba$  abba

$

Time 5

a b b a a, $  0$ a, 0  00 a, 1  

b, $  1$ b, 1  11 b, 0  

q0

, $  

kosong Stack

qf 48

Bagaimanapun juga, konversi grammer Tdk dpt bekerja pada seluruh PDAs:

a, $  A$ a, A  A$

b, A  

b, A   q0

q1

, $  

qf

L (M ) {a b : n 1} n n

49

a, $  A$ a, A  A$

b, A  

b, A   q0 Grammer:

$  aA$ $

q1

, $  

qf

A  aA$ Ab 50

Derivasi yg buruk:

S  aA$  aaA$  aab$  aab L (M )

Grammer:

$  aA$ $

A  aA$ Ab 51

Kontruksi Grammer Yg Benar Pada grammer

G:

Variabel:

simbol stack PDA

( qi Aq j ) PDA states

Terminals: simbol input pada PDA 52

Transisi PDA

q a, A   q1

produksi Grammer

( qAq1 )  a

53

Transisi PDA

q

a, A  B1 B2  Bm

q1

Produksi Grammer

( qAqm+1)  a (q1 B1q 2 )( q2 B2 q3 )  ( qm Bm q m1 ) Utk seluruh state yg mungkin q 2 , , qm1 pada PDA 54

Simbol stack bawah

$ or # Variabel awal : State awal

(qo Zq f ) State yg diterima

55

Contoh ::

a, $  0$ a, 0  00 a, 1  

b, $  1$ b, 1  11 b, 0  

q0

Produksi Grammar:

, $  

qf

(q01q0 )  a 56

Contoh :

a, $  0$ a, 0  00 a, 1  

b, $  1$ b, 1  11 b, 0  

q0

, $  

qf

Produksi Grammer :

(q0 $q0 )  b(q01q0 )(q0 $q0 ) | b(q01q f )(q f $q0 ) (q0 $q f )  b(q01q0 )(q0 $q f ) | b(q01q f )(q f $q f ) 57

Contoh:

a, $  0$ a, 0  00 a, 1  

b, $  1$ b, 1  11 b, 0  

q0 Produksi Grammer:

, $  

qf

(q0 $q f )   58

Kesimpulan Grammer: ( q0 $ q f ) : start variable

(q0 $q0 )  b(q01q0 )(q0 $q0 ) | b(q01q f )(q f $q0 ) (q0 $q f )  b(q01q0 )(q0 $q f ) | b(q01q f )(q f $q f ) (q01q0 )  b(q01q0 )(q01q0 ) | b(q01q f )(q f 1q0 ) (q01q f )  b(q01q0 )(q01q f ) | b(q01q f )(q f 1q f ) (q0 $q0 )  a(q0 0q0 )(q0 $q0 ) | a(q0 0q f )(q f $q0 ) (q0 $q f )  a(q0 0q0 )(q0 $q f ) | a (q0 0q f )(q f $q f ) 59

(q0 0q0 )  a(q0 0q0 )(q0 0q0 ) | a( q0 0q f )(q f 0q0 ) (q0 0q f )  a(q0 0q0 )(q0 0q f ) | a (q0 0q f )(q f 0q f ) (q01q0 )  a (q0 0q0 )  b (q0 $q f )  

60

Derivasi Grammar Kiri

Komputasi PDA

( q0 $q f )

(q0 , abba,$)

 a(q0 0q0 )(q0 $q f )

 ab(q0 $q f )  abb(q01q0 )(q0 $q f )

( q0 , bba,0$) ( q0 , ba,$) ( q0 , a,1$)

 abba (q0 $q f )

( q0 , ,$)

 abba

( q f , , ) 61

Derivasi:

( q0 $q f )

Time 0

a b b a a, $  0$ a, 0  00 a, 1  

b, $  1$ b, 1  11 b, 0  

q0

, $  

qf 62

Derivasi:

( q0 $q f )  a ( q0 0q0 )( q0 $q f )

Time 1

a b b a a, $  0$ a, 0  00 a, 1  

b, $  1$ b, 1  11 b, 0  

q0

, $  

0 $ Stack

qf 63

Derivasi:

( q0 $q f )  a ( q0 0q0 )( q0 $q f )  ab( q0 $q f )

Time 2

a b b a a, $  0$ a, 0  00 a, 1  

b, $  1$ b, 1  11 b, 0  

q0

, $  

$ Stack

qf 64

Derivasi:

( q0 $q f )  a ( q0 0q0 )( q0 $q f )  ab( q0 $q f )

 abb(q01q0 )(q0 $q f )

Time 3

a b b a a, $  0$ a, 0  00 a, 1  

b, $  1$ b, 1  11 b, 0  

q0

, $  

1 $ Stack

qf 65

Derivasi:

( q0 $q f )  a ( q0 0q0 )( q0 $q f )  ab( q0 $q f )

 abb(q01q0 )(q0 $q f )  abba (q0 $q f ) Time 4

a b b a a, $  0$ a, 0  00 a, 1  

b, $  1$ b, 1  11 b, 0  

q0

, $  

$ Stack

qf 66

Derivasi:

( q0 $q f )  a ( q0 0q0 )( q0 $q f )  ab( q0 $q f )

 abb(q01q0 )(q0 $q f )  abba (q0 $q f )  abba Time 5

a b b a a, $  0$ a, 0  00 a, 1  

b, $  1$ b, 1  11 b, 0  

q0

, $  

kosong Stack

qf 67

Secara Umum:

Grammer 

(qi Aq j )  wB

Jika dan PDA  Hanya ( q , w , A )  ( q ,  , B ) i j jika

68

Thus:

Grammer dg general w 

( q0 $ q f )  w

Jika dan PDA menerima w  Hanya ( q , w ,$)  ( q ,  ,  ) 0 f jika

69

sehingga: Untuk setiap PDA Merupakan grammer bebas kontek Akan menerima bahasa yg sama

Bahasa Bebas konteks (Grammer)

bahasa diterima Oleh PDA 70

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