8 April 2015 Teori Bahasa dan Otomata

EKSPRESI REGULAR MATERI MINGGU KE KE--4

• • • •

EKSPRESI REGULAR

Bahasa disebut reguler jika terdapat FSA yang dapat menerimanya. Bahasa reguler dinyatakan secara sederhana dengan ekspresi reguler/regular expression (RE). Contoh penerapan : searching string pada file RE -> NFA dengan e Move -> DFA

Definisi ekspresi reguler 1. Ø = {} = (himpunan kosong) adalah sebuah ekspresi regular 2. { ɛ } =string kosong adalah ekspresi regular 3. Untuk setiap a ϵ ∑, maka a adalah ekspresi regular 4. Jika a dan b adalah ekspresi regular maka a ∪ b , ab dan a* adalah ekspresi regular. “Ø yang melambangkan himpunan kosong, atau tidak punya anggota, sedangkan { ɛ } adalah himpunan yang memiliki satu anggota , yaitu string kosong.”

2 8 April 2015

Teori Bahasa dan Otomata

Notasi a ∪ b , ab dan a* adalah penyederhanaan notasi yang diperoleh dari notasi asli sebagai berikut : Jika dimiliki himpunan A,B sebagai himpunan berikut : • Ekspresi a ∪ b maksudnya : A={a} dan B={b} A ∪ B = gabungan/union antara himpunan A dengan himpunan B = {a,b} Dinotasikan secara singkat sebagai : a ∪ b • Ekspresi ab maksudnya : A={a} dan B={b} AB = CONCATENATION antara himpunan A dengan himpunan B = {ab} Dinotasikan secara singkat sebagai : ab • Ekspresi a* maksudnya : A={a} A* = CLEENE closure dari himpunan A, didefinisikan : A0 ∪ A1 ∪ A2 ∪....∪ A∞, yang menghasilkan suatu himpunan : { ɛ , a, aa, aaa, aaaa, ….}, dinotasikan sebagai a*

3 8 April 2015


Akibat Logis Ekspresi Reguler Reguler,, berdasarkan Aturan Aturan--Aturan dalam Teori Himpunan Himpunan,, 1. 2. 3. 4. 5. 6. 7. 8. 9. 10.

a∪b=b∪a a∪Ø=Ø∪a a∪a=a (a ∪ b) ∪ c = a ∪(b ∪ c) aɛ = ɛa = a aØ = Øa = Ø (ab)c=a(bc) a(b ∪ c)=ab ∪ ac = dan (a ∪ b)c = ac ∪ bc a* = a** = a*a* = (ɛ ∪ a)*=a*(a ∪ ɛ) = (a ∪ ɛ)a* = ɛ ∪ aa* aa*= a*a 4

8 April 2015


CONTOH

Ekspresikan dalam bentuk ekspresi reguler kalimat-kalimat berikut : • Sederatan NOL minimal nol buah Ekspresinya : 0* • Sederatan NOL minimal satu buah Ekspresinya : 00* • Sederetan NOL minimal satu buah diikuti sederetan SATU sebanyak satu buah atau lebih Ekspresinya : 00*11* • Sederetan bit NOL dan SATU sembarang yang diawali dengan NOL dan diakhiri dengan SATU Ekspresinya : 0(0,1)*1 atau ditulis : 0(0 ∪ 1)*1 • Sederetan SATU dengan jumlah GENAP Ekspresinya : 11(11)* • Sederetan NOL dengan jumlah GENAP diikuti sederetan SATU dengan jumlah GANJIL Ekspresinya : 00(00)*1(11)*

5 8 April 2015


CONTOH String apakah ekspresi-ekspresi regular berikut : a. Ekspresi : (1,0)* → Sederetan bit NOL dan SATU dengan jumlah sembarang dan susunan sembarang. b. Ekspresi : (0,1)*1* → Sederetan bit NOL dan SATU dengan jumlah sembarang urutan sembarang diikuti dengan deretan bit SATU dengan jumlah nol atau lebih. c. Ekspresi : (00)*(11)* → Deretan NOL kosong atau Genap diikuti deretan SATU kosong atau genap. a. Ekspresi : (11)* ∪ (00)* → String kosong atau berisi bit NOL genap atau bit SATU genap dengan posisi sembarang 6 8 April 2015


Bahasa Reguler Apabila r adalah RE, maka L(r) adalah bahasa reguler yang dibentuk menggunakan ekspressi reguler r. Contoh : Tentukan bahasa reguler yang dibentuk oleh r=(aa)* Jawab L(r) = L( (aa)* ) = { λ, aa, aaaa, aaaaaa, ... } = {a2n | n ≥ 0 } menyatakan himpunan string a dengan jumlah genap

