Ekspresi Reguler. Pertemuan Ke-8. Sri Handayaningsih, S.T., M.T. Teknik Informatika

Ekspresi Reguler

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

TIU dan TIK 1. memahami konsep ekspresi reguler dan ekivalensinya dengan bahasa reguler. 2. Mengetahun Penerapan Ekspresi Reguler 3. Mengetahui Definisi Formal ER 4. Mengetahui Bahasa untuk ER 5. Mengetahui proses Konversi ER ke FA TEORI BAHASA OTOMATA 2

Ekspresi Regular ekspresi Regular adalah menggambarkan bahasa regular

Contoh:

( a b  c) * Menggambarkan bahasanya

a, bc *  , a, bc, aa, abc, bca,... TEORI BAHASA OTOMATA 3

Definisi Rekursif

Ekspresi reguler yg paling sederhana :

, ,  Diberikan ekspresi reguler r1 and r2 Maka :

r1 r2 r1  r2 r1 *

Merupakan ekspresi reguler

 r1

TEORI BAHASA OTOMATA 4

Contoh 1 Ekspresi reguler

Bukan Ekspresi reguler :

 a b  c * (c )  a b 

TEORI BAHASA OTOMATA 5

Bahasa dari Ekspresi reguler L r : bahasa dari Ekspresi reguler r

contoh

L ( a b  c ) * , a, bc, aa, abc, bca,...

TEORI BAHASA OTOMATA 6

Definisi Untuk Ekspresi reguler yg paling sederhana:

L  L    L a  a TEORI BAHASA OTOMATA 7

Definisi (Lanjutan) Untuk Ekspresi reguler r1 dan r2

L r1 r2 L r1 L r2  L r1  r2 L r1 L r2  L r1 * L r1  * L  r1  L r1 TEORI BAHASA OTOMATA 8

Contoh 2

 a b   a* L  a b   a *L  a b  L a * L a b L a *  L a L b  L a *   a  b  a *  a, b , a, aa, aaa,...  a, aa, aaa,..., b, ba, baa,... Ekspresi reguler :

TEORI BAHASA OTOMATA 9

Tentukan L(r) dari : Ekspresi reguler

r  a b  * a bb

TEORI BAHASA OTOMATA 10

Jawab Ekspresi reguler

r  a b  * a bb Adalah :

L r  a, bb, aa, abb, ba, bbb,...

TEORI BAHASA OTOMATA 11

Tentukan L(r) dari : Ekspresi reguler

r  aa  * bb  *b

TEORI BAHASA OTOMATA 12

Jawab r  aa  * bb  *b

Ekspresi reguler

L r {a b

b : n, m 0}

2n 2m

TEORI BAHASA OTOMATA 13

Apakah berikut ini merupakan Ekspresi reguler?

L(r ) = { seluruh string yang tidak boleh ada dua “0” yang berurutan }

TEORI BAHASA OTOMATA 14

Contoh 1 Ekspresi reguler

r (0 1) * 00 (0 1) *

L(r ) = {seluruh string yang ada dua “0” yang berurutan }

TEORI BAHASA OTOMATA 15

Contoh 2 Reguler ekspresi

r (1 01) * (0 )

L(r ) = {seluruh string yang tidak ada dua “0” yang berurutan }

TEORI BAHASA OTOMATA 16

Equivalen ekspresi Reguler Definisi: ekspresi regular

r1 dan r2

adalah equivalen jika

L(r1) L( r2 )

TEORI BAHASA OTOMATA 17

Contoh

L = {seluruh string yang tidak ada dua “0” yang berurutan }

r1 (1 01) * (0 ) r2 (1* 011*) * (0 ) 1* (0 ) L(r1) L( r2 ) L TEORI BAHASA OTOMATA

r1 dan r2

Adalah equivalen Ekspresi reguler 18

Expresi Reguler dan Bahasa Reguler

TEORI BAHASA OTOMATA 19

Teorema General Bahasa dengan Ekspresi Reguler

Bahasa Regular

TEORI BAHASA OTOMATA 20

Pembuktian General Bahasa dengan Ekspresi Reguler

Bahasa Regular

General Bahasa dengan Ekspresi Reguler

Bahasa Regular

TEORI BAHASA OTOMATA 21

