Definisi Bahasa Regular
Misalkan S merupakan sebuah abjad. Kumpulan dari bahasa regular berdasar S didefinisikan secara rekursif sebagai berikut [1] :
(1) Æ adalah sebuah bahasa regular
(2) {l} adalah sebuah bahasa regular
(3) untuk setiap a Î S, {a} merupakan bahasa regular. Disebut juga bahasa singleton
(4) Jika A dan B bahasa regular maka AÈB, A.B, dan A* atau B* merupakan bahasa regular.
(5) Tidak ada bahasa lain berdasarkan S yang regular.
Contoh 1 : Misalkan S = {a,b}, maka berikut ini merupakan bahasa-bahasa regular berdasarkan S yaitu Æ , {l},{a},{b},{a,b},{ab},{a,ab,b},{ai | i ³0}, {(ab)i | i ³ 0}
Ekspresi Regular
Ekspresi Regular (Regular Expression), disingkat RE, didefinisikan sebagai berikut:
(1) Æ merupakan ekspresi regular untuk bahasa regular Æ
(2) l merupakan ekspresi regular untuk bahasa regular {l}
(3) a merupakan ekspresi regular untuk bahasa singleton {a}
(4) Jika r ekspresi regular untuk bahasa regular A dan s sebuah ekspresi regular untuk bahasa regular B, maka
- r + s merupakan ekspresi regular untuk bahasa A È B
- rs merupakan ekspresi regular untuk bahasa A.B
- r* merupakan ekspresi regular untuk bahasa A*
Contoh 2:
Bahasa Regular | RE |
{l} | l |
{a} | a |
{a,b} | a+b |
{ab} | ab |
{a,aa} | a+aa |
{a}* | a* |
{a,b}* | (a+b)* |
{l,ab}* | (l+ab)* |
Teorema
Misalkan r,s dan t merupakan ekspresi regular berdasar abjad S yang sama, maka berlaku :
(1) r + s = s + r
(2) r + Æ = Æ + r = r
(3) r + r = r
(4) (r + s) + t = r + (s + t)
(5) r.l = l.r = r
(6) r.Æ = Æ.r = Æ
(7) (rs)t = r(st)
(8) r (s + t) = rs + rt dan (r + s) t = rt + st
(9) r* = r** = r* r* = (l + r)* = r* (r + l) = (r + l) r* = l + rr*
(10) (r+s)* = (r* + s*)* = (r* s*)* = (r* s)* r* = r* (sr*)*
(11) r (sr)* = (rs)* r
(12) (r* s)* = l + (r + s)*s
(13) (rs*)* = l + r(r+s)*
(14) s (r+l)*(r+l)+s = sr*
(15) rr* = r*r = r+
Seperti halnya dalam operasi aritmatik, untuk menghilangkan ambiguitas saat menggunakan notasi +, * dan concat, maka diperlukan suatu hirarki penulisan notasi. Hirarki tertinggi adalah *, kemudian concat, dan terakhir +. Tanda kurung berperan untuk mengelompokkan suatu subekspresi sebagai satu entitas ekspresi seperti halnya penulisan formula aritmatika. Misalkan : aa*(b+ba*)*b
Berikut ini contoh penulisan ekspresi regular dari pendefinisian bahasa regular :
Contoh 3: Jika S = {a,b} dan L adalah bahasa berdasarkan abjad S yang semua string didalamnya mempunyai panjang genap. (termasuk l Î L, dimana panjangnya nol)
Setiap string yang panjangnya genap merupakan hasil operasi concat dari string dengan panjang 2 atau dapat dituliskan : L = {aa + ab + ba + bb}* dimana dapat dinyatakan dengan ekspresi regular
(aa+ab+ba+bb)* = (a(a+b) + b(a+b))*
= ((a+b)(a+b))*
Contoh 4: Jika S = {a,b} dan L adalah bahasa berdasarkan abjad S yang semua string didalamnya diakhiri dengan double a.
Sembarang string berdasarkan abjad S dapat dituliskan L1 = {a,b}*, dan kemudian diconcat dengan L2 = {aa} , sehingga menjadi L1.L2 = {a,b}*{aa}. Jika dituliskan dalam ekspresi regular : (a+b)*(aa)
Finite Automata (FA)
Suatu Finite Automata (FA) atau kadang disebut Finite State Automaton (FSA) adalah mesin abstrak yang dapat mengenali bahasa regular.
FA didefinisikan sebagai berikut :
Suatu FA merupakan mesin status hingga yang terdiri dari 5 tuple yaitu (Q,S,s,F,d) dimana
- Q merupakan himpunan berhingga dari state (status)
- S adalah himpunan alfabet dari simbol input.
- s Î Q merupakan sebuah state yang berlaku sebagai state awal (start state).
- F Í Q yang merupakan state akhir (final state)
- d adalah fungsi transisi yang memetakan Q x S ke Q , ditulis d(Q,S) = Q
Contoh 5: Diketahui sebuah FA M = (Q,S,s,F,d) dimana Q = {q0, q1, q2}, S = {a,b}, s = q0, F = {q0} dan d :
| a | b |
q0 | Q1 | q2 |
q1 | Q2 | q0 |
q2 | Q2 | q2 |
FA tersebut dapat dinyatakan dalam bentuk digraf sebagai berikut:

