Ekspresi Regular. Teori Bahasa dan Automata. Viska Mutiawani - Informatika FMIPA Unsyiah

Ekspresi Regular Teori Bahasa dan Automata

Viska Mutiawani - Informatika FMIPA Unsyiah

1

Ekspresi Regular Ekspresi Regular (Regular expressions) mendeskripsikan bahasa regular

(a  b  c) * Contoh: mendeskripsikan bahasa

a, bc*   , a, bc, aa, abc, bca,... Viska Mutiawani - Informatika FMIPA Unsyiah

2

Recursive Definition Ekspresi regular primitif: ,  ,  Diberikan ekspresi regular r1 dan r2

r1  r2 r1  r2 r1 *

Merupakan ekspresi regular

r1  Viska Mutiawani - Informatika FMIPA Unsyiah

3

Contoh Suatu Ekspresi regular:

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

Bukan ekspresi regular:

a  b  


4

Bahasa Ekspresi Regular Lr  : bahasa dari ekspresi regular r Contoh

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


5

Definisi Bagi ekspresi regular primitif:

L    L     La   a Viska Mutiawani - Informatika FMIPA Unsyiah

6

Definisi (2) Untuk ekspresi regular r1 and

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


7

Contoh

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 regular:


8

Contoh Ekspresi regular

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

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


9


r  aa  * bb  * b 2n 2m

Lr   {a b

b : n, m  0}


10


L(r )

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

= { semua string yang mengandung substring 00 }


11


L(r )

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

= { semua string tanpa substring 00 }


12

Ekuivalensi Ekspresi Regular Definisi: Ekspresi Regular

r1 and r2

adalah ekuivalen jika

L(r1 )  L( r2 )


13

Contoh L

= { semua string tanpa substring 00 }

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

r1

dan

r2

merupakan ekspresi regular yang ekuivalen


14

Ekspresi Regular dan Bahasa Regular


15

Teorema Bahasa yang dihasilkan oleh Ekspresi Regular




Bahasa Regular

16

Pembuktian: Bahasa yang dihasilkan oleh Ekspresi Regular



Bahasa Regular

Bahasa yang dihasilkan oleh Ekspresi Regular



Bahasa Regular


17

Pembuktian bagian 1 Bahasa yang dihasilkan oleh Ekspresi Regular



Bahasa Regular

Untuk setiap ekspresi regular r maka bahasa L (r ) adalah regular Pembuktian secara induksi terhadap Viska Mutiawani - Informatika FMIPA Unsyiah

r 18

Basis Induksi Primitive Regular Expressions:

,  , 

Bentuk NFAnya

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

Bahasa regular

L( M 3 )  {a}  L(a ) Viska Mutiawani - Informatika FMIPA Unsyiah

19

Hipotesis Induksi Anggap Untuk ekspresi regular r1 dan r2 , L(r1 ) dan L(r2 ) adalah bahasa regular


20

Langkah Induksi Kita akan buktikan:

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

adalah bahasa regular

Lr1  Viska Mutiawani - Informatika FMIPA Unsyiah

21

Berdasarkan definisi dari ekspresi regular:

Lr1  r2   Lr1   Lr2  Lr1  r2   Lr1  Lr2  Lr1 *   Lr1  * Lr1   Lr1  Viska Mutiawani - Informatika FMIPA Unsyiah

22

Secara induksi kita ketahui: L( r1 ) dan L( r2 ) adalah bahasa regular Sebab kita ketahui bahwa: Bahasa Regular adalah tertutup di bawah operasi: Union

Lr1   Lr2 

Concatenation

Lr1  Lr2 

Star

 Lr1  * Viska Mutiawani - Informatika FMIPA Unsyiah

23

Oleh karena itu:

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

Adalah bahasa regular

Lr1 *   Lr1  * L((r1 ))  L(r1 ) Akhir pembuktian 1

Secara tidak langsung, bahasa regular juga (melalui induksi) Viska Mutiawani - Informatika FMIPA Unsyiah

24

Berdasarkan regular closure dari operasi ini, kita dapat membangunkan NFA M yang menerima L( M )  L( r ) Contoh:

r  r1  r2

L( M )  L( r )

L( M 1 )  L(r1 )

 L( M 2 )  L(r2 )




25

Pembuktian bagian 2 Bahasa yang dihasilkan oleh Ekspresi Regular



Bahasa Regular

Untuk setiap bahasa regular L akan ada ekspresi regular r sehingga L ( r )  L Kita akan mengkonversi NFA yang menerima ke bentuk ekspresi regular Viska Mutiawani - Informatika FMIPA Unsyiah

L 26

Sebab L adalah regular, maka akan ada NFA M yang menerima bahasa tersebut

L( M )  L

Gunakan yang memiliki satu state penerima Viska Mutiawani - Informatika FMIPA Unsyiah

27

Dari M konstruksikan Graf Transisi Umum yang ekuivalen dimana label transisi berupa ekspresi regular Contoh: Graf Transisi Umum yang ekuivalen

M a

c

a

a, b

c ab


28

a q0

Contoh lain

b

b

q1 a, b

q2

b

b

b

Label transisi berupa Ekspresi regular

a q0

q1 a  b q2

b Viska Mutiawani - Informatika FMIPA Unsyiah

29

b

a q0

Mengurangi state

b

q1 a  b q2

b

Label transisi berupa Ekspresi regular

bb * a q0

b

bb * (a  b)


q2 30

Hasilnya:

bb * a q0

b

bb * (a  b)

q2

r  (bb * a ) * bb * (a  b )  b *

L(r )  L( M )  L Viska Mutiawani - Informatika FMIPA Unsyiah

31

Secara umum e

Mengurangi state

c

d

qi

qj

q

a

b

ae * d

ce * b ce * d

qi

qj ae * b Viska Mutiawani - Informatika FMIPA Unsyiah

32

Dengan mengulangi langkah tersebut hingga dua state yang tersisa, graf terhasil: Graf awal

Graf hasil

r1

r4 r3

q0

r2

qf

Ekspresi regular yang terhasil:

r  r1 * r2 (r4  r3r1 * r2 ) * L(r )  L( M )  L Akhir pembuktian 2


33

Representasi standar bahasa regular Bahasa Regular

DFA

NFA


Ekspresi Regular

34

Jika: Kita diberikan bahasa regular

Bermakna:

L

Bahasa L dapat direpresentasikan dengan DFA, NFA, ekspresi regular


35

Ekuivalensi NFA-ε Dengan ER (Ekspresi Regular) NFA- ε = NFA-λ

(Automata Hingga Non-deterministik = NFA)

atau λ

atau r1 ˅ r2 atau r1 + r2


36

Tentukan NFA untuk ekspresi regular r = 0(1+23)*


37


38

Ekspresi Regular. Teori Bahasa dan Automata. Viska Mutiawani - Informatika FMIPA Unsyiah

Recommend Documents