ILMU KOMPUTASI

STMIK AMIKOM

PURWOKERTO

Pertemuan 6

• Sifat-sifat Bahasa Regular

Pendahuluan

• Sifat-sifat penting dalam bahasa regular digunakan sebagai alat untuk membuktikan bahwa sebuah bahasa bukan regular.

• Alat dan sifat tersebut adalah pumping lemma dan sifat closure.

• Dengan sifat-sifat bahasa regular, dapat dibuat alat untuk mengenal bahasa-bahasa yang dikonstruksi dari bahasa-bahasa yang lain dengan menggunakan operasi tertentu.

– Sebagai contoh, irisan dari dua bahasa regular adalah regular.

– Dengan menggunakan automata yang mengenal dua bahasa yang berbeda, kita dapat membentuk sebuah automaton yang mengenali secara tepat irisan dari dua bahasa regular tersebut.

• Sifat closure dapat digunakan untuk membangun automata yang kompleks.

Membuktikan Bahasa Bukan Regular

• Perhatikan bahasa L01 = {0n1n | n 1}.

• Bahasa ini mengandung semua string 01, 0011,

000111, dan seterusnya.

• String tersebut terdiri dari satu atau lebih para 0

dan diikuti oleh jumlah yang sama dari para 1.

• Bahasa tersebut bukan bahasa regular.

• Jika L01 adalah bahasa regular maka akan ada

sebuah DFA A yang menerima bahasa tersebut.

Teorema 1: (Pumping lemma untuk

bahasa regular) Misalkan L adalah bahasa regular.

Maka terdapat sebuah konstanta n (yang tergantung pada L) sedemikian sehingga untuk setiap string w di dalam L sedemikian sehingga |w| n, kita dapat memecah w ke dalam tiga string, w = xyz, sedemikian sehingga:

y

|xy| n

Untuk semua k 0, string xykz juga di dalam L.

Bahwa kita selalu dapat menemukan string tak kosong y tidak begitu jauh dari awal w yang dapat di “pump”; bahwa pengulangan y beberapa kali, atau penghapusan y (dalam kasus k = 0), tetap menghasilkan string dalam bahasa L.

Contoh 1

• Dengan menggunakan Pumping lemma dapat

ditunjukkan bahwa bahasa berikut bukan bahasa

regular

– Leq yang mengandung semua string dengan

banyaknya para 0 dan para 1 adalah sama

(tidak dalam urutan tertentu).

– Lpr yang mengandung semua string dari para 1

yang memiliki panjang adalah bilangan prima.

Sifat-sifat Closure dari Bahasa Regular

1. Gabungan dari dua bahasa regular adalah regular

2. Irisan dari dua bahasa regular adalah regular

3. Komplemen dari sebuah bahasa regular adalah regular

4. Difference/beda dari dua bahasa regular adalah regular

5. Reversal dari sebuah bahasa regular adalah regular

6. Closure (star) dari sebuah bahasa regular adalah regular

7. Perangkaian dari bahasa-bahasa regular adalah regular

8. Sebuah homomorphism (substitusi dari string untuk simbol) dari sebuah bahasa regular adalah regular.

9. Inverse homomorphism dari sebuah bahasa regular adalah regular

Closure dari Bahasa Regular pada

Operasi-operasi Boolean (1)

• Sifat closure yang pertama adalah tiga operasi Boolean, yaitu gabungan, irisan dan komplemen: 1. Misalkan L dan M adalah bahasa pada alphabet .

Maka L M adalah bahasa yang mengandung semua string yang berada di L atau M, atau keduanya.

2. Misalkan L dan M adalah bahasa pada alphabet . Maka L M adalah bahasa yang mengandung semua string yang berada di L dan M.

3. Misalkan L adalah bahasa pada alphabet . Maka L’, komplemen dari L, adalah himpunan dari string-string dalam * yang tidak dalam L.

• Bahasa regular tertutup di bawah ketiga operasi Boolean tersebut.

Closure dari Bahasa Regular pada

Operasi-operasi Boolean (2)

• Gabungan dan irisan dari dua bahasa dapat diperoleh dari bahasa-bahasa dengan alphabet yang berbeda.

• Contoh, L1 {a, b} sedangkan L2 {a, b, c}.

• Tetapi, jika sebuah bahasa L terdiri dari string-string dengan simbol dalam , maka L dapat dipandang sebagai bahasa pada sejumlah berhingga alphabet yang merupakan powerset dari .