Finite Automata dan Bahasa Regular
Dalam definisi suatu FA terdapat sejumlah status akhir. Apabila sebuah string masukan membawa status FA mulai dari status awal ke salah satu status akhir maka string tersebut diterima atau dikenali oleh FA tersebut. Dan sebuah bahasa L dikatakan diterima oleh sebuah FA jika semua string elemen bahasa L diterima oleh FA tersebut.
Contoh 6 : Perhatikan FA pada contoh 5, string ab diterima oleh FA tersebut karena jika kita mulai dari status awal q0 membaca input a, kita akan menuju status q1. Kem udian dari q1 membaca b, menuju status q0. Disini pembacaan inpu selesai, dan berhenti di status akhir (final state). Sehingga ab diterima oleh FA tersebut.
Contoh 7 : String aab tidak diterima oleh FA pada contoh 5. Mengapa? String apa saja yang diterima oleh FA tesebut? Bahasa apa yang diterima oleh FA tersebut?
Nondeterministic Finite Automata
FA pada contoh 5 merupaka Deterministic Finite Automata, dimana banyaknya transisi dari satu status ke status lainnya satu dan hanya satu. Nondeterministic Finite Automata adalah FA yang banyaknya fungsi transisi (d) dari satu state ke state lainnya nol, satu atau lebih dari satu state.
Contoh 8 : Berikut ini adalah NFA M = (Q,S,s,F,d) dimana Q = {q0, q1, q2}, S={a,b}, s=q0, F = {q0} dan d :
| a | b |
Q0 | {q1} | {} |
Q1 | {} | {q0,q2} |
Q2 | {q0} | {} |
Atau dalam bentuk digraf :

Ekivalensi NFA dan DFA
Jika terdapat sebuah NFA M = (Q,S,s,F,d) yang menerima bahasa L, maka ada DFA M’=(Q’,S’, s’,F’,d’) yang juga menerima bahasa L , dimana :
(1) S’ = S
(2) s’ = s
(3) Jika Q = {q0, q1, …, qn} maka mula-mula Q’ = { [q0],[q1],…,[qn]}
(4) Jika d(qi,a) = {qj, qk, …} dan a Î S, maka d’([qi],a) = [qj, qk, …] dan [qj, qk, …] menjadi state baru dan digabungkan ke Q’
(5) Setiap state baru dalam Q’ yang diperoleh, dicari transisi untuk setiap input dalam S’. Dimana d’([qj, qk, …],a) = d(qj,a) È d(qk,a) È …
(6) F’ terdiri dari semua state di Q’ yang mengandung state di F.
Contoh 9 : Carilah sebuah DFA M’=( Q’,S’,s’,F’,d’) yang ekivalen dengan NFA M=(Q,S,s,F,d) pada contoh

.
(1) S’ = S = {a,b}
(2) s’ = s = [q0]
(3) Qmula-mula = {[q0],[q1],[q2]}
(4) d(q0,a) = {q1} à d’(q0,a) = [q1]
d(q0,b) = {} à d’(q0,b) = [ ] (state baru)
d(q1,a) = {} à d’(q1,a) = [ ]
d(q1,b) = {q0,q2} à d’(q1,b) = [q0, q2] (state baru)
d(q2,a) = {q0} à d’(q2,a) = [q0]
d(q2,b) = {} à d’(q2,b) = [ ]
maka Q’ = {[q0],[q1],[q2], [],[q0, q2]}
(5) d’( [] , a) = []
d’( [] , b) = []
d’( [q0, q2], a ) = d(q0,a) È d(q2,a) = {q1} È {q0} = {q0,q1} à [q0,q1]
d’( [q0, q2], b ) = d(q0,b) È d(q2,b) = {} È {} = {} à []
d’( [q0, q1], a ) = d(q0,a) È d(q1,a) = {q1} È {} = {q1} à [q1]
d’( [q0, q1], b ) = d(q0,b) È d(q1,b) = {} È {q0,q2} = {q0,q2}
Tidak ada state baru.
(6) F’ = {[q0], [q0,q2],{qo,q1}}
Maka kita mendapatkan sebuah DFA M’ = (Q’,S’,s’,F’,d’) dengan Q’ = {[q0], [q1], [q2], [], [q0,q1], [q0,q2]}, S’ = {a,b}, s’ = [q0], F’ = {[q0], [q0,q2], [qo,q1]}, dan d’ :
| a | b |
[q0] | [q1] | [] |
[q1] | [] | [q0,q2] |
[q2] | [q0] | [] |
[] | [] | [] |
[q0,q2] | [q0,q1] | [] |
[q0,q1] | [q1] | [q0,q2] |
Finite Automata Dengan Transisi Hampa (l-transition)
Adalah NFA yang mempunyai transisi yang tidak bergantung dari suatu input tertentu. Atau dengan kata lain, dapat berpindah dari satu state ke state lain tanpa membaca input apapun.
Contoh :

