tk slides01

Teori Komputasi

Reza Pulungan

Jurusan Ilmu KomputerUniversitas Gadjah Mada

Yogyakarta

March 1, 2010

NON-DETERMINISME

Deterministic FA (DFA)

Semua FA yang telah kita lihat sampai sekarang adalah DFA.

Catatan Penting!

δ(q, a) unik; setiap state q memiliki satu (dan hanya satu)

transisi keluar untuk setiap simbol a ∈ Σ.

Untuk setiap string input tertentu w , eksekusi benar-benar

dapat diprediksi dan dapat diulangi. Oleh karena itu hasil dari

eksekusi yang sama mesti sama. Sifat ini disebut dengan

determinisme.

Reza Pulungan Teori Komputasi 3

Non-Deterministic FA (NFA)

δ(q, a) adalah himpunan state-state:

bisa jadi himpunan kosong, atau

lebih dari satu state.

Dengan demikian, q bisa memiliki beberapa (atau tidak ada

sama sekali) transisi keluar untuk setiap a ∈ Σ.

NFA dapat “menebak” langkah yang tepat, tanpa harus

ditentukan (di dalam struktur NFA itu) terlebih dahulu. Tebakan

ini muncul karena adanya beberapa pilihan. Sifat ini disebut

dengan non-determinisme.

Reza Pulungan Teori Komputasi 4

Contoh NFA

L = {w ∈ {0, 1}∗ | w berakhir dengan 01}

Ide: Di suatu state NFA “menebak” bahwa akhir dari input

sudah akan dimulai dan oleh karena itu NFA kemudian

menunggu 01, dengan menggunakan non-determinisme.

q0

Startq1 q2

0 1

0, 1

Reza Pulungan Teori Komputasi 5

Pohon Eksekusi

Non-determinisme berarti trace eksekusi tidak unik (seperti

halnya pada DFA). Non-determinisme menghasilkan pohon

trace eksekusi yang mungkin.

Contoh (untuk string input w = 0010)

Contoh (untuk string input w = 0001)

Reza Pulungan Teori Komputasi 6

Non-Deterministic FA (NFA)

Menerima: jika terdapat paling sedikit satu path yang berakhir

di state Final di pohon trace eksekusi.

Menolak: jika semua path yang mungkin “terhenti” (stuck, halt)

atau berakhir di state yang bukan Final.

Interpretasi:

1 NFA selalu mengambil pilihan yang benar untuk

memastikan penerimaan (asumsi: path yang berakhir di

state Final memang ada),

2 NFA membuat copy dirinya sendiri untuk menelusuri

semua path yang mungkin,

3 NFA menjelajahi semua path secara parallel.

Reza Pulungan Teori Komputasi 7

Penting!

Semua NFA dengan bahasa L harus memastikan:

∀x /∈ L: semua path yang mungkin di pohon trace eksekusi

menolak,

∀x ∈ L: paling sedikit satu path di pohon trace eksekusi

menerima.

Meskipun NFA bebas “menebak”, NFA harus memastikan

bahwa salah satu dari tebakannya benar. Caranya adalah

dengan menebak semua tebakan yang mungkin.

Reza Pulungan Teori Komputasi 8

Secara Formal

NFA N = (Q,Σ, δ, q0, F ) memiliki struktur yang sama dengan

DFA kecuali untuk fungsi transisi δ.

δ : Q × Σ → 2Q (Ingat: 2Q adalah powerset dari Q)

=⇒ δ(q, a) adalah himpunan bagian dari Q.

Tabel transisi contoh sebelumnya:

δ 0 1

q0 {q0, q1} {q0}q1 ∅ {q2}q2 ∅ ∅

Reza Pulungan Teori Komputasi 9

Extended Transition Function

δ̂(q, w ): himpunan state-state yang dapat dicapai dari q pada

string input w .

Contoh

δ̂(q0, 001) = {q0, q2} dan δ̂(q0, 000) = {q0, q1}.

Definisi (Induktif)

∀q ∈ Q,∀a ∈ Σ,∀x ∈ Σ∗:

Basis: δ̂(q, ǫ) = {q},

Induksi: δ̂(q, x) = {p1, p2, · · · , pk}, (asumsi)

δ(pi , a) = Si , (∀1 ≤ i ≤ k ), (asumsi)

δ̂(q, xa) = S1 ∪ S2 ∪ · · · ∪ Sk . (implikasi)

Catatan Penting!

δ̂(q, xa) =⋃

pi∈δ̂(q,x)

δ(pi , a)

. Reza Pulungan Teori Komputasi 10

Contoh

