my tugas

NAMA      :ANDI BAHARUDDIN

NIM          :H11111251

TUGAS ILMU KOMPUTASI

Regular expression adalah cara untuk mengekspresikan bahasa dengan hanya menggunakan operasi :

§  Concatenation : Penyambungan dilakukan pada 2 karakter atau lebih membentuk 1 barisan karakter (string simbol).
Contoh :
'a' o 'b' = 'ab'
'ab' o 'baab' = 'abbaab'

§  Superscript : Penyambungan dapat dianggap sebagai perkalian karena biasanya penulisannya adalah bila x dan y string, maka x o y adalah xy. sehingga pemangkatan dapat digunakan
VoV = VV = V² ----> Panjang string = 2

§  Kleene closure : string pada V, termasuk string kosong dimana ε string kosong (string tanpa simbol) ε mempunyai sifat identitas, yaitu:
ε o x = x
x o ε = x

§  Positif closure : himpunan string pada V, tidak ada string kosong didalamnya.

Definisi Ekspresi Regular :

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.

Contoh:

1. Ekspresi : (1,0)*

2. Ekspresi : (10)*

3. Ekspresi : (0,1)*1*

4. Ekspresi : (00)*(11)*

5. Ekspresi : (11)* (00)*

Aturan Ekspresi Reguler :

- Simbol pada Sebelah kiri harus berupa sebuah simbol variabel

- Simbol pada sebelah kanan maksimal hanya memiliki sebuah simbol variabel dan bila

ada terletak di posisi paling kanan

contoh Bahasa Reguler :

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

Tentukan bahasa reguler yang dibentuk oleh r=(aa*)(bb)*b

Jawab

L(r)      = L( (aa)* (bb)*b )

= { a2n b2m+1 | n,m ≥ 0 }

 

 

 

 

Ekuivalensi AHN, AHD, dan GR

AHD bisa dibentuk dari AHN.                                  AHN

GR bisa dibentuk dari AHD.                         

AHN bisa dibentuk dari GR.                          AHD                 GR

Ekuivalensi Ahn-e Dengan ER (Ekspresi Regular)

Jenis ER	Simbol ER	AHN
Simbol hampa	e	q
ER hampa	f atau {}	q                                         q
ER umum	r	r                   q                                         q
Alternation	r| r	e           r        e                                                   q       e                   e         q                                     r
Concatenation	rr	e                        e                       e       q               r                      r                 q
Kleene Clossure	r *	e                      e                                e       q                           r                             q                                        e