EKSPRESI REGULER

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 


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

contoh

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


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 :


Tentukan L(r) dari : Ekspresi reguler

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


Jawab Ekspresi reguler

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

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


Tentukan L(r) dari : Ekspresi reguler

r  aa  * bb  *b


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

Ekspresi reguler

L r {a b

b : n, m 0}

2n 2m


Apakah berikut ini merupakan Ekspresi reguler?

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


Contoh 1 Ekspresi reguler

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

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


Contoh 2 Reguler ekspresi

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

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


Equivalen ekspresi Reguler Definisi: ekspresi regular

r1 dan r2

adalah equivalen jika

L(r1) L( r2 )


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


Teorema General Bahasa dengan Ekspresi Reguler

Bahasa Regular


Pembuktian General Bahasa dengan Ekspresi Reguler

Bahasa Regular

General Bahasa dengan Ekspresi Reguler

Bahasa Regular


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


Induksi Dasar Ekspresi reguler Paling Sederhana:

, , 

NFA

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

Bahasa reguler

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


Induksi Hipotesa Asumsi Untuk ekspresi reguler r1 dan r2 maka ;

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


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


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


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


Kesimpulan Ekspresi Reguler :

bb * a q0

b

bb * (a b)

q2

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


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


Jika diberikan Bahasa Regular

Berarti:

L

Bahasa L adalah standar representasi


Properti dari Bahasa Regular


Untuk bahasa regular L1 dan Union: Concatenation:

L1 L2 L1L2

Star:

L1 *

Reversal:

R L1

Complement:

L1

Intersection:

L1 L2


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


Contoh n 0

L1 {a b} n

M1 a b

M2 L2  ba

b

a


Union

L1 L2

NFA untuk

M1  

M2


NFA untuk

Contoh

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

L1 {a b} n

a

 

b

L2 {ba} b

a


Concatenation L1L2

NFA untuk

M1

M2 




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

n

NFA untuk

L1 {a b} n

L2 {ba}

a b



b

a




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






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


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


Intersection L1 regular Lihat

L2 regular

L1 L2 regular


Hukum DeMorgan’s :

L1 L2 L1 L2

L1 , L 2

regular

L1 , L 2

regular

L1  L2

regular

L1  L2

regular

L1  L2

regular


Contoh

L1 {a b} regular n

L2 {ab, ba} regular

L1 L2 {ab} regular


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


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


Konstruksi Mesin untuk Irisan


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


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


EKSPRESI REGULER

Recommend Documents