δ̂(q0, 0) = δ(q0, 0) = {q0, q1}.

δ̂(q0, 00) =⋃

pi∈δ̂(q0,0)

= δ(q0, 0) ∪ δ(q1, 0),

= {q0, q1} ∪ ∅,

= {q0, q1}.

δ̂(q0, 001) =⋃

pi∈δ̂(q0,00)

= δ(q0, 0) ∪ δ(q1, 1),

= {q0} ∪ {q2},

= {q0, q2}.

Observasi: δ̂(q0, 001) berisi state Final q2. Dengan demikian

string input 001 diterima.

Reza Pulungan Teori Komputasi 11

Bahasa Sebuah NFA

Diberikan: NFA N = (Q,Σ, δ, q0, F )

Definisi

L(N) = {w ∈ Σ∗ | δ̂(q0, w ) ∩ F 6= ∅}

Pastikan bahwa definisi ini konsisten dengan penjelasan dan

tiga interpretasi sebelumnya.

Reza Pulungan Teori Komputasi 12

Contoh NFA

Bahasa L123 ⊂ {1, 2, 3}∗: semua string w ∈ {1, 2, 3}∗ di mana

simbol terakhir di w telah muncul sebelumnya, dan di antara

kedua simbol tersebut tidak ada simbol dengan nilai lebih besar.

Contoh: · · · 11, · · · 2112, · · · 3121213.

pStart

q

r

s

t

1

2

3

1

2

3

1, 2, 3 1

1, 2

di p: belum menebak,

di s: menebak simbol

terakhir adalah 3 dan baru

saja menerima 3;

menunggu dan

memastikan bahwa semua

simbol perantara lebih kecil

dari 3,

di r dan q: mirip dengan s,

di t : menerima.

Reza Pulungan Teori Komputasi 13

Contoh NFA

Tabel Transisiδ 1 2 3

p {p, q} {p, r} {p, s}q {t} ∅ ∅r {r} {t} ∅s {s} {s} {t}t ∅ ∅ ∅

Contoh (w=31213)

3121 /∈ L123.

Reza Pulungan Teori Komputasi 14

DFA vs. NFA

Perbandingan Power DFA & NFA

Power? Kemampuan untuk menerima bahasa.

Observasi: DFA adalah kasus khusus NFA dengan

|δ(q, a)| = 1,∀q ∈ Q,∀a ∈ Σ.

=⇒ Power(DFA) ≤ Power(NFA)

Teorema

Untuk setiap NFA terdapat DFA yang menerima bahasa yang

sama.

=⇒ Power(NFA) ≤ Power(DFA)

Kesimpulan: Power(NFA) = Power(DFA)

Reza Pulungan Teori Komputasi 16

Kenapa Peduli dengan NFA?

DFA dapat diimplementasikan dengan mudah dalam

komputer,

NFA lebih mudah dibangun, dimengerti dan dibuat

spesifikasinya.

Dengan demikian, kita menggunakan NFA untuk

mengungkapkan pola dalam string processor (grep atau lexical

analyzer), dan kemudian mengubahnya ke DFA untuk

menemukan pola tersebut.

Reza Pulungan Teori Komputasi 17

Ide Pembuktian

Teorema

Untuk setiap NFA N, terdapat sebuah DFA A s.s. L(A) = L(N).

Ide: Diberikan NFA N , DFA A akan mensimulasikan seluruh

pohon eksekusi N dalam satu eksekusi.

Contoh

q0

q1

q1

q0

q0

q0

q0

q1

q2

terhenti terhenti

0 0 0 1

diterima

q1

