TEORI BAHASA DAN OTOMATA - … · Ekspresi Regular (1) Sebuah bahasa dinyatakan regular jika terdapat finite state automata yang dapat menerimanya. Bahasa-bahasa yang diterima oleh

TEORI BAHASA DAN OTOMATA

[TBO]

Ekspresi Regular (1) Sebuah bahasa dinyatakan regular jikaterdapat finite state automata yang dapatmenerimanya.

Bahasa-bahasa yang diterima oleh suatu finitestate automata bisa dinyatakan secarasederhana dengan ekspresi regular (regularexpression).

Ekspresi regular selanjutnya disebut sebagaiER, memungkinkan menspesifikasikan ataumendefinisikan bahasa-bahasa.

Ekspresi Regular (2) Ekspresi regular memberikan suatu pola(pattern) atau template untuk untai/stringdari suatu bahasa.

Untai yang menyusun suatu bahasa regularakan cocok (match) dengan pola bahasa itu.

Banyak masalah pada perancangan perangkatlunak yang bisa disederhanakan denganmelakukan pengubahan notasi ekspresiregular ke dalam implementasi komputer darifinite state automata yang bersangkutan.

Ekspresi Regular (3) Penerapan ekspresi regular yang tampakmisalnya pencarian (searching) untai karakter(string) pada suatu file, biasanya fasilitas iniada pada text editor. Dalam kasus itu dilakukanpenerapan finite state automata pada untai-untai yang terdapat dalam file tersebut.

Contoh penerapan yang lain adalah pembatasandata masukan yang diperkenankan, misalnyasuatu field masukan hanya menerima inputbilangan (0..9)

FSA yang menerima bilangan integer tak bertanda Bila dalam bahasa Indonesia bisa dikatakanbahwa otomata pada gambar menerima masukansymbol input antara 0 sampai 9 sedang ekspresiregularnya dinyatakan sebagai berikut:

(digit)digit)*

Penerapan Ekspresi Regular (1) Dalam suatu kompilator, ekspresi regular bisadiaplikasikan untuk melakukan analisis leksikal,yaitu mengidentifikasikan unit-unit leksikal yangdikenal dalam program.

Unit leksikal ini biasanya disebut dengan token. Token-token pada suatu bahasa pemrogramankebanyakan tanpa kecuali dinyatakan sebagaiekspresi regular.

Misalkan suatu identifier baik huruf besar atauhuruf kecil yang kemudian diikuti huruf ataudigit, dengan tanpa pembatasan jumlah panjangbisa dinyatakan sebagai:

(huruf)(huruf+digit)*

Penerapan Ekspresi Regular (2) Contoh otomata pada gambar 2 bergunamengenali identifier, bila huruf A..Z, a..z, dandigit berupa 0..9.

Bila dalam bahasa FORTRAN dibatasi panjangidentifier maksimal 6 (enam), maka ekspresiregular untuk identifier pada FORTRAN bisadinyatakan sebagai:

(huruf)(huruf+digit)5

Dalam implementasinya suatu finite stateautomata akan diterjemahkan menjadi kodedalam sebuah bahasa pemrograman.

FSA mengenali identifier Gambar 2

Notasi Ekspresi Regular * (karakter asterisk), berarti bisa tidak muncul,bisa juga muncul berhingga kali (0-n)

+ (pada posisi superscript/diatas) berartiminimal muncul satu kali (1-n)

+ atau berarti union

. (titik) berarti konkatensi, biasanya titik bisadihilangkan, misal ab bermakna seperti a.b

Contoh ekspresi regular (1) ER: ab*cc

contoh string yang dibangkitkan : abcc,abbcc, abbbcc, abbbbcc, acc (b bisatidak muncul atau muncul sejumlahberhingga kali)

ER: 010*

contoh string yang dibangkitkan : 01,010, 0100, 01000

(jumlah 0 diujung bisa tidak muncul,bisa muncul berhingga kali)

Contoh ekspresi regular (2) ER: a*d

contoh string yang dibangkitkan : d, ad, aad,aaad

ER: a+d

contoh string yang dibangkitkan: ad, aad,aaad (a minimal muncul sekali)

