teori komputasi

72

Upload: sidiq-dwi-laksana

Post on 13-Aug-2015

161 views

Category:

Documents


22 download

DESCRIPTION

Teori Komputasi

TRANSCRIPT

Page 1: Teori Komputasi
Page 2: Teori Komputasi

Dokumen ini merupakan bagian pertama Kuliah Teori Komputasi (MAT40414 – 3).

Dokumen ini hanya sebagai penunjang pelaksanaan perkuliahan.

Untuk memahami materi kuliah, Anda wajib membaca :

1.Diktat Kuliah

2.Hand-out (berisi materi yang tidak ada dalam diktat)

3.Buku Acuan yang digunakan

Page 3: Teori Komputasi

Bagian pertama

1. Pendahuluan2. Mesin Keadaan Hingga3. Pengantar Bahasa Alami dan Bahasa Formal4. Automata Hingga

Page 4: Teori Komputasi

1. Pendahuluan

2 x (3 + 4) = 14 à dengan bantuan kalkulator

Mudah !

Bagaimana dgn :

a + b = ?

a x (b + c) = ?

Dapatkah digunakan kalkulator ?

Tergantung nilai a, b, c

a = 2, b = 2, c = 4, hasil s.d.a

Bagaimana untuk nilai a, b, c yg lain?

Page 5: Teori Komputasi

Urutan langkah1. Masukan nilai A, B, C2. Hitung (kalkulasi) X = B+C3. Hitung Y = A x X4. Tulis (keluarkan isi) Y5. Jika masih diperlukan nilai A, B, C yg

lain, kembali ke 1.Jika tidak, selesai

Oh, oh, ……

Itu kan algoritma ya ??

Page 6: Teori Komputasi

Kalkulator (mekanik) : Mesin Fisik (nyata)Urutan langkah (algoritma) dpt dianggap sebagai

MESIN ABSTRAK

Lantas, siapa yg menjalankan algoritma ?

Kalau mudah, ya manusia.Tapi kalo rumit dan panjang bagaimana ?

Yaa, mesin fisik juga tapi yg mempunyai kemampuan untuk mengerti urutan perintah dalam algoritma

Ah, ah, … itu kan KOMPUTER

Oh, jadi dlm KOMPUTER ada mesin abstrak juga agar mampu mengerti urutan perintah

Oh ……makanya namanya KOMPUTER (i.e yg melakukan komputasi)

Page 7: Teori Komputasi

Kalkulasi - Komputasi

Kalkulasi ?

Komputasi ?

Harga satuan suatu barang : Rp1000

Jika pembeli beli 3 buah, maka denganuang Rp.5000, penjual mengembalikan :

à 5000 – 3(1000) = 2000 (rupiah)

A : banyaknya barang yg dibeli

B : Banyaknya pembelian = 1000 x A

U : uang kembalian = 5000 – B

àHitung dulu B, kemudian

hitung 5000 - B

Bedanya ?

Page 8: Teori Komputasi

Oh, oh, oh, …kalo gitu sekarang, aku sudah tahu beda makna kalkulasi dan komputasi

Page 9: Teori Komputasi

Kalkulasi : proses melakukanperhitungan

Komputasi: proses menjalankan urutan

langkah-langkah

dlm penyelesaian masalah

dlm penyelesaian masalah

Urutan langkah-langkah (?)

ß ALGORITMA

Page 10: Teori Komputasi

Pada contoh : yang menyuruh menjalankan urutan langkah-langkah adalah kita sendiri.Bagaimana kalau yg menjalankan orang lain ?

- Kita harus memberikan urutan perintah yg dpt dipahami

- Urutan perintah salah, hasilnya salah (latihan algoritma sederhana)

Bagaimana kalau yg menjalankan perintah adalah MESIN ?

Page 11: Teori Komputasi

Siapa yg melakukan perintah ?Siapa yg diperintah ?

Mesin harus dapat berkomunikasi dgn kita :• mengerti bahasa kita• memberitahukan siap menerima perintah• menerima dan mengerti perintah• dapat mengerjakan perintah• memberikan hasil yg dikerjakan kepada kita dgn

menggunakan bahasa kita• memberitahukan bhw sudah selesai melaksanakan perintah

← kita (manusia)

← mesin