q0

},{q0

q1

q0

},{ q1

q0

},{ q2

q0

},{

NFA

DFA

Reza Pulungan Teori Komputasi 18

Bukti Formal (Subset Construction)

Diberikan: N = (QN ,Σ, δN , q0, FN ),Bangun: A = (QA,Σ, δA, {q0}, FA),sedemikian sehingga:

QA = 2QN (semua subset dari QN ),

FA = {S ⊆ QN | S ∩ FN 6= ∅},

dan untuk setiap state baru S:

δA(S, a) =⋃

pi∈S

δN (pi , a).

(δA(S, a) adalah himpunan semua state di N yang dapat

dicapai dari semua state pi ∈ S pada input a).

Reza Pulungan Teori Komputasi 19

Contoh

NFA N :q0

Startq1 q2

0 1

0, 1

DFA A:

q1

q0

},{q0}{

q1

q0

},{ q2,

q2

q0

},{

q1}{ q

2}{

}{ q2

q1

},{

1

0

1

0

101

0

0,1

0

1

0,11

0

Start

Reza Pulungan Teori Komputasi 20

Contoh

Semua state yang tidak bisa dicapai dari state Start dapat

dihilangkan karena tidak esensial untuk perilaku DFA yang

diperoleh.

DFA yang disederhanakan:

p0

Startp1 p2

1

0

0

1

0

1

Reza Pulungan Teori Komputasi 21

Lanjutan Bukti

Lemma

∀q ∈ QN ,∀w ∈ Σ∗, δ̂A({q}, w ) = δ̂N (q, w ).

Latihan: Buktikan lemma ini dengan induksi pada panjang

string w .

L(A) = {w ∈ Σ∗ | δ̂A({q0}, w ) ∈ FA},

= {w ∈ Σ∗ | δ̂A({q0}, w ) ∩ FN 6= ∅}

(dari definisi FA),

= {w ∈ Σ∗ | δ̂N (q0, w ) ∩ FN 6= ∅}

(dari lemma di atas),

= L(N)

(dari definisi L(N)).

Reza Pulungan Teori Komputasi 22

ǫ-NFA

ǫ-NFA?

Menambahkan fitur non-determinisme tidak mengubah

power DFA,

Sekarang kita menambahkan fiture yang disebut dengan

ǫ-move:

p0 p1ǫ

yaitu, sebuah transisi tanpa “mengkonsumsi” simbol input.

ǫ-NFA sama dengan NFA, kecuali dalam hal

memperbolehkan ǫ-move.

Reza Pulungan Teori Komputasi 24

Buat Apa?

Alat deskripsi yang berguna (spesifikasi),

Berguna untuk komposisi dan penggabungan NFA,

Dapat dikonversikan ke DFA dan diimplementasikan.

Reza Pulungan Teori Komputasi 25

Contoh

Dua NFA dengan bahasa L1 = {w | w berakhir dengan 01}dan L2 = {w | w berakhir dengan 10}:

q0

Startq1 q2

0 1

0, 1

p0

Startp1 p2

1 0

0, 1

NFA yang mengungkapkan gabungan bahasa L1 dan L2

(L = {w | w berakhir dengan 01 atau 10}:

r0

Start

q0 q1 q2

p0 p1 p2

r1

ǫ

ǫ

0 1

0, 1

1 0

0, 1

ǫ

ǫ

Reza Pulungan Teori Komputasi 26

Secara Formal

ǫ-NFA N = (Q,Σ, δ, q0, F )memiliki struktur yang sama dengan NFA kecuali untuk δ.

δ : Q × (Σ ∪ {ǫ}) → 2Q

Contoh: δ(q0, ǫ) = {q1, q2, q3}.

Tabel transisi contoh sebelumnya:

δ 0 1 ǫ

· · · · · · · · · · · ·q2 ∅ ∅ {r1}p2 ∅ ∅ {r1}r0 ∅ ∅ {q0, p0}r1 ∅ ∅ ∅

Reza Pulungan Teori Komputasi 27

ǫ-Closure

Untuk setiap q ∈ Q, ECLOSE (q) adalah himpunan dari semua

state yang dapat dicapai dari q dengan menggunakan

sembarang barisan ǫ-moves, termasuk barisan kosong.

Catatan: q ∈ ECLOSE (q).

Contoh:

q0

Startq1 q2 q3

ǫ

0

1

ǫ

1

ǫ

ECLOSE (q0) = {q0, q1, q3},

ECLOSE (q1) = {q1, q3}

ECLOSE ({p1, · · · , pn}) =⋃

1≤i≤n

ECLOSE (pi).

Reza Pulungan Teori Komputasi 28

Extended Transition Function

Definisi (Induktif)

∀q ∈ Q,∀a ∈ Σ,∀x ∈ Σ∗:

Basis: δ̂(q, ǫ) = ECLOSE (q),

Induksi:

δ̂(q, xa) = ECLOSE

⋃

pi∈δ̂(q,x)

δ(pi , a)

,

=⋃

pi∈δ̂(q,x)

ECLOSE (δ(pi , a)).

δ̂(q, x) adalah himpunan dari semua state yang dapat dicapai

dari q di sepanjang semua path dengan transisi-transisi yang

menghasilkan x dengan mengabaikan semua ǫ-moves.Reza Pulungan Teori Komputasi 29

Penting!

q ∈ δ̂(q, ǫ)

δ̂(q, a) 6= δ(q, a) (Ini berbeda dengan DFA dan NFA.)

δ̂(q, a) = ECLOSE (δ(ECLOSE (q), q))

Contoh:

δ̂(q0, ǫ) = {q0, q1, q3},

δ(q0, ǫ) = {q1},

δ̂(q0, 0) = {q1, q3}.

Reza Pulungan Teori Komputasi 30

Bahasa Sebuah ǫ-NFA

Diberikan ǫ-NFA: N = (Q,Σ, δ, q0, F )

L(N) = {w ∈ Σ∗ | δ̂(q0, w ) ∩ F 6= ∅}

Yang membedakan ǫ-NFA dengan NFA adalah cara kita

mendefinisikan Extended Transition Function.

Reza Pulungan Teori Komputasi 31

Regular Language

(Bahasa Reguler)

Ekspresi Reguler

Notasi aljabar untuk mendefinisikan bahasa

(deklaratif)—dibandingkan dengan bahasa komputasional

dengan mesin.

Aljabar? Tentukan alfabet Σ:

Operand: ǫ, ∅, dan sembarang a ∈ Σ,

Operator:

+ penggabungan atau union,

· penyambungan atau concatenation,∗ closure.

Notasi: Untuk ekspresi reguler R yang dibangun dengan

aljabar di atas, L(R) adalah bahasa yang didefinisikan oleh R.

Reza Pulungan Teori Komputasi 33

Ekspresi Reguler paling Sederhana

R L(R)

ǫ {ǫ}∅ {}

∀a ∈ Σ {a}

Reza Pulungan Teori Komputasi 34

Union

Jika R dan S adalah ekspresi reguler

maka R + S adalah ekspresi reguler

di mana

L(R + S) = L(R) ∪ L(S).

Reza Pulungan Teori Komputasi 35

Concatenation

Jika R dan S adalah ekspresi reguler

maka R · S adalah ekspresi reguler

di mana

L(R · S) = L(R) · L(S).

Untuk bahasa L1 dan L2:

L1 · L2 = {w = xy | x ∈ L1, y ∈ L2}.

Contoh:

R = ǫ + 1 =⇒ L(R) = {ǫ, 1},

S = ǫ + 0 + 1 =⇒ L(S) = {ǫ, 0, 1},

T = R · S =⇒ L(T ) = {ǫ, 0, 1, 10, 11}.

Reza Pulungan Teori Komputasi 36

Perpangkatan Bahasa

L0 = {ǫ},

L1 = L,

L2 = L · L,

L3 = L · L · L,

...

Lk = {w = x1x2 · · · xk | ∀i , xi ∈ L}.

Definisi (Closure)

L∗ = L0 ∪ L1 ∪ L2 ∪ · · ·

Reza Pulungan Teori Komputasi 37

Closure

Jika R adalah ekspresi reguler

maka R∗ adalah ekspresi reguler

di mana

L(R∗) = L(R)∗,

= L(ǫ) ∪ L(R1) ∪ L(R2) ∪ · · · ,

= L(ǫ) ∪ L(R)1 ∪ L(R)2 ∪ · · · .

Contoh:

R = 0 + 1 =⇒ L(R) = {0, 1},

S = R∗ =⇒ L(S) = {Semua string biner},

R = 00 =⇒ L(R∗) = {Semua string 0 berpanjang genap}.

Reza Pulungan Teori Komputasi 38

Closure Positif

L+ = L1 ∪ L2 ∪ L3 ∪ · · · ,

L(R+) = L(R) ∪ L(R)2 ∪ L(R)3 ∪ · · · ,

Catatan Penting!

R+ = R · R∗ = R∗ · R,

R∗ = ǫ + R+,

L(ǫ∗) = L(ǫ) = {ǫ},

L(∅∗) = L(ǫ) = {ǫ}.

Reza Pulungan Teori Komputasi 39

Closure Positif

Contoh

L(a∗b∗) = L(a∗) · L(b∗),

= {ǫ, a, b, aa, ab, bb, aaa, aab, · · · },

= {Semua string di mana a mendahului b}.

Observasi: (a + b)∗ 6= a∗ · b∗, namun (a + b)∗ 6= (a∗ · b∗)∗.

Reza Pulungan Teori Komputasi 40

Urutan Evaluasi Operator

Tertinggi ∗

·

Terendah +

Contoh: R + S · T ∗ = R + (S · (T ∗)).

Reza Pulungan Teori Komputasi 41

Hukum-Hukum

Associative:

(RS)T=R(ST)=RST,

(R+S)+T=R+(S+T)=R+S+T.

Distributive:

(R+S)T=RS+RT,

Reza Pulungan Teori Komputasi 42

Bahasa Sebuah Ekspresi Reguler

Bahasa yang dibangkitkan oleh Ekspresi Reguler (ER) disebut

dengan bahasa reguler (regular languages).

Reza Pulungan Teori Komputasi 43