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.


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


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)


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.


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.


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 ∅ ∅


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.


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.


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.


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.


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)


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.


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


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).


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


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


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)).


ǫ-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.


Buat Apa?

Alat deskripsi yang berguna (spesifikasi),

Berguna untuk komposisi dan penggabungan NFA,

Dapat dikonversikan ke DFA dan diimplementasikan.


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

ǫ

ǫ


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 ∅ ∅ ∅


ǫ-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).


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}.


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.


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.


Ekspresi Reguler paling Sederhana

R L(R)

ǫ {ǫ}∅ {}

∀a ∈ Σ {a}


Union

Jika R dan S adalah ekspresi reguler

maka R + S adalah ekspresi reguler

di mana

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


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}.


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 ∪ · · ·


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}.


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(ǫ) = {ǫ}.


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∗)∗.


Urutan Evaluasi Operator

Tertinggi ∗

·

Terendah +

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


Hukum-Hukum

Associative:

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

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

Distributive:

(R+S)T=RS+RT,


Bahasa Sebuah Ekspresi Reguler

Bahasa yang dibangkitkan oleh Ekspresi Reguler (ER) disebut

dengan bahasa reguler (regular languages).


tk slides01

Documents