Bagaimana prinsip mesin tsb ?

Page 12: Teori Komputasi

Interaksi manusia - mesinMESIN

MANUSIA MANUSIAperintah hasil pelaksanaan

?

bahasa bahasa bahasamanusia mesin manusia antar muka : translator antar muka

Page 13: Teori Komputasi

Proses pemikiran atau abstraksi

bagaimana prinsip mesin tsb ?

← Mesin abstraksbg model komputasi

Page 14: Teori Komputasi

mesin abstrak >< mesin nyataapa hubungannya ?

Unsur utama Teori Komputasi :• Teori mesin abstrak• Teori bahasa

Studi lain (tidak dipelajari dalam kuliah ini):1.Translasi perintah dalam mesin dan interpretasinyaà coding & decoding

2.Realisasi perintah dan pengaruh akibatnyaà error correcting code

← dasar: struktur aljabar

Page 15: Teori Komputasi

Tugas dalam kuliah

(i) Tugas kelas, dikerjakan dalam kelas(ii) Tugas rumah,dikerjakan di luar kelas(iii)Tugas pemrograman, dikerjakan di luar

kelas. Tugas ini menggunakan bahasa C++, danselanjutnya dipresentasikan dalam kelas.

Page 16: Teori Komputasi

Buku Acuan

1. Harry R.Lewis, Cristos H.Papadimitrou, Elements of Theory of Computation, Prentice-Hall Inc.

2. Zohar Manna, Mathematical Theory of Computation, McGraw-Hill

3. Buku-buku matematika diskret yg relevan

Page 17: Teori Komputasi

2. Mesin Keadaan HinggaFinite State Machine

mesin seperti apa itu?

Page 18: Teori Komputasi

Mesin Keadaan Hingga

input M K H output-himp.hingga keadaan

-transisi keadaan

uang logam segelas minumanteks: 1 0

0 1

Page 19: Teori Komputasi

Cara menyajikan mesin ?

menggunakan graf berarah

menggunakan algoritma

Page 20: Teori Komputasi

mesin pembuka – penutup pintu

Mana keadaan ?

Mana input ? Output ?

Page 21: Teori Komputasi

Tabel transisi ?

Page 22: Teori Komputasi
Page 23: Teori Komputasi

Mesin Keadaan Hingga (finite state machine)

1 0 0 1Input : 1001 à transisi keadaan : s0 s0 s1 s3 s1

ouput : 0 1 1 0

Page 24: Teori Komputasi

Struktur Matematis

MKH merupakan sistem berupa 6-tupel :M = (S, I, O, f, g, s0)

dengan

S : himpunan hingga keadaan (state)I : himpunan hingga simbol inputO : himpunan hingga simbol outputf : fungsi transisi, f : S x I → S, fungsi keadaan berikut

g : fungsi output, g : S x I → O.f dan g disajikan dalam 2 cara :

1. tabel transisi2. diagram transisi

Coba periksa MKH contoh sebelumnya!

Page 25: Teori Komputasi

Struktur fisis

← arah gerak

ap pita input← kepala (head) baca

si

MKH

← kepala (head) tulis

ok pita output

← arah gerak

f(si,ap) = sj .g(si,ap) = ok .

Page 26: Teori Komputasi

MKH pembaca untaiPd diagram sebelumnya, untai input 1001→ output 01101. s0 = f(s0,1) ; 0 = g(s0,1) 3. s3 = f(s1,0) ; 1 = g(s1,0) 2. s1 = f(s0,0) ; 1 = g(s0,1) 4. s1 = f(s3,1) ; 0 = g(s3,1)

input : x = x0x1x2x3…… , fungsi input f ?s0 = f(s0, x0) = f1(s0, x0) , f = f1: S x I → Ss1 = f(s0, x1) = f(f1(s0, x0),x1)= f2 (s0, x0x1) f2: S x I2 →Ss3 = f(s1, x2) = f(f2(s0, x0x1),x2) = f2 (s0, x0x1x2) f3: S x I3 →S…….. → fn: S x In →Ss0 = fn(s0, x0x1x2 …. xn-1) = f(fn-1(s0, x0x1x2 …. xn-2), xn-1)

Page 27: Teori Komputasi

Bagaimana dgn fungsi output g?