ER: a*b*(ingat ‘’ berarti atau)

contoh string yang dibangkitkan: a, b, aa, bb,aaa, bbb, aaaa, bbbb

ER: (ab)

contoh string yang dibangkitkan: a, b

Contoh ekspresi regular (3) ER: (ab)*

contoh string yang dibangkitkan: a, b, ab, ba,abb, bba, aaaa, bbbb (untai yang memuat aatau b)

* perhatikan : notasi ‘’ kadang dituliskanjuga sebagai ‘+’

ER: 01*+0

contoh string yang dibangkitkan: 0, 01, 011,0111, 01111, (string yang berawalan dengan0, dan selanjutnya boleh diikuti deretan 1)

Hubungan ER dan FSA Untuk setiap ekspresi regular ada satu Non-deterministic Finite Automata dengan transisi (NFA -move) yang ekivalen.

Sementara untuk Deterministic FiniteAutomata ada satu ekspresi regular daribahasa yang diterima oleh DeterministicFinite Automata.

Sederhananya kita bisa membuat suatu Non-deterministic Finite Automata -move darisuatu ekspresi regular.

Bisa dilihat contohnya pada gambar 3-5. Yangperlu diperhatikan disitu, state akhir akanmenandakan apakah suatu input diterimaatau tidak.

NFA -move untuk ER: ab Gambar 3

NFA -move untuk ER: a*b

Gambar 4

NFA -move untuk ER: a b

Kemudian dari Non-deterministic Finite Automata -move tersebut dapat kita ubah ke Non-deterministicFinite Automata dan selanjutnya ke DeterministicFinite Automata, atau prosesnya sebagai berikut:

NFA -move NFA DFA

Gambar 5

HUBUNGAN ANTARADFA, NFA, DAN ER

Hubungan antara Non-deterministicFinite Automata, Deterministic FiniteAutomata, dan ekspresi regular bisadigambarkan seperti gambar berikut ini.

NFA

DFA

EkspresiRegular

NFA -move

CONTOH 1 Membuat mesin Deterministic Finite Automatayang menerima bahasa yang berupa semuastring yang berakhiran dengan ‘00’. Diketahui, = (0,1)

Pertama buat ekspresi regularnya:

(0+1)*00 atau (0 1)*00

Dari ekspresi regular tersebut lebih mudahmembuat Non-deterministic Finite Automata,lebih dahulu, dari pada langsung DeterministicFinite Automata

CONTOH 2 Membuat mesin Deterministic Finite Automatayang menerima bahasa berupa semua stringyang memuat minimal dua nol berturutan(‘00’). Diketahui = (0,1)

Perhatikan perbedaannya dengan soalsebelumnya. Disini tidak ditentukan letak ‘00’.Buat ekspresi regularnya:

(0+1)*00(0+1)*

CONTOH 3 Membuat mesin Deterministic Finite Automatayang menerima bahasa berupa semua stringdimana symbol ketiga dari kanan adalah ‘1’.Diketahui = (0,1)

Buat ekspresi regularnya:

(0+1)*1(0+1)(0+1)

CONTOH 4 Membuat mesin Deterministic Finite Automatayang menerima bahasa yang berupa 4(empat) symbol yang minimal memuat 2(dua) buah ‘0’ (yang tidak perlu berturutan).Diketahui = (0,1)

Disini agak kesulitan membuat ekspresiregular dari permasalahan tersebut.

Maka coba langsung mengkonstruksiDeterministic Finite Automata-nya denganjalan melihat semua kemungkinan yang ada.

CONTOH 4 Lanjt.. Kemungkinan pertama adalah dua buah nolterletak di paling ujung

Kemungkinan kedua adalah dua buah nolterletak di paling awal

Kemungkinan untuk tiga symbol pertamasudah memuat dua buah nol

Kemungkinan bila tiga symbol pertama baru

memuat satu buah nol

LATIHANBuatlah FSA (DFA, NFA, NFA -Move)dari ER berikut ini:

010*

0(10)

0(10)*

01*0

0*10*

a(ba)*

(ab)*

01*10*11*

a(ba*a(ba*b)*)

a(ba)*ab*(abab*)*