Pembuktian - bagian 1 General Bahasa dengan Ekspresi Reguler

Bahasa Regular

Untuk setiap ekspresi reguler r Bahasa L(r ) adalah reguler Pembuktian dengan induksi pada ukuran

r

TEORI BAHASA OTOMATA 22

Induksi Dasar Ekspresi reguler Paling Sederhana:

, , 

NFA

L(M1)  L() L(M 2 ) {} L() a

Bahasa reguler

L(M 3 ) {a} L(a)

TEORI BAHASA OTOMATA 23

Induksi Hipotesa Asumsi Untuk ekspresi reguler r1 dan r2 maka ;

L( r1) dan L( r2 ) adalah bahasa reguler

TEORI BAHASA OTOMATA 24

Langkah Induksi Pembuktian:

L r1 r2  L r1  r2  L r1 *

TEORI BAHASA OTOMATA

 L r1 

Adalah Bahasa Reguler

25

Dengan definisi dari ekspresi reguler, maka:

L r1 r2 L r1 L r2  L r1  r2 L r1 L r2  L r1 * L r1  * L  r1  L r1 TEORI BAHASA OTOMATA 26

Dengan hipotesis induksi didapatkan: L( r1) dan L( r2 ) adalah bahasa reguler

diketahui: Bahasa reguler adalah pendekatan dari 3 hal ini: L r1 L r2  Union

Concatenation Star TEORI BAHASA OTOMATA

L r1 L r2 

 L r1  *

27

Oleh karena itu :

L r1 r2  L r1 L r2  L r1  r2 L r1 L r2 

Adalah bahasa reguler

L r1 * L r1  * TEORI BAHASA OTOMATA 28

Kesimpulan:

L(( r1)) Adalah bahasa reguler

TEORI BAHASA OTOMATA 29

Pembuktian - bagian 2 General Bahasa dengan Ekspresi Reguler

Bahasa reguler

untuk setiap bahasa reguler L merupakan ekspresi reguler r dengan L( r ) L Pembuktian dengan contruksi pada Ekspresi reguler TEORI BAHASA OTOMATA 30

Selama L adalah reguler yang diambil dari NFA M yang diterimanya

L(M ) L

Satu state akhir TEORI BAHASA OTOMATA 31

Dari

M konstruksi untuk equivalen menggunakan

Graf Transisi secara Umum Dengan penamaan transisi adalah ekspresi reguler

Contoh :

M a

c a, b

a

c a b

TEORI BAHASA OTOMATA 32

Contoh Lain :

a q0

b

b

q1 a, b

q2

b

b

b

a q0

q1 a b q2

b TEORI BAHASA OTOMATA 33

b Perulangan state :

a q0

b

q1 a b q2

b

bb * a q0

b

bb * (a b)

q2

TEORI BAHASA OTOMATA 34

Kesimpulan Ekspresi Reguler :

bb * a q0

b

bb * (a b)

q2

r (bb * a) * bb * (a b)b * L( r ) L( M ) L

TEORI BAHASA OTOMATA

35

Secara Umum e c

Pergerakan Statenyad:

qi

qj

q

a

b

ae * d

ce * b ce * d

qj

qi TEORI BAHASA OTOMATA

ae * b 36

r4

Graf transisi Akhir : r1

r3 q0

r2

qf

Kesimpulan ekspresi reguler :

r r1 * r2 (r4 r3r1 * r2 ) * TEORI BAHASA OTOMATA

L( r ) L( M ) L 37

Standard dari Bahasa Reguler Bahasa reguler

FA NFA

Ekspresi Regular

TEORI BAHASA OTOMATA 38

Jika diberikan Bahasa Regular

Berarti:

L

Bahasa L adalah standar representasi

TEORI BAHASA OTOMATA 39

Properti dari Bahasa Regular

TEORI BAHASA OTOMATA 40

Untuk bahasa regular L1 dan Union: Concatenation:

L1 L2 L1L2

Star:

L1 *

Reversal:

R L1

Complement:

L1

Intersection:

L1 L2

TEORI BAHASA OTOMATA

L2

Adalah Bahasa Reguler

41

Bahasa reguler

L1

L M1  L1 NFA

M1

State yang diterima tunggal