O0 = g(s0,x0) = g1(s0,x0)

O1 = g(s1,x1) = g(f1(s0,x0), x1) = g2(s0,x0x1)……

On-1 = g(sn-1,xn-1) = g(fn-1(s0,x0x1…xn-2) = gn(s0,x0x1……xn-1)

gn : S x In → O

Definisi: jika x = x0x1x2x3…… input yg t.d n simbola : sembarang simbol input,

maka pemetaan f dan g dpt diperluas secara rekursif sbb:

(i) f(si, xa) = f(f(si, x),a) (ii) g(si, xa) = g(f(si, x),a) (iii) g(si, x0x1x2 …. xn-1) = g(si, x0).g(si, x0x1)….. g(si,x0x1…. xn-1)

Page 28: Teori Komputasi

Mesin penambah 2 bil integer biner :* ← carry (bawaan)

xn xn-1 …… x1 x0 ↓yn yn-1 ……y1 y0 ↓+

Diagram keadaan:

s0 : bawaan 0

s1 : bawaan 1Input: 00

0110

11

Periksa diagram tsb!

Page 29: Teori Komputasi

Mesin Ekivalen :M1 ≡ M2 jik –ka unt sembarang input yg sama, M1 dan M2

menghasilkan output yang sama

Keadaan Ekivalen, pd mesin M = (S, I, O, f, g, s0)

Unt si,sj ∈ S, si ≡ sj jik-ka g(si,x) = g(sj,x) ∀ x ∈I*Beri contoh !Teorema 1:

Jika s : suatu keadaan dlm MKH, x, y : untai, makaf(s,xy) = f(f(s,x),y) dan g(s,xy) = g(f(s,x),y)

Berikan contoh !

Tujuan : * ekivalensi mesin* mesin minimal

Page 30: Teori Komputasi

Bukti :

Gunakan induksi, sesuai dgn panjangnya y

ambil y=a (|y|=1), maka f(s,xa) = f(f(s,x),a) (sesuai (i))

Misal benar unt |y| = n, hipotesa induksi: f(s,xy) = f(f(s,x),y) Tunjukkan benar unt |y|=n+1!

Dari (i), f(s,xya) = f(f(xy),a)= f(f(f(s,x),y),a) ß Anggap s’ = f(s,x)= f(f(,s’,y),a) = f(s’,ya) à(sesuai (i))

= f(f(s,x),ya)

D.c.s unt g(s,xy) = g(f(s,x),y)

Page 31: Teori Komputasi

Teorema 2: Jika si ≡ sj , maka unt semb barisan input x ,berlaku f(si ,x) ≡ f(sj ,x)

Bukti :Def. seblmnya, jika si ≡ sj , maka g(si,xy) = g(sj,xy).

Teorema 1: g(f(si,x),y) = g(f(sj,x),y), unt suatu y ∈ I*.àdari def.ekivalensi : f(si ,x) ≡ f(sj ,x)

Definisi (k-ekivalen): Pada MKH M = (S,I,O,f,g,s0)

Unt integer pos k, si disebut k- ekivalen thd sj ditulis si ≡k sj jikasi ≡k sj g((si,x) = g(sj,x), unt semua x, dgn |x| ≤ k

apa artinya ?

Page 32: Teori Komputasi

Relasi k-ekivalen merupakan juga relasi ekivalensi, sehingga akan membuat k-partisi Pk pd himpunankeadaan S yg k- ekivalennya didefinisikan sbb:

[s]k = [sj|si ≡k sj] dan Pk = ∪ [s]ks ∈S

[s0]1 ={s0, s4, s5} [s1]1 ={s1, s2, s3}

dan

P1={{s0,s4,s5},{s1, s2, s3}}periksa melalui tabel trans.Apa yg terlihat?

Page 33: Teori Komputasi

Teorema 3: Jika untuk integer k, Pk+1 = Pk, maka Pk = P dan sebaliknya

Teorema 4: Mis. si ≡ sj , si ≡k+1 sj jik-ka si ≡ksj dan∀a∈I, f(si,a ) ≡k f(sj,a), serta g(si,a ) ≡k g(sj,a).

Definisi (keekivalenan 2 mesin):Diberikan M={S,I,f,g,s0} dan M’={S’,I,f’,g’,s’0}M ≡ M’, jik-ka untuk semua si∈S akan terdpt si’∈S’sedmkian sehingga si ≡ sj .

Definisi (tereduksi):MKH M = {S,I,f,g,s0} disebut tereduksi jik-ka si ≡ sjà si = sj unt semua keadaan si, sj ∈S

Page 34: Teori Komputasi

Teorema 5:Jika diberikan MKH M={S,I,f,g,s0}, maka akan terdapat

mesin ekivalen M’ sedemikian sehingga S’ ⊆ S dan S’bersifat tereduksi

Definisi (homomorfisma):Diberikan M={S,I,f,g,s0} dan M’={S’,I,f’,g’,s’0}.φ : pemetaan dari S ke S’Homomorfisma keadaan hingga adalah

φ(f(s,a)) = f’(φ(s),a)φ(g(s,a) = g’(φ(s,a))

Page 35: Teori Komputasi

3. Bahasa Alami dan Bahasa Formal- Pengantar -

Bahasa Alami :Komunikasi (lisan – tulisan) antar dua orang :

……

……..

Page 36: Teori Komputasi

Bahasa Alami dan Bahasa FormalApa Persamaan dan Perbedaaan ?

Kalimat berstruktur frasa:Aturan: ß sintaksKalimat dibuat dari frasa Subyek, diikuti Predikat, Obyek.

Subyek dibuat dari kt benda, Predikat dari kt kerja, Obyek dari kt benda.Kt Benda = {kucing, nasi, meja}, kt kerja = {makan, jalan}<kalimat> → <subjek> <predikat> <obyek>

→ <kt benda> <kt kerja> <kt benda>→ kucing <kt kerja> <kt benda>→ kucing makan <kt benda>→ kucing makan nasi

Kalimat lain : kucing makan kucing, kucing makan meja, nasi makankucing, kucing jalan meja, ……..

ßproses subst

(penurunan)

ß Periksa semantiknya

Page 37: Teori Komputasi

Proses penurunan total : <kalimat> →* kucing makan nasipenulisan lain : <kalimat> ::= <subyek><pred><obyek>

⇒ atau |-

Pohon Penurunan :<kalimat>

<subyek> <predikat> <obyek>

<kt benda> <kt kerja> <kt benda>

kucing makan nasi Buatlah lebih rinci struktur frasa tsb!

Bila Sdr belajar bhsIndonesia : di bagianmana dipelajari ?

Page 38: Teori Komputasi

Pengertian dasar dlm bahasa alami :

1.himpunan huruf dalam alfabet 2.kata dibentuk oleh rangkaian huruf3.kalimat dibentuk oleh rangkaian kata (dipisahkan spasi)4.bahasa dibentuk oleh rangkaian kalimat (dipisahkan spasi)

Bahasa alami lebih umumalfabet = {a, b, …, z} himp simbolkata = untai yg punyai arti kata = untairangkaian kata yg punya arti rangkaian untaibahasa alami baku bahasa

→ Kosakata : himp kata himp kata, himp simbol ?

Page 39: Teori Komputasi

Bahasa (dlm pengertian lebih umum)

• Bahasa : himpunan kalimat, himpunan untai• Kosakata : himpunan (tak hampa) hingga untai (i.e simbol)

bila kosakata adalah himp V (atau ), maka himp semuauntai sepanjang V adalah V* (atau *)

• Simbol : himp alfabet, himp karakter khusus, dsb• Untai :

untai hampa ^ atau εkosakata V = {0,1}, untai : ^ 0 1 01 11 00 101 …..

V= {t, i}, untai: ^ t i tt ii titiii …panjang untai

w = 101, |W| = 3, |titi| = 4

Page 40: Teori Komputasi

Bahasa (umum)Untai:

• posisi simbol dlm untaiw = titi, w(1)=w(3)=t ; w(2) = w(4) = i, posisi {1,2,…, |w| } → V

• operasi untaiPerangkaian (concatenation)v, w untai sepanjang V, perangkaian vw atau wvsifat : vw ≠ wv, ^ : unsur identitas, ^w=w^=w

asosiatif, (uv)w = u(vw)

Berikan penjelasan struktur aljabar yg terkait !

Page 41: Teori Komputasi

Himpunan untai & struktur aljabar

V : himp simbolV*: himp untai sepanjang V

struktur : grup ?monoid ?

V = {a,b}, V* ={a, aa, .,b,bb, ab,..}Adakah op.biner, unsur identitas ?

Adakah sifat lain?

Page 42: Teori Komputasi

Bacalah literaturTtg STRUKTUR

ALJABAR !

Page 43: Teori Komputasi

Bahasa (umum-pengertian dasar)

(v)Himpunan untaiV : kosakata (mungkin berupa himp alfabet)V*: himp untai sepanjang V (termasuk ^)∅ Atau {} : himp. yg tak mengandung satupun untaiV+ = V* - ∅• operasi antar 2 himp untaiA, B ⊆ V, rangkaian (concatenation) : AB atau BAAB = {xy| x ∈ A, y∈B}

A = {a,bb}, B = {b,ab, aa}, AB = {ab, aab,aaa,bbb,bab,baa}Sifat rekursifitas: A0 = {^}

An+1 = An. A, n=0, 1,…A = {a,bb}; A0 = {^}, A1 = A0A={a,bb}, A2 = A1A=

Page 44: Teori Komputasi

Bahasa (umum)pengertian dasar• penutup Kleene

A ⊆ V*, A* : penutup Kleene dari A = (vi)subuntai: v subuntai w jik-ka ∃ untai x dan y ∋ w = xvy(vii)prefiks dan sufiks

jika w = vx ∀x, maka v : prefiks dari wjika w = xv ∀x, maka v : sufiks dari w

(vii) Banyaknya munculnya untai : w = ti, w2 =(ti)2= titirekursivitas: w0 = ^, wi+1 = wi w, i = 0,1, ….

Page 45: Teori Komputasi

pengertian dasar:(ix)balikan

w : untai. Balikan w ditulis w’ merupakan w yg nyatakan dari belakang ke depanw = balik, w’ = kilab

1.jika |w|=0, maka w’=w=^2.jika |w|=n+2>0, untuk w = ua, a∈V, maka w’=au’Umum : untuk 2 untai w dan x, berlaku (wx)’=x’w’Contoh : (desasdesus)’ = (desus)’(desas)’=sesudsased

• |x| = 0, maka x=^, dan (wx)’=(w^)’=w’=^w’=^’w’=x’w’• Andaikan unt |x|≤n, (wx)’=x’w’ ß hipotesa induksi• Misal |x|=n+1, dg x = ua,|u|=n, |a|=1, u,a ∈V*

Page 46: Teori Komputasi

pengertian dasar:(ix)balikanmaka (wx)’ = (w(ua))’ … x=ua

= ((wu)a)’ .. perangkaian: asosiatif

=a(wu)’ … definisi balikan= au’w’ … hipotesa induksi= (ua)’w’ … definisi balikan= x’w’ … x=ua

Teorema :Apabila V : himp berhingga alfabet, maka V* :

himp berhingga terhitung.àTerdapat pemetaan bijektif f : N à V*

(perhatikan cara penyusunan kamus)

Page 47: Teori Komputasi

Untai dan Bahasa

• Perhatikan cara penyuntingan berbantuan komputer menggunakan perangkat lunak (misal microsoft words)

- mengetik huruf demi huruf, kata demi kata, kalimat demi kalimat

- menghapus huruf, kata, kalimat- menyalin huruf, kata, kalimat- mencari kata tertentu dan menggantikan dgn kata lain- dsb

Page 48: Teori Komputasi

4. Automata Hingga

Page 49: Teori Komputasi

Automata Hingga

Automata – Automaton ?

Automatis ?

Apa bedanya dgn mesin keadaan hingga ?

Page 50: Teori Komputasi

Automata Hinggadiagram transisi tabel transisi

mesin dalam keadaan s0 membaca a beralih ke keadaan s0

mesin dalam keadaan s0 membaca b beralih ke keadaan s1

Page 51: Teori Komputasi

Automata Hingga5-tupel, M = (S, I, f, s0 ,F)

dengan,

S : himp hingga keadaanI : himp hingga simbol inputf : pemetaan S x I → S (fungsi transisi keadaan)s0: keadaan awal, s0 ∈SF : himp keadaan akhir (penerima), F ⊆ S

pd contoh, S = {s0, s1}, I = {a, b}, keadaan awal s0, F = {s1},f: (s0, a) → s0 ; (s1, a) → s1 ;

(s0, b) → s1 ; (s1, b) → s0 ;

Page 52: Teori Komputasi

Automata hingga dan Bahasa* pengenalan untai

xxxx → automata → dikenal/tdkM xxxx ∈ atau ∉ L(M) ?

pd contoh, aba ∈ atau ∉ L(M) ?

(s0, aba) → (s0, ba) f(s0, aba) = f(f(f(s0, a),b,),a) → (s1, a) = f(f(s0, b),a)→ (s1,^) = f(s1, a)→ (s1) = s1

s1 ∈ F, aba ∈ L(M)

Page 53: Teori Komputasi

s0 : keadaan penerima

Page 54: Teori Komputasi

Bahasa dan Automata Hingga Pengenalan Untai

x = aabba M = (S, I, f, s0 , F), S = {s0, s1}, I = {a, b}, F = {s0}

Proses komputasi pemeriksaan untai :f(s0, aabba) = f(f(f(f(f(s0, a), a), b), b), a)

= f(f(f(f(s0, a), b), b), a)= f(f(f(s0, b), b), a)= f(f(s1, b), a)= f(s0, a)= s0

s0 : keadaan penerima, maka untai aabba diterima oleh Mà aabba ∈ L(M)

Page 55: Teori Komputasi

Automata hingga & pengenalan untai

(s0, aabba) |→M (s0, abba) M(s0, aabba) → M(s0,abba)|→M (s0, abba) → M(s0,bba)|→M (s1, ba) → M(s1, ba)|→M (s0, a) → M(s0, a)|→M (s0, ^), untai selalu berakhir dgn ^ …

Jadi, (s0, aabba) |→M* (s0, ^)

Page 56: Teori Komputasi

Bahasa yg dibangkitkan automata

• Perhatikan automata M

Untai yg dikenal: b, b…b, ab, ab….b, bab, bab..b, ab…bab,.. ; L(M) = ?

L(M) = {ambn | m=0,1,..; n=1,2, …} ∪{ambn ak bn| m=0,1,..; n=1,2, , k=1,2,…} ∪…}

s1 : penerima (akhir)

Page 57: Teori Komputasi

Bagaimana dengan M :

Page 58: Teori Komputasi

Automata Hingga Deterministik (AHD) Automata Hingga Nondeterministik (AHN)

Diagram transisi Tabel transisi

Mesin dlm keadaan s1 membaca a, beralih ke keadaan s1 ATAU ke keadaan s2 .

Bandingkan automata hingga deterministik !

Page 59: Teori Komputasi

AHNM = (S, I, f, s0 ,F)

dengan,

S : himp hingga keadaanI : himp hingga simbol inputf : pemetaan S x I → B, B ⊆ S (fungsi transisi keadaan)

s0: keadaan awal, s0 ∈SF : himp keadaan akhir (penerima), F ⊆ S

pd contoh, S = .. , I = .. , F = …, s0 = .., f : (s0, a) → s0 ; (s1, a) → s1 atau

(s0, b) → s1 ; (s1, a) → s0 ;

Page 60: Teori Komputasi

Pd contoh : aba ∈ L(M) ?

f(s0, aba) = f(f(f(s0, a),b,),a)= f(f(s0, b),a)= f(s1, a)= f(s1, ^) ∪ f(s0, ^) = (s1) ∪ (s0)

↓ ↓aba ∈ L(M) aba ∉ L(M)

apa kesimpulannya ?Periksa : bab ∈ L(M) ?

Page 61: Teori Komputasi

Ekivalensi 2 buah AHD

Diberikan 2 buah AHD, yaitu M dan M’.M ekivalen M’, jik-ka L(M) = L(M’).

Untuk memeriksa ekivalensi M dan M’ àAlgoritma More

(hand-out)

Page 62: Teori Komputasi

Pemeriksaan ekivalensi AHD

Teorema Moore :

Terdapat suatu algoritma untuk menentukan apakah dua buah automata hingga ekivalen atau tidak sepanjang ∑

Page 63: Teori Komputasi

Algoritma Moore11. Berikan nama berbeda pd semua keadaan M dan M’.

Misalkan, M : S, A1, A2 , ... M’ : S’, A1 ’, A2’, ...

2.Buat tabel (n+1) kolom, yaitu kolom: (v,v’), (va1,va1’), ..., (van,van’), sbg pasangan terurut (keadaan M, keadaan M’).

3. Isikan (S,S’) pd baris ke-1 kolom (v,v’); S, S’ : keadaan awal M dan M’. 4. Jika ∃ busur dari S ke A1 dg label a1 dan jika ∃ busur dari S’ ke A1’ juga dg label a1, isikan pasangan terurut (A1, A1’ ) pd baris ke-1 kolom (va1,va1’).Lakukan juga unt kolom-kolom berikutnya.

5. Jika ∃ nilai pasangan terurut pd kolom (va1,va1’) s/d (van,van’) yang tidak sama dengan nilai pasangan terurut (v,v’), tempatkan nilai tsb pd kolom (v,v’) baris-baris berikutnya.Lakukan hal yg sama spt yg dilakukan pd langkah (4). Lanjutkan dengan langkah

6 Jika selama proses dihasilkan nilai pd kolom (v,v’), dg v : keadaan penerima sedangkan v’ bukan, atau sebaliknya, maka M dan M’ tersebut tidak ekuivalen. Proses dihentikan

7. Jika kondisi (6) tdk dipenuhi dan jika tdk ada lagi pasangan terurut baru yg harus ditempatkan pada kolom (v, v’) maka proses dihentikan. M dan M’ ekuivalen.

Page 64: Teori Komputasi

Apakah M ekivalen M’

Page 65: Teori Komputasi

Apakah M ekivalen M’

Page 66: Teori Komputasi

AHD - AHN

Teorema :Untuk setiap AHN, terdapat suatu AHD yang ekivalen

Bukti : lht diktat

Contoh :Pembangunan AHD dari AHN (hand out)

Page 67: Teori Komputasi

Algoritma pembangunan1.Tetapkan s0 = s0’ dan I=I’2. Salinlah tabel transisi M ke tabel M’

(awalnya I’=I dan f’=f)3. Setiap keadaan s adalah peta dari pemetaan f dan

apabila terdapat s ∉ S, maka s tsb ditetapkan sbg keadaan baru dari I’

4. Tempatkan s tsb pada kolom keadaan f’, dan lakukan pemetaan berdasarkan pemetaan f.

5. Ulangi langkah 3 sampai tdk diperoleh keadaan baru

6. Unsur F’ adalah semua keadaan yg mengandung keadaan dalam F

Page 68: Teori Komputasi

Diberikan AHN, M = (S, I, f, s0, F) dgn S={A,B, C}, I={ a, b}, s0= A, F = {C}

• Tabel transisi, f :

• Buatlah AHD M’ yg ekivalen !

Page 69: Teori Komputasi

1. s0’ = s0 = A, I’ =I = {a, b}2. salinan tabel fs transisi f menghasilkan tabel fs transisi f’

sbb:

Pd tabel di atas terdpt keadaan baru yaitu {A,B}. Pemetaan terhadap {A,B} :

f({A,B},a) = f(A,a) ∪ f(B,a) = {A,B}∪A = {A,B}, dan f({A,B},b) = f(A,b) ∪ f(B,b) = C∪B = {B,C}, shg

diperoleh tabel berikut :

Page 70: Teori Komputasi

Tabel baru

4. Langkah (3) di atas menghasilkan keadaan baru yaitu{B,C}. Dg melakukan pemetaan thd {B,C}, seperti yg telah dilakukan di atas, diperoleh tabel sbb:

Page 71: Teori Komputasi

5. Setelah langkah (4) di atas tidak terdapat lagi keadaan baruJadi, AHD yg dihasilkan, M’ = (S’, I’, f’, s0’, F’), dgn.S’ ={A, B, C, {A,B}, {B,C}}, I’ ={a, b}, s0’ = A, F’={C, {B,C}}.Sehingga f’ serta graf transisi dari M’ adalahf’ : tabel terakhirGraf transisi :

file berikut : tekom_3Isi : tata bhs formal

Page 72: Teori Komputasi

Dokumen selanjutnya,

Teori Komputasi bagian kedua