• Sehingga, kita dapat menyatakan L1 dan L2 sebagai bahasa pada aplhabet {a, b, c, d}.

Closure dari Bahasa Regular pada

Operasi-operasi Boolean (3)

• Komplemen dari bahasa L adalah sebuah subset dari * untuk alphabet 1,

• Kita dapat memilih untuk mengambil komplemen terhadap alphabet 2 yaitu sebuah superset dari 1.

• Jika demikian, maka komplemen L adalah 2* L, yaitu komplemen dari L terhadap 2 meliputi semua string di dalam 2* yang memiliki sedikitnya satu simbol yang ada dalam 2 tetapi tidak ada dalam 1.

a. Closure pada gabungan

Teorema 2:

Jika L dan M adalah bahasa regular, maka

demikian halnya dengan L M.

Bukti:

• Karena L dan M adalah regular, maka kedua

bahasa tersebut memiliki ekspresi regular;

katakanlah L = L(R) dan M = L(S).

• Maka L M = L(R + S) dengan menggunakan

definisi dari operator + untuk ekspresi regular.

b. Closure pada operasi komplemen (1)

• Berikut tahapan untuk menentukan ekspresi regular untuk komplemen dari bahasa yang diberikan:

1. Konversikan ekspresi regular ke dalam bentuk -NFA.

2. Konversikan -NFA ke sebuah DFA dengan menggunakan konstruksi subset.

3. Komplemenkan accepting state dari DFA tersebut.

4. Kembalikan komplemen dari DFA ke dalam bentuk ekspresi regular dengan menggunakan konstruksi yang telah dibahas sebelumnya.

b. Closure pada operasi komplemen (2)

Teorema 3:

• Jika L adalah bahasa regular pada alphabet , maka L’ = * L adalah juga bahasa regular.

Bukti:

• Misalkan L = L(A) untuk suatu DFA A = (Q, , , q0, F).

• Maka L’ = L(B), dimana B adalah DFA (Q, , , q0, Q F).

• Bahwa B seperti A, hanya saja accepting state dari A bukan accepting state dari B, dan sebaliknya.

• Maka w adalah dalam L(B) jika dan hanya jika adalah dalam Q F, yang muncul jika dan hanya jika w tidak di dalam L(A).

w,q0

Contoh 2

• Misalkan A adalah automata yang dinyatakan dalam diagram transisi di bawah ini.

• DFA tersebut menerima semua string dari para 0 dan pada 1 yang diakhiri dengan 01.

• Dalam bentuk ekspresi regular, bahasa yang diterima oleh DFA tersebut dinyatakan sebagai L = (0 + 1)*01.

Start

0q

20q,q

10q,q

1

1

1

0

0

0

Contoh 2 (lanjutan)

• Komplemen dari L(A) adalah semua string dari para 0 dan para 1 yang tidak diakhiri dengan 01. Gambar berikut menunjukkan automaton untuk {0, 1}* L(A).

• Gambar tersebut sama seperti diagram transisi untuk DFA , tetapi accepting state dijadikan bukan accepting state dan dua state yang bukan accepting state dijadikan accepting state.

Start

0q

20q,q

10q,q

1

1

1

0

0

0

c. Closure pada irisan

• Operasi irisan dari dua bahasa dapat diperoleh dari operasi gabungan dan komplemen (dikatakan sebagai hukum De Morgan).

L M = (L’ M’)’

• Hukum De Morgan yang lain adalah

L M = (L’ M’)’

• Konstruksi langsung dapat dilakukan untuk irisan dari dua bahasa. Konstruksi ini menjalankan dua DFA secara paralel.

Teorema 4:

• Jika L dan M adalah bahasa regular, maka demikian juga dengan L M.

Contoh 3

• DFA pada Gambar a menerima semua string yang memiliki sebuah 0,

• DFA pada Gambar b menerima semua string yang memiliki sebuah 1.

• DFA pada Gambar c adalah produk dari kedua DFA dalam gambar a dan b.

• State-state dari DFA pada gambar c diberi label oleh pasangan dari state-state dari automata dalam gambar a dan b.

p q

0,1

0

1

start

(a)

r s

0,1

1

0

start

(b)

pr ps

1

0

1start

qr qs

0,1

1

0

0

(c)

