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

Bagian pertama

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

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?

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

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)

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 ?

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

Kalkulasi : proses melakukanperhitungan

Komputasi: proses menjalankan urutan

langkah-langkah

dlm penyelesaian masalah

dlm penyelesaian masalah

Urutan langkah-langkah (?)

ß ALGORITMA

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 ?

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 ?

Interaksi manusia - mesinMESIN

MANUSIA MANUSIAperintah hasil pelaksanaan

?

bahasa bahasa bahasamanusia mesin manusia antar muka : translator antar muka

Proses pemikiran atau abstraksi

bagaimana prinsip mesin tsb ?

← Mesin abstraksbg model 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

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.

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

2. Mesin Keadaan HinggaFinite State Machine

mesin seperti apa itu?

Mesin Keadaan Hingga

input M K H output-himp.hingga keadaan

-transisi keadaan

uang logam segelas minumanteks: 1 0

0 1

Cara menyajikan mesin ?

menggunakan graf berarah

menggunakan algoritma

mesin pembuka – penutup pintu

Mana keadaan ?

Mana input ? Output ?

Tabel transisi ?

Mesin Keadaan Hingga (finite state machine)

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

ouput : 0 1 1 0

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!

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 .

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)

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)

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!

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

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)

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 ?

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?

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

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

3. Bahasa Alami dan Bahasa Formal- Pengantar -

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

……

……..

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

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 ?

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 ?

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

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 !

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?

Bacalah literaturTtg STRUKTUR

ALJABAR !

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=

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, ….

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*

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)

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

4. Automata Hingga

Automata Hingga

Automata – Automaton ?

Automatis ?

Apa bedanya dgn mesin keadaan hingga ?

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

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 ;

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)

s0 : keadaan penerima

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)

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, ^)

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)

Bagaimana dengan M :

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 !

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 ;

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

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)

Pemeriksaan ekivalensi AHD

Teorema Moore :

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

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.

Apakah M ekivalen M’

Apakah M ekivalen M’

AHD - AHN

Teorema :Untuk setiap AHN, terdapat suatu AHD yang ekivalen

Bukti : lht diktat

Contoh :Pembangunan AHD dari AHN (hand out)

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

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 !

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 :

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:

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

Dokumen selanjutnya,

Teori Komputasi bagian kedua