7 8 April 2015


CONTOH •

Tentukan bahasa reguler yang dibentuk oleh r =(aa*)(bb)*b Jawab : L ( r ) = L((aa)*(bb)*b) = { an b2m+1 | n, m ≥ 0}

•

Tentukan ekspresi reguler pembentuk bahasa pada S = {0,1}, yaitu L(r) = { w ϵ ∑* | w memiliki substring ‘00’ } Jawab : r = (0+1)*00(0+1)*

•

Tentukan ekspresi reguler pembentuk bahasa pada ∑ = {a,b}, yaitu L(r) = { abnw | n ≥ 3 , w ϵ {a , b}+ } Jawab : r = abbb(a+b)(a+b)*

8 8 April 2015


Sifat Bahasa Reguler •

Tertutup terhadap operasi himpunan sederhana Jika L1 dan L2 adalah bahasa reguler, maka L1 U L2 L1 ∩ L2, L1L2, ~ (L1) dan L1* adalah bahasa reguler juga

•

Tertutup terhadap homomorphic image Jika L1 adalah bahasa reguler, maka homomorphic image h(L1) adalah bahasa reguler juga. Dimisalkan ∑ dan ᴦ adalah alfabet, maka fungsi homomorphic dinyatakan denganh : ∑→ᴦ jika w = a1 a2 ... an maka h(w) = h(a1) h(a2 ) ... h(an) Jika L adalah bahasa pada ∑ maka homomorphic image bahasa L adalah h(L)= { h(w) | w ϵ L}

9 8 April 2015


CONTOH •

Dimisalkan ∑ = {a,b} dan ᴦ = {a,b,c} dan didefinisikan h(a) = ab dan h(b) =bbc homomorphic image bahasa L = {aa,aba } adalah h(L)= { abab, abbbcab}

•

Dimisalkan ∑= {a,b} dan h(b) =bdc

•

homomorphic image bahasa L(r) yang dibentuk dari ekspresi reguler r = (a+b*)(aa)* adalah h(L(r)) yang dibentuk dengan ekspresi reguler r = (dbcc + (bdc)*) (dbccdbcc)*

ᴦ = {b,c,d} dan didefinisikan h(a) = dbcc dan

10 8 April 2015


Hubungan RE dan NFA

11 8 April 2015


Hubungan RE dan NFA

12 8 April 2015


Ekuivalensi NFA, DFA, dan RG

• DFA bisa dibentuk dari NFA. • RG bisa dibentuk dari DFA. • NFA bisa dibentuk dari RG

NFA

DFA

RG

13 8 April 2015


Pembentukan DFA dari NFA 1.

2. 3. 4.

5. 6.

Diberikan sebuah NFA F = (K, VT, M, S, Z). Akan dibentuk sebuah DFA F’ = (K’, V ’, M’, S’, Z’) dari NFA F tersebut. Algoritma pembentukannya adalah sbb. : Tetapkan : S’ = S dan VT’ = VT Copykan tabel NFA F sebagai tabel DFA F’. Mula-mula K’ = K dan M’ = M Setiap stata q yang merupakan nilai (atau peta) dari fungsi M dan q  K, ditetapkan sebagai elemen baru dari K’. Tempatkan q tersebut pada kolom Stata M’, lakukan pemetaan berdasarkan fungsi M. Ulangi langkah (3) sampai tidak diperoleh stata baru. Elemen Z’ adalah semua stata yang mengandung stata elemen Z. 14

8 April 2015


CONTOH

Berikut ini diberikan sebuah NFA F = (K, V , M, S, Z) dengan : K = {A, B, C}, VT = {a, b}, S = A, Z = {C}, dan M didefinisikan sebagai berikut : STATA K NFA F

Input a

b

A

[A,B]

C

B

A

B

C

B

[A,B]

Tentukan DFA hasil transformasinya !

15 8 April 2015


Jawab: Berdasarkan algoritma di atas, maka : 1. S’ = S = A, VT’ = VT = {a, b}. 2. Hasil copy tabel NFA F menghasilkan tabel DFA F’ berikut : STATA K’ NFA F’

3.

Input a

b

A

[A,B]

C

B

A

B

C

B

[A,B]

Pada tabel DFA F’ di atas terdapat stata baru yaitu [A,B]. Pemetaan [A,B] adalah : M([A,B],a) = M(A,a) ∪ M(B,a) = [A,B] ∪ A = [A,B], dan M([A,B],b) = M(A,b) ∪ M(B,b) = C ∪ B = [B,C], sehingga diperoleh tabel berikut : STATA K’ NFA F’