d. Closure pada beda

• Dalam istilah bahasa, L M, beda dari L dan M, adalah himpunan string-string yang ada dalam bahasa L tetapi tidak dalam bahasa M.

• Bahasa regular juga tertutup pada operasi beda himpunan.

Teorema 5:

• Jika L dan M adalah bahasa regular, maka demikian juga dengan L M.

Reversal (1)

• Reversal dari sebuah string a1a2...an adalah string

yang ditulis terbalik, bahwa, anan1...a1.

• Notasi wR digunakan untuk reversal dari string w.

Contoh: 0010R adalah 0100, dan R = .

• Reversal dari bahasa L, ditulis LR, adalah bahasa

yang terdiri dari reversal dari semua stringnya.

Contoh, jika L = {001, 10, 111},

maka LR = {100, 01, 111}.

Reversal (2)

Teorema 6:

• Jika L adalah bahasa regular, maka

demikian juga dengan LR.

• Pembuktian pernyataan ini dapat dilakukan

dengan dua cara: menggunakan automata

dan ekspresi regular.

Reversal (3)

• Diberikan sebuah bahasa L yaitu L(A) untuk suatu finite automaton, bisa berupa non determistik atau -transition, konstruksi automaton untuk LR dilakukan sebagai berikut:

– Reverse semua arc dalam diagram transisi untuk A.

– Buatlah start state dari A menjadi accepting state dari automaton yang baru.

– Buatlah start state yang baru p0 dengan transisi pada ke semua accepting state dari A.

• Hasilnya adalah sebuah automaton yang mensimulasi A “in reverse”

menerima sebuah string w jika dan hanya jika A menerima wR.

Contoh 4

• Misalkan L didefinisikan oleh ekspresi regular

(0 + 1)0*

• Maka LR adalah bahasa dari (0*)R(0 + 1)R, dengan

menggunakan aturan perangkaian.

• Jika aturan untuk closure dan gabungan digunakan

untuk dua bagian ini, dan kemudian digunakan

aturan basis yang menyatakan bahwa reversal dari

0 dan 1 adalah tetap, didapatkan bahwa LR

memiliki ekspresi regular 0*(0 + 1).

Homomorphism (1)

• Sebuah homomorphism string adalah sebuah fungsi pada string yang bekerja dengan mensubtitusikan sebuah string tertentu untuk setiap simbol.

Contoh 5:

• Fungsi h didefinisikan oleh h(0) = ab dan h(1) = adalah homomorphism.

• Diberikan string dari para 0 dan para 1, homomorphism mengganti semua para 0 oleh string ab dan menggantikan semua para 1 dengan string kosong.

• Sebagai contoh, h yang diaplikasikan ke string 0011 adalah abab.

Homomorphism (2)

• Jika h adalah sebuah homomorphism pada alphabet , dan w = a1a2... an adalah sebuah string dari simbol pada , maka

h(w) = h(a1)h(a2)... h(an).

h diaplikasikan ke setiap simbol dari w dan merangkai hasilnya, sesuai dengan urutan simbol-simbol pada w.

• Contoh, jika h adalah homomorphism dalam Contoh 5, dan w = 0011, maka

h(w) = h(0)h(0)h(1)h(1) = (ab)(ab)()() = abab.

Homomorphism (3)

• Homomorphism dapat diaplikasikan ke sebuah bahasa dengan mengaplikasikannya ke setiap string dalam bahasa.

Bahwa, jika L adalah bahasa pada alphabet , dan h adalah homomorphism pada , maka

h(L) = {h(w) | w adalah dalam L}.

• Contoh: jika L adalah bahasa dari ekspresi regular 10*1, yaitu sejumlah para 0 yang dilingkupi oleh satu buah simbol 1, maka h(L) adalah bahasa (ab)*.

• Homomorphism h pada Contoh 5 menggantikan para 1 dengan , dan menggantikan 0 dengan ab.

Homomorphism (4)

Teorema 7:

• Jika L adalah bahasa reguler pada alphabet

, dan h adalah homomorphism pada ,

maka h(L) juga regular.

Bukti: dapat dilihat pada buku rujukan

Daftar Pustaka

• John E. Hopcroft, Rajeev Motwani, Jeffrey D.

Ullman. 2001. Introduction to Automata

Theory, Languange, and Computation. Edisi

ke-2. Addison-Wesley.