l-Closer
Untuk sebuah state q Î Q dari NFA M=(Q,S,s,F,d) dengan transisi-l, didefinisikan penutup-l (l-closer) dari q dimana :
l-cl(q) = {p | p Î Q dan p dapat dicapai dari q tanpa input apapun}
sedangkan
l-cl({qi1 , qi2, qi3, …, qik}) = 

dimana a Î S., qi Î Q. dan
d(q,a) = {p | pÎ Q dimana ada transisi dari q ke p dengan input a}

Setiap state punya tran sisi-l ke state itu sendiri, meskipun tidak digambarkan.
Eliminasi Transisi-l
Jika NFA M=(Q,S,s,F,d) dengan transisi-l, maka terdapat NFA lain M’=(Q’,S’,s’,F’,d’) tanpa transisi-l yang mendefinisikan bahasa yang sama dimana :
d’(q,a) = l-cl (d (l-cl (q), a))
dan
F’ = F È { q | (l-cl(q) Ç F) ¹ Æ }
Contoh 10 : Hilangkan transisi-l dari NFA berikut :

Dari gambar diatas kita dapat menentukan bahwa S = {a,b}, F = {q1} dan
d(q0,a) = {} l-cl(q0) = {q0, q1}
d(q0,b) = {q0} l-cl(q1) = {q1}
d(q1,a) = {q1}
d(q1,b) = {}
Maka :
(1) d’(q0,a)
§ l-cl(q0) = {q0, q1}
§ d({q0, q1},a) = d(q0,a) È d(q1,a) = {} È {q1} = {q1}
§ l-cl(q1) = {q1}
§ maka d’(q0,a) = {q1}
(2) d’(q0,b)
§ l-cl(q0) = {q0, q1}
§ d({q0, q1},b) = d(q0,b) È d(q1,b) = {q0} È {} = {q0}
§ l-cl(q0) = {q0, q1}
§ maka d’(q0,b) = {q0, q1}
(3) d’(q1,a)
§ l-cl(q1) = {q1}
§ d(q1,a) = {q1}
§ l-cl(q1) = {q1}
§ maka d’(q1,a) = {q1}
(4) d’(q1,b)
§ l-cl(q1) = {q1}
§ d(q1,b) = {}
§ l-cl({}) = {}
§ maka d’(q1,a) = {}
(5) F’ = {q1} È {q0, q1} = {q0, q1}
Jadi NFA tanpa transisi-l adalah :


Finite Automata & Ekspresi Regular
Jika r1 dan r2 adalah ekspresi regular yang mendefinisikan sebuah bahasa regular L, maka kita dapat membentuk sebuah NFA dari bahasa regular L tersebut, dimana
(1) RE : l
FA :

(2) RE : Æ
FA :

(3) RE : r
FA :

(4) RE : r1 + r2
FA :

(5) RE : r1.r2
FA :

(6) RE : r1*
FA :

Jika diketahui RE sebuah bahasa regular L, maka kita dapat membentuk sebuah DFA yang menerima bahasa L dengan langkah-langkah :
(1) Bentuklah NFA dengan transisi-l dari RE tersebut
(2) Eliminasi transisi-l dari NFA di langkah (1)
(3) Rubah NFA yang diperoleh di langkah (2) menjadi DFA
Sebaliknya jika terdapat sebuah FA M = (Q,S,s,F,d) yang menerima bahasa L, maka kita dapat menentukan RE dari bahasa L dimana jika qj Î d(qi,s) dan s Î S maka terdapat persamaan :