8 April 2015

Input a

b

A

[A,B]

C

B

A

B

C

B

[A,B]

[A,B]

[A,B]

[B,C] Teori Bahasa dan Otomata

16

4.

Langkah (3) di atas menghasilkan stata baru yaitu [B,C]. Setelah pemetaan terhadap [B,C] diperoleh tabel berikut : STATA K’ NFA F’

Input a

b

A

[A,B]

C

B

A

B

C

B

[A,B]

[A,B]

[A,B]

[B,C]

[B,C]

[A,B]

[A,B]

5. Setelah langkah (4) di atas tidak terdapat lagi stata baru. Dengan demikian DFA F’ yang dihasilkan adalah : DFA F’ = (K’, VT’, M’, S’, Z’), dimana : K’ = {A, B, C, [A,B], [B,C]}, VT’ = {a, b}, S’ = A, Z’ = {C, [B,C]}. Fungsi transisi M’ serta Graf dari DFA F’ adalah sebagai berikut :

17 8 April 2015


Pembentukan RG dari DFA Diketahui sebuah DFA F = (K, VT, M, S, Z). Akan dibentuk RG G = (VT’,VN, S’, Q). Algoritma pembentukan RG dari DFA adalah sebagai berikut : • Tetapkan VT’ = VT, S’ = S, VN = S • Jika Ap, Aq ϵ K dan a ϵ VT, maka : M(Ap, a) = A ekuivalen dengan produksi A p  aA q , jika A q  Z

  A p  a, jika A q  Z

18 8 April 2015


CONTOH Diketahui sebuah DFA F dengan Z = {S} dan fungsi transisi M sebagai berikut : Dengan algoritma di atas maka diperoleh Q(RG)sbb. : M(S,0) = B  S  0B STATA K DFA INPUT F M(S,1) = A S  1A 0 1 M(A,0) = C  A  0C S B A M(A,1) = S A  1 A C S M(B,0) = S  B  0 M(B,1) = C B 1C B S C M(C,0) = A  C  0A C A B M(C,1) = B C  1B RG yang dihasilkan adalah G(VT’, VN, S’, Q), dengan VT’ = {0,1}, VN = {S, A, B, C}, S’ = S, dan Q = {S  0B, S  1A, A  0C, B 1C, C  0A, C  1B, A  1, B  0}

19 8 April 2015


Pembentukan NFA dari RG Diketahui RG G = (VT, VN, S, Q). Akan dibentuk NFA F = (K, VT’, M, S’, Z). Algoritma pembentukan NFA dari RG : 1. Tetapkan VT’ = VT, S’ = S, K = VN 2. Produksi Ap  a Aq ekuivalen dengan M(Ap, a) = Aq Produksi Ap  a ekuivalen dengan M(Ap , a) = X, dimana X  V 3. K = K ∪ {X} 4. Z = {X}

20 8 April 2015


CONTOH Diketahui RG G = (VT, VN , S, Q) dengan : VT = {a, b}, VN = {S, A, B}, S = S, dan Q = {S  aS, S  bA, A  aA, A  aB, B  b} Tabel M :

STATA K NFA F

INPUT a

b

S

S

A

A

[A,B]

⌽

B

⌽

X

X

⌽

⌽

Terapkan algoritma di atas untuk memperoleh NFA F sebagai berikut : 1. VT’ = VT = {a, b}, S’ = S, K = VN = {S, A, B} 2. S  aS  M(S,a) = S, S  bA  M(S,b) = A, A  aA  M(A,a) = A, A  aB  M(A,a) = B, B  b  M(B,b) = X NFA yang diperoleh : F(K, VT’, M, S’, Z), dengan K = {S, A, B, X}, VT’ = {a, b}, S’ = S, Z = {X},

21

8 April 2015


Ekuivalensi NFA NFA-- Dengan ER (Ekspresi (Ekspresi Regular)

22 8 April 2015


CONTOH

Tentukan NFA untuk ekspresi regular r = 0(1  23)* Jawab : r1 = 0  r2 = 1  r3= 23 

r4= r2 r3 = 1 23 

23 8 April 2015


CONTOH r5= r4* = (1 23)* 

r = r5= 0(1 23)* 

24 8 April 2015


TERIMAKASIH Lilis Setyowati

25 8 April 2015


8 April 2015 Teori Bahasa dan Otomata

Recommend Documents