Bahasa reguler

L2

L M2 L2 NFA

M2

State yang diterima tunggal

TEORI BAHASA OTOMATA 42

Contoh n 0

L1 {a b} n

M1 a b

M2 L2  ba

b

a

TEORI BAHASA OTOMATA 43

Union

L1 L2

NFA untuk

M1  

M2

TEORI BAHASA OTOMATA 44

NFA untuk

Contoh

L1 L2 {a b} {ba} n

L1 {a b} n

a

 

b

L2 {ba} b

a

TEORI BAHASA OTOMATA 45

Concatenation L1L2

NFA untuk

M1

M2 



TEORI BAHASA OTOMATA 46

Contoh L1L2 {a b}{ba} {a bba} n

n

NFA untuk

L1 {a b} n

L2 {ba}

a b



b

a



TEORI BAHASA OTOMATA 47

Star Operation

L1 * NFA untuk



L1 *

M1 



 TEORI BAHASA OTOMATA 48

Contoh NFA untuk

w w1w2  wk

L1* {a b} * n

wi L1



L1 {a b} n

a



TEORI BAHASA OTOMATA



b

 49

Reverse R NFA for L1

L1

M1

 M1

1. Reverse seluruh transisi 2. Buat state awal yg dapat diterima dan sebaliknya TEORI BAHASA OTOMATA 50

Contoh

M1 a

L1 {a b} n

b

a R L1

{ba } n

 M1 b

TEORI BAHASA OTOMATA 51

Complement

L1

M1

L1

 M1

1. Ambil FA yang diterima oleh

L1

2. Buat state akhir non-final, dan sebaliknya TEORI BAHASA OTOMATA Kenapa tdk NFA? 52

Contoh

M1 a, b

a

L1 {a b} n

b

n

L1 {a, b} *  {a b}

a, b

 M1

a, b

a b

a, b

TEORI BAHASA OTOMATA 53

Intersection L1 regular Lihat

L2 regular

L1 L2 regular

TEORI BAHASA OTOMATA 54

Hukum DeMorgan’s :

L1 L2 L1 L2

L1 , L 2

regular

L1 , L 2

regular

L1  L2

regular

L1  L2

regular

L1  L2

regular

TEORI BAHASA OTOMATA 55

Contoh

L1 {a b} regular n

L2 {ab, ba} regular

L1 L2 {ab} regular

TEORI BAHASA OTOMATA 56

Pembuktian lain untuk Closur Interseksi Mesin

Mesin

M1

FA untuk L1 Bangun FA baru

M2

FA untuk

M

yg dpt diterima

L2

L1 L2

M Simulasi secara paralel M1 dan M 2 TEORI BAHASA OTOMATA 57

State pada M

qi , p j State pada M1

State pada M 2

TEORI BAHASA OTOMATA 58

FA

q1

FA

M1 a

q2

a

p1

transisi

M2 p2

transisi

FA

q1, p1

M

a

q2 , p2

transisi TEORI BAHASA OTOMATA 59

FA

FA

M1

M2

q0

p0

State awal

State awal

FA

M

q0 , p0 State awal TEORI BAHASA OTOMATA 60

FA

FA

M1

M2

pj

qi State akhir

pk

State akhir FA

qi , p j

M qi , pk

State akhir Kedua isi harus dapat diterima oleh state TEORI BAHASA OTOMATA 61

M

Simulasi secara paralel

M1 dan M 2

M Menerima string w Jika dan hanya jika

M1 menerima stringw dan M 2 menerima stringw L( M ) L( M1) L( M 2 ) TEORI BAHASA OTOMATA 62

Contoh: n 0

m 0

L1 {a b}

L2 {ab }

M1

M2

n

a q0

b q2

m

q1

p0

a, b

b

a, b

a

b

p1

a p2

a, b

TEORI BAHASA OTOMATA 63

Konstruksi Mesin untuk Irisan

TEORI BAHASA OTOMATA 64

Automata untuk irisan n n L {a b} {ab } {ab}

a, b q0 , p0

a

b q1 , p2

q0 , p1

b

q1, p1

a

b

a

a b

q0 , p2

q2 , p2

q2 , p1

a

b a, b

TEORI BAHASA OTOMATA 65

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 66