Lemma Arden : Persamaan X = AX + B ekivalen dengan X = A*.B
Contoh 11: Tentukan RE dari FA berikut

Kita dapatkan persamaan :
A0 = aA0 + bA1 …..(1)
A1 = l …………….(2)
Persamaan (2) disubstitusikan ke persamaan (1) sehingga :
A0 = aA0 + b.l
A0 = aA0 + b ………(3)
Menurut lemma Arden , persamaan (3) ekivalen dengan :
A0 = a*.b
RE yang mendefinisikan bahasa L, didapatkan dari A0. Jadi RE : a*b
Ekivalensi Dua DFA
Jika M = (Q,S,s,F,d) adalah DFA yang menerima bahasa L dan M’=(Q’,S’,s’,F’,d’) adalah DFA yang menerima bahasa L’, maka M dan M’ dikatakan ekivalen jika M dan M’ menerima bahasa yang sama (L = L’). Kita dapat menentukan apakah dua DFA M dan M’ ekivalen dengan menggunakan algoritma Moore sebagai berikut, misalkan S = {a,b}:
(1) Setiap state dari M dan M’ diberi label/nama yang semuanya berbeda (tidak boleh ada duplikat label)
(2) Buat tabel perbandingan yang terdiri dari N(3 karena jumlah symbol ada 2) kolom. Elemen dari tabel berbentuk pasangan (q,q’) dimana qÎQ dan q’ÎQ’. Sebagai inisial, pasangan (s,s’) ditempatkan di kolom pertama baris pertama.
(3) Tempatkan di kolom pertama, baris pertama pasangan (s,s’). Dan di kolom kedua diisi dengan pasangan (d(s,a),d’(s’,a)) dan di kolom ketiga diisi dengan pasangan (d(s,b), d’(s’,b))
(4) Dari hasil langkah (3), jika elemen di kolom kedua dan kolom ketiga belum pernah muncul di kolom pertama, maka kita tempatkan di kolom pertama baris berikutnya.
(5) Jika dalam proses muncul pasangan (q,q’) dimana q Î F dan q’ Ï F’ atau sebaliknya q Ï F dan q’ÎF’ maka proses berhenti dan disimpulkan bahwa M dan M’ tidak ekivalen.
(6) Proses berhenti dengan kesimpulan bahwa M ekivalen dengan M’ jika sudah tidak ada lagi pasangan baru yang ditempatkan di kolom pertama.
Contoh 12: Tentukan apakah dua DFA berikut ekivalen


Tabel perbandingan :
| a | b |
(1,4) | (1,4) | (2,5) |
(2,5) | (3,6) | (1,4) |
(3,6) | (2,7) | (3,6) |
(2,7) | (3,6) | (1,4) |
Maka kedua DFA diatas ekivalen
Minimize DFA
Misalkan M = (Q,S,s,F,d) adalah sebuah DFA dengan n buah state, maka terdapat DFA lain M’= (Q’,S’,s’,F’,d’) yang mempunyai < n buah state, yang menerima bahasa yang sama dengan M. Untuk mendapatkan M’ yang jumlah statenya lebih minimum digunakan algoritma sebagai berikut :
(1) Buat sebuah partisi p yang mula-mula berisi dua kelas/grup. Kelas pertama berisi state akhir dan kelas kedua beranggotakan state-state yang bukan state akhir.
(2) Untuk setiap grup dalam p dipecah (split) menjadi subgrup-subgrup dimana state s dan t akan terletak dalam grup yang sama jika dan hanya jika dari state s dan t dengan input a akan menuju ke state yang terletak di grup yang sama
(3) Proses berhenti jika sudah tidak ada lagi grup yang dapat dipecah.
Contoh 13 : Minimalkan jumlah state dari DFA berikut :

Soal-Soal
1. Tentukan RE dari bahasa regular berdasarkan S = {a,b} berikut :
(a) L = {abia | i ³0 } (b) L = {(aa)i | i ³ 0 }
(c) L = {(ab)ia | i ³ 0 } (d) L = {aibj | i,j ³ 0 }
(e) Bahasa yang semua string didalamnya diakhiri dengan double b
(f) Bahasa yang terdiri dari sebarang untai
(g) Bahasa yang semua stringnya terdiri dari simbol b saja dengan panjang string ganjil.
(h) Bahasa yang terdiri dari sebarang untai dengan panjang string genap.
2. Tentukan bahasa apa yang didefinisikan oleh RE berikut ini :
(a) ab* (b) b*aa
(c) (a+b)(a+b) (d) (a+b)*ab(a+b)*
Komentar
Posting Komentar
Suwon wes komen