*PERTEMUAN IVEkspresi Regular dan Kelas Bahasa RegularTujuan InstruksionalSetelah mempelajari diharapkan :Memahami pengertian ekspresi regular, kaidah-kaidah ekspresi regular dan operasi-operasi yang dapat dikerjakan pada ekspresi regular. Dapat mengaitkan ekspresi regular dengan bahasa regular dan selanjutnya dengan tata bahasa regular.Penguasaan hubungan timbal balik antara bahasa dan tata bahasa sedemikian sehingga jika dimiliki suatu bahasa akan dapat ditetapkan tata bahasanya dan sebaliknya jika dimiliki tata bahasa akan dapat ditetapkan bahasanya.

Ekspresi RegularJika adalah suatu himpunan abjad (yang tentu saja jumlahnya terhingga), maka:* = himpunan seluruh string yang dapat disusun dari abjad dalam , adalah berjumlah TAK HINGGA (countably infinite)Kumpulan dari semua bahasa yang dapat dibangkitkan dari abjad dalam berjumlah tak terhitung (uncountably)Definisi Ekspresi Regular : = {} = (himpunan kosong) adalah sebuah ekspresi regular{} = string kosong adalah ekspresi regular*

*Ekspresi Regular3. Untuk setiap a , maka a adalah ekspresi regular4. Jika a dan b adalah ekspresi reguler maka a b, ab dan a* adalah ekspresi regular.

Perlu dibedakan dengan jelas antara yang melambangkan himpunan kosong, atau tidak punya anggota.Sedangkan {} adalah himpunan yang memiliki satu anggota, yaitu string kosong.Notasi ab, ab dan a* adalah penyederhanaan notasi yang diperoleh dari notasi asli sbb:Jika dimiliki himpunan A,B sebagai himpunan sbb:

*Ekspresi RegularEkspresi ab maksudnya:A={a} dan B={b}AB= gabungan/union antara himpunan A dengan himpunan B={a,b} ini dinotasikan secara singkat sebagai: abEkspresi ab maksudnya:A={a} dan B={b}AB= CONCATENATION antara himpunan A dengan himpunan B={ab} ini dinotasikan secara singkat sebagai: ab

Ekspresi RegularEkspresi a* maksudnya:A={a}A*= CLEEN closure dari himpunan A, seperti yang telah didefinisikan dalam Pertemuan II: AoA1A2Ayang menghasilkan suatu himpunan : {, a, aa, aaa, aaaa}, dinotasikan sebagai a*Jika a,b,c adalah ekspresi reguler dalam ab=ba6. a= a= a= a7. (ab)c=a(bc)aa=a8. a(bc)=abac=dan (ab)c=acbc(ab)c=a(bc)9. a*=a**=a*a*=(a)*=a*(a)=(a)a*= aa*a= a=a10. aa*=a*a*

Ekspresi RegularContoh:A. Ekspresikan dalam bentuk ekspresi reguler kalimat berikut:Sederetan NOL minimal nol buahSederetan NOL minimal satu buahSederetan NOL minimal satu buah diikuti sederetan SATU sebanyak satu buah atau lebihSederetan bit NOL dan SATU sembarang yang diawali dengan NOL dan diahiri dengan SATUSederetan SATU dengan jumlah GENAPSederetan NOL dengan jumlah GENAP diikuti sederetan SATU dengan jumlah GANJIL

*

Ekspresi RegularContoh:B. String apakah ekspresi-ekspresi regular berikut:Ekspresi : (1,0)*Ekspresi : (10)* Ekspresi : (0,1)*1*Ekspresi : (00)*(11)*Ekspresi : (11)*(00)**

Jawab:Contoh 1 a.Ekspresinya : 0*

Contoh 1 b.Sederetan bit NOL dan SATU dengan jumlah sembarang dan susunan sembarang*

*Tata Bahasa RegulerBahasa regular merupakan kelas bahasa yang dibangkitkan oleh tata bahasa regular.Tata bahasa ini memiliki aturan produksi dengan batasan: = HANYA terdiri dari 1 simbol Non terminal saja, atau N = dalam bentuk salah satu diantara: a,aB, atau

Tata Bahasa RegulerContoh:Tentukan bahasa yang dihasilkan oleh tata bahasa regular berikut:G{,N,S,P}; dimana ={a,b} N={A,B} danP={SaS; SaB; SA; Bb; BbB; B; Aa}*

Pengenal Bahasa RegularPengenal pada bahasa regular adalah mesin abstrak yang disebut dengan otomata berhingga (Finite State Automata, biasa disingkat FSA).Latihan:Tulislah notasi untuk ekspresi-ekspresi regular di bawah ini: a. sederetan a dengan panjang minimal 1b. sederetan ab dengan panjang nol*

Pengenal Bahasa RegularLatihan:2. Bagaimanakah mengungkapkan kalimat untuk ekspresi regular berikut:a. {a,b}c, {a*,b}e. {a*b*}b. {ab*}d. {a,b*}f. {a*,b*}3. Tentukan bahasa yang dihasilkan oleh tata bahasa regular berikut: G{,N,S,P}; dimana ={a,b} N={A,B} dan jika aturan produksi masing-masing bahasa adalah sbb:a. P={SaS; S}b. P={SaS; S; SB; BbB; B}c. P={SaS; SB; BbB; B}*

Pengenal Bahasa Regular4. Tentukan bahasa yang dihasilkan oleh tata bahasa regular berikut: G{,N,S,P}; dimana ={a,b,c} N={A,B,C} dan jika aturan produksi masing-masing bahasa adalah sbb:a. P={SaA; AaA; AbB; BbB; BcC; CcC; C}b. P={SaA; AaA; AbB; BbB; BcC; CcC; C; B}c. P={SaA; AbB; BcC; C}d. P={SaA; AbB; BcC; CcC; C}*