Teori Bahasa dan Automata - RE

RE (Regular Expression): Ekspresi sederhana untuk language yang diterima FA (Finite Automata)
Untuk setiap regular expression E, bahasa yang direpresentasikan dinotasikan dengan L(E)

 Basis:

- Konstanta Epsilon dan merupakan RE yang menunjukkan Empty Set

- Jika a adalah simbol dan a adalah RE. notasi ini menunjukkan language {a}, atau L(a)={a}.

- Variabel dengan huruf kapital merepresentasikan language

Induksi :

– Jika E dan F adalah RE, dan E + F adalah RE yang merepresentasikan union L(E) dan L(F). Atau L(E+F) = L(E) U L(F)

– Jika E dan F adalah RE, dan EF adalah RE yang merepresentasikan concatenation L(E) dan L(F). Atau L(EF) = L(E) L(F)

– Jika E adalah RE, dan E* adalah RE yang merepresentasikan closure dari L(E). Atau L(E*) = (L(E))*

Sifat-Sifat Regular Expression:

Contoh: (keterangan: ^+ = pangkat + atau positive closure)
- 00 = RE untuk {00}
- (0+1)* = RE untuk himpunan string yang terdiri dari 0 dan 1
- (0+1)*00(0+1)* = meliputi (epsilon)00(epsilon), 10010, 010011, ...
- (1+10)* = meliputi 1, 1010, 110, ...
- (0|1)*011 = meliputi 0011, 1011, 01011, ...
- (aa|ab|ba|bb)* = meliputi aa, aaab, aabb, ...
- (a|b)(a|b)(a|b)(a|b)* = meliputi aaaa, aaab, abbab, ...
- (aa|ab|ba|bb)^+ a = meliputi aaa, ababa, bbaaa, ...

LATIHAN!
Buat RE untuk:
1. Himpunan string dari alphabet {0, 1} yang diakhiri dengan 01
2. Himpunan string dari alphabet {a, b} yang diawali dengan abb
3. Himpunan string dari alphabet {0, 1} yang mengandung string 001
4. Himpunan string dari alphabet {a, b} yang diakhiri dengan b dan mempunyai panjang ganjil
5. Himpunan string dari alphabet {0, 1} yang diawali dan/atau diakhiri 01
6. Himpunan string dari alphabet {0, 1} yang simbol ketiga dari kanan merupakan angka 1
7. Himpunan string dari alphabet {a, b, c} yang mengandung sedikitnya satu buah a dan b

(Jawaban ada di akhir post Teori Bahasa dan Automata - Finite Automata)