handout automata

BAB I PENDAHULUAN

PENGERTIAN AUTOMATATeori otomata mempelajari tentang mekanisme komputer abstrak atau mesin abstrak. Jauh sebelum ada komputer, tahun 1930, Alan Turing mempelajari mesin abstrak yang punya kemampuan seperti komputer sekarang, dikenal dengan nama Mesin Turing. Tujuan Turing adalah menggambarkan secara jelas apa yang dapat dan yang tidak dapat dilakukan mesin komputing. Kemudian pada tahun 1940 an dan 1950-an, ditemukan mesin abstrak yang lebih sederhana, yaitu finite automata. Automata ini, asalnya diperuntukkan untuk membentuk fungsi kecerdasan, berubah secara drastis untuk keperluan lain yang sangat beragam. Tahun 1950-an juga Chomsky mempelajari tentang tata bahasa formal, yang sangat berguna untuk pengembangan compiler. Semua pengembangan teori ini secara langsung melahirkan ilmu-ilmu komputer yang sekarang ini. Beberapa konsepnya, seperti Finite Automata dan grammar, digunakan untuk perancangan dan pembuatan bermacam software penting, seperti Pascal dan C. Konsep lainnya, seperti Mesin Turing, membantu kita memahami apa yang dapat kita harapkan dari perangkat lunak kita.

KEDUDUKAN TEORI BAHASA

DAN

OTOMATA

Ilmu komputer mempunyai dua komponen utama, pertama : model dan gagasan mengenai komputasi, dan kedua adalah teknik rekayasa untuk perancangan sistem komputasi, yang meliputi perangkat keras dan perangkat lunak. Teori Bahasa dan Otomata merupakan bagian dari komponen pertama. Finite State Automata dan ekspresi regular awalnya dikembangkan berdasarkan pemikiran jaringan syaraf tiruan (neural network) dan rangkaian switch (switching circuit). Finite State Automata sangat berguna dalam perancangan lexica l analyzer, yang merupakan bagian dari sebuah compiler. FSA dan ekspresi regular juga digunakan dalam perancangan text editor, pattern-matching, sejumlah pemrosesan teks, dan program file-searching serta sebagai konsep matematis untuk aplikasi lain. Mengapa mempelajari teori? Teori memberikan konsep dan prinsip yang menolong untuk memahami perilaku dari suatu disiplin ilmu. Bidang ilmu komputer meliputi topik yang sangat luas, dimana sebagian besar mempunyai prinsip yang umum. Untuk mempelajari prinsip dasar inilah diperlukan pemodelan secara abstrak dari komputer. Model ini memiliki fungsi-fungsi yang penting dan umum untuk dapat diterapkan pada perangkat keras maupun perangkat lunak. Beberapa gagasan yang diutarakan memiliki penerapan yang penting. Misalkan pada compiler.

Materi Kuliah Teori Bahasa Dan Otomata

Author : Fajar Astuti H, S.Kom

PENGANTAR MODEL KOMPUTASIKuliah ini membahas model-model komputasi sebagai mesin abstrak yang dapat didefinisikan secara matematis, mulai dari yang paling sederhana hingga yang paling powerful. Model-model sederhana dibahas agar formalisasi matematis dapat terbentuk secara bertahap, selain itu tetap masih ada hubungannya dengan situasi-situasi dunia nyata. Secara umum model-model digambarkan sebagai mesin untuk menjawab masalah keputusan berdasarkan masukan string x dengan memberikan keluaran berupa : ya atau tidak misalnya : Apakah x bilangan ganjil Apakah sebuah kata s anggota bahasa B Masalah komputasi memang lebih umum daripada masalah keputusan, namun pada dasarnya suatu model untuk masalah keputusan memerlukan komponen yang dapat melakukan komputasi yang terkait, misalnya : Untuk suatu (x,y), apakah y = f(x)? hanya dapat dijawab jika f(x) dapat dikomputasi. Model-model mesin yang akan dibahas pada kuliah ini adalah Finite Automata (FA), PushdownAutomata(PDA), Mesin Turing (TM). Teori dan model komputasi ini telah berkembang jauh sebelum ditemukan perangkat komputer itu sendiri.

KONSEP BAHASASimbol. Simbol merupakan elemen unik terkecil dari bahasa. Dalam sebuah bahasa terdapat sejumlah berhingga simbol-simbol. Abjad / Alfabet. Merupakan himpunan dari simbol-simbol yang digunakan dalam suatu bahasa. Biasanya dinotasikan dengan . Misalkan = {0,1}. String / word / kata / untai. Adalah barisan berhingga dari simbol-simbol dalam suatu alfabet. Misalkan : = {0,1} maka 01, 00, 111 merupakan string yang dibentuk berdasarkan alfabet . Dalam pembahasan, seringkali suatu untai/string dinyatakan dengan suatu variabel, yang biasanya berupa huruf kecil. Contoh : w = 01; x = aba, dst. Panjang String. Suatu string disusun dari sejumlah n simbol, dengan n 0. Banyaknya simbol yang menyusun sebuah string disebut panjang string, yang disimbolkan dengan | x|. contoh : x = aba , maka |x| = 3. Untai hampa. Sebuah string dengan panjang nol (n=0) disebut untai hampa dan dinotasikan dengan . Untai hampa () merupakan untai yang dibentuk berdasarkan abjad apa saja. Sehingga merupakan himpunan bagian dari sembarang himpunan. Bahasa. Bahasa merupakan himpunan string/kata dari alfabet bahasa itu. Misal untuk



- 1 = {0,1} maka L1 = {00,01,11,111} merupakan bahasa yang dibentuk berdasarkan abjad 1 . - 2 = {a,b} maka L2 = {a, ab, aab, aaab, } merupakan bahasa berdasarkan abjad 2 Misalkan suatu abjad dan w adalah untai yang dibentuk berdasarkan abjad . Jika terdapat L yang merupakan bahasa berdasar abjad dan jika w ada di dalam L, kita tuliskan w L, yang berarti w elemen dari L. Bahasa kosong. Merupakan bahasa yang tidak terdiri dari untai apapun. Dinotasikan dengan {} atau . Bahasa Universal. Adalah bahasa yang terdiri dari semua kata yang dapat dibentuk berdasarkan suatu abjad . Misalkan = {1} maka bahasa universal, dinotasikan *, adalah * = {, 1, 11, 111, 1111, }

OPERASI

PADA

STRING

Perangkaian (Concatenation). Jika w dan z adalah untai, perangkaian w dengan z merupakan untai yang diperoleh dengan merekatkan z ke w. Contoh : w = abang dan z = none maka wz atau w.z = abangnone. Panjang kata wz, |wz| = |w| + |z|=9. Sebarang kata jika dirangkai dengan , tidak akan merubah kata tersebut. w = w=w. Jadi merupakan identitas (identity) terhadap operasi perangkaian. Pangkat (Exponentiation). Misalkan w merupakan sebuah kata, untuk n bilangan asli, didefinisikan : ; n = 0 w n = n 1 ww ; n > 0 Misalkan , = {0,1} dan w = 110, diperoleh : w0 = w1 = w.w0 = 110. = 110 w2 = w.w1 = 110.110 = 110110 w3 = w.w2 = 110.110110 = 110110110

Sama Dengan (Equal). Jika w dan z adalah untai, dikatakan w sama dengan z jika keduanya terdiri dari simbol-simbol yang sama dan panjangnya sama, dinotasikan w = z. Awalan (prefix). Jika w dan x adalah kata, maka x merupakan awalan dari w jika untuk suatu untai y, berlaku w = xy. Contoh w = 121 dan x = 12, maka x merupakan awalan dari w, dimana dalam hal ini y = 1. Subuntai (substring). Sebuah untai w merupakan subuntai dari untai lain z jika terdapat untai-untai x dan y, sehingga berlaku z = xwy. Pembalikan (reversal / transpose). Transpose dari sebuah untai w, yaitu wR, didefinisikan sebagai :Materi Kuliah Teori Bahasa Dan Otomata Author : Fajar Astuti H, S.Kom

w; w = wR = R y a; w = ay , a , y * Contoh : w = able, wR = (able)R = (ble)R a = (le)Rba = (e)R lba = ()Relba = . elba = elba

OPERASI PADA BAHASAConcatenation. Misal A dan B adalah bahasa berdasarkan suatu abjad. Didefinisikan perangkaian dari bahasa A dan B sebagai : A.B = { w.x | w A dan x B} Jadi A.B terdiri dari semua untai yang dibentuk dengan mengambil setiap untai di A dan merangkaikannya dengan setiap untai di B. Contoh : A = {bird, dog} dan B = { house} maka AB = {birdhouse, doghouse} Eksponensiasi. Misalkan A bahasa berdasarkan abjad , didefinisikan : {}; n = 0 An = n 1 A. A ; n 1

Jadi, jika misalkan A = {ab,a} berdasarkan abjad = {a,b} maka : A0 = { } A1 = A.A0 = {ab,a}{} = {ab,a} A2 = A.A1 = {ab,a}{ab,a} = {abab,aba,aab,aa} A3 = A.A2 = {ab,a}{abab,aba,aab,aa} = {ababab,ababa,abaab,abaa,aabab,aaba, aaab,aaa} Gabungan (Union). Jika A dan B adalah bahasa berdasarkan abjad maka gabungan dari A dan B, A B, terdiri dari semua kata yang muncul sekurang-kurangnya sekali di dalam A dan B. A B = {x | x A atau xB} Irisan (intersection). Irisan dari bahasa A dan B terdiri dari kata-kata yang muncul di A sekaligus di B. Dinotasikan sebagai : A B, A B = {x | x A dan x B} Selisih (Difference). Jika A dan B bahasa berdasarkan abjad , didefinisikan selisih antara bahasa-bahasa tersebut sebagai : A B = {x | x A dan x B}



Komplemen. Komplemen dari suatu bahasa A berdasarkan abjad didefinisikan sebagai : A = * A . Subbahasa (sublanguage). Jika A dan B bahasa berdasarkan abjad , dan jika semua untai di A juga merupakan untai di B maka A disebut subbahasa dari B. (A B) Equal. Dua bahasa A dan B dikatakan sama atau equal, A = B, jika kedua bahasa tersebut secara persis mempunyai untai-untai yang sama. Pembalikan (Transpose/Reversal). Pembalikan dari suatu bahasa A dapat didefinisikan sebagai : AR = { xR | x A } Contoh : A = { dog, bog} maka AR = {god, gob}. Kleene Closure / Star Closure. Jika A sebuah bahasa maka penutup kleene dari bahasa A didefinisikan sebagai : A* =

n =0

An .

Contoh : A = {a} maka A* = {,a,aa,aaa,} Positive Closure / Plus Closure. Jika A sebuah bahasa maka penutup kleene dari bahasa A didefinisikan sebagai : A+ =

n =1

An .

Contoh : A = {a} maka A+ = {a,aa,aaa,}. Teorema : A+ = A. A* = A*. A

SOAL-SOAL1. Misalkan A = {the,my} dan B = {horse,house,hose} merupakan bahasa-bahasa berdasarkan alfabet bahasa inggris. Carilah A.B, A.A 2. Misalkan A = {,a}. Carilah An untuk n = 0,1,2,3. Berapa banyaknya elemen An untuk sembarang n? 3. Misalkan A = {}. Carilah A*. 4. Misalkan A = {,ab} dan B = {cd}. Tentukan untai-untai dalam A*B. 5. Misalka A = {a,b} Carilah A* 6. Misalkan A = {}, B = {aa,ab,bb}, C = {,aa,ab} , dan D = {}. Carilah AB, AC, AD, BD dan AB, BC, CD, AD. Misalkan F sebarang bahasa carilah FD dan FD. 7. Misalkan bahasa S = {a,b} dan S* merupakan star closure dari bahasa S. Ada berapa kata di S* yang punya panjang 2? Panjang 3? Panjang n?



8. Misalkan bahasa S = {aa,b} dan S* merupakan star closure dari bahasa S. Ada berapa kata di S* yang punya panjang 4? Panjang 5? Panjang 6? (Jelaskan secara umum) 9. Misalkan bahasa S = {ab,ba} dan S* merupakan star closure dari bahasa S. Tuliskan semua kata di S* yang panjangnya kurang atau sama dengan 7. Mungkinkan ada kata dalam S* yang mempunyai substring aaa atau bbb? 10. Misalkan bahasa S = {a, ab,ba} dan S* merupakan star closure dari bahasa S. Apakah string abbba ada di S*? Tuliskan semua kata di S* yang panjangnya kurang atau sama dengan 6!

REFERENCE[1] Hopcroft,John E; Motwani, Rajeev; Ullman, Jeffrey D.; Introduction to Automata Theory, Language and Computation; Second Edition; Addison-Wesley, 2001. [2] [3] Kelley, Dean; Otomata dan Bahasa Formal, Sebuah Pengantar; PT. Prenhallindo, 1999 Cohen, Daniel I.A; Introduction to Computer Theory; John Wiley & Sons, Inc, 1991.

BAB IIMateri Kuliah Teori Bahasa Dan Otomata Author : Fajar Astuti H, S.Kom

BAHASA REGULER

DEFINISI BAHASA REGULARMisalkan merupakan sebuah abjad. Kumpulan dari bahasa regular berdasar didefinisikan secara rekursif sebagai berikut [1] : (1) adalah sebuah bahasa regular (2) {} adalah sebuah bahasa regular (3) untuk setiap a , {a} merupakan bahasa regular. Disebut juga bahasa singleton (4) Jika A dan B bahasa regular maka AB, A.B, dan A* atau B* merupakan bahasa regular. (5) Tidak ada bahasa lain berdasarkan yang regular. Contoh 1 : Misalkan = {a,b}, maka berikut ini merupakan bahasa-bahasa regular berdasarkan yaitu , {},{a},{b},{a,b},{ab},{a,ab,b},{ai | i 0}, {(ab)i | i 0}

EKSPRESI REGULAREkspresi Regular (Regular Expression), disingkat RE, didefinisikan sebagai berikut: (1) merupakan ekspresi regular untuk bahasa regular (2) merupakan ekspresi regular untuk bahasa regular {} (3) a merupakan ekspresi regular untuk bahasa singleton {a} (4) Jika r ekspresi regular untuk bahasa regular A dan s sebuah ekspresi regular untuk bahasa regular B, maka - r + s merupakan ekspresi regular untuk bahasa A B - rs merupakan ekspresi regular untuk bahasa A.B - r* merupakan ekspresi regular untuk bahasa A* Contoh 2: BAHASA REGULAR RE {} {a} a {a,b} a+b {ab} ab {a,aa} a+aa {a}* a* {a,b}* (a+b)* {,ab}* (+ab)*

Teorema Misalkan r,s dan t merupakan ekspresi regular berdasar abjad yang sama, maka berlaku : (1) r + s = s + r (2) r + = + r = r (3) r + r = r (4) (r + s) + t = r + (s + t) (5) r. = .r = r (6) r. = .r = (7) (rs)t = r(st) (8) r (s + t) = rs + rt dan (r + s) t = rt + st (9) r* = r** = r* r* = ( + r)* = r* (r + ) = (r + ) r* = + rr* (10) (r+s)* = (r* + s*)* = (r* s*)* = (r* s)* r* = r* (sr*)*



(11) (12) (13) (14) (15)

r (sr)* = (rs)* r (r* s)* = + (r + s)*s (rs*)* = + r(r+s)* s (r+)*(r+)+s = sr* rr* = r*r = r+

Seperti halnya dalam operasi aritmatik, untuk menghilangkan ambiguitas saat menggunakan notasi +, * dan concat, maka diperlukan suatu hirarki penulisan notasi. Hirarki tertinggi adalah *, kemudian concat, dan terakhir +. Tanda kurung berperan untuk mengelompokkan suatu subekspresi sebagai satu entitas ekspresi seperti halnya penulisan formula aritmatika. Misalkan : aa*(b+ba*)*b Berikut ini contoh penulisan ekspresi regular dari pendefinisian bahasa regular : Contoh 3: Jika = {a,b} dan L adalah bahasa berdasarkan abjad yang semua string didalamnya mempunyai panjang genap. (termasuk L, dimana panjangnya nol) Setiap string yang panjangnya genap merupakan hasil operasi concat dari string dengan panjang 2 atau dapat dituliskan : L = {aa + ab + ba + bb}* dimana dapat dinyatakan dengan ekspresi regular (aa+ab+ba+bb)* = (a(a+b) + b(a+b))* = ((a+b)(a+b))* Contoh 4: Jika = {a,b} dan L adalah bahasa berdasarkan abjad yang semua string didalamnya diakhiri dengan double a. Sembarang string berdasarkan abjad dapat dituliskan L1 = {a,b}*, dan kemudian diconcat dengan L2 = {aa} , sehingga menjadi L1.L2 = {a,b}*{aa}. Jika dituliskan dalam ekspresi regular : (a+b)*(aa)

FINITE AUTOMATA (FA)Suatu Finite Automata (FA) atau kadang disebut Finite State Automaton (FSA) adalah mesin abstrak yang dapat mengenali bahasa regular. FA didefinisikan sebagai berikut : Suatu FA merupakan mesin status hingga yang terdiri dari 5 tuple yaitu (Q,,s,F,) dimana Q merupakan himpunan berhingga dari state (status) adalah himpunan alfabet dari simbol input. s Q merupakan sebuah state yang berlaku sebagai state awal (start state). F Q yang merupakan state akhir (final state) adalah fungsi transisi yang memetakan Q x ke Q , ditulis (Q,) = Q Contoh 5: Diketahui sebuah FA M = (Q, ,s,F, dimana Q = 0, q1, q2}, = {a,b}, s = q0, F = ) {q {q0} dan : a b q0 Q1 q2 q1 Q2 q0 q2 Q2 q2 FA tersebut dapat dinyatakan dalam bentuk digraf sebagai berikut:



a b

q 0

q 1

bq 2

a

a , b

FINITE AUTOMATA

DAN

BAHASA REGULAR

RE=(ab)*

Dalam definisi suatu FA terdapat sejumlah status akhir. Apabila sebuah string masukan membawa status FA mulai dari status awal ke salah satu status akhir maka string tersebut diterima atau dikenali oleh FA tersebut. Dan sebuah bahasa L dikatakan diterima oleh sebuah FA jika semua string elemen bahasa L diterima oleh FA tersebut. Contoh 6 : Perhatikan FA pada contoh 5, string ab diterima oleh FA tersebut karena jika kita mulai dari status awal q0 membaca input a, kita akan menuju status q1. Kem udian dari q1 membaca b, menuju status q0. Disini pembacaan inpu selesai, dan berhenti di status akhir (final state). Sehingga ab diterima oleh FA tersebut. Contoh 7 : String aab tidak diterima oleh FA pada contoh 5. Mengapa? String apa saja yang diterima oleh FA tesebut? Bahasa apa yang diterima oleh FA tersebut?

NONDETERMINISTIC FINITE AUTOMATAFA pada contoh 5 merupaka Deterministic Finite Automata, dimana banyaknya transisi dari satu status ke status lainnya satu dan hanya satu. Nondeterministic Finite Automata adalah FA yang banyaknya fungsi transisi () dari satu state ke state lainnya nol, satu atau lebih dari satu state. Contoh 8 : Berikut ini adalah NFA M = (Q,,s,F,) dimana Q = {q0, q1, q2}, ={a,b}, s=q0, F = {q0} dan : a {q1} {} {q0} b {} {q0,q2} {}

Q0 Q1 Q2 Atau dalam bentuk digraf :



a b

q0

q1

bq2

b

EKIVALENSI NFA DAN DFA(1)(2) Jika terdapat sebuah NFA M = (Q,,s,F,) yang menerima bahasa L, maka ada DFA M=(Q,, s,F,) yang juga menerima bahasa L , dimana : = s = s Jika Q = {q0, q1, , qn} maka mula-mula Q = { [q0],[q1],,[qn]} (4) Jika (qi,a) = {qj, qk, } dan a , maka ([qi],a) = [qj, qk, ] dan [qj, qk, ] menjadi state baru dan digabungkan ke Q (5) Setiap state baru dalam Q yang diperoleh, dicari transisi untuk setiap input dalam . Dimana ([qj, qk, ],a) = (qj,a) (qk,a) (6) F terdiri dari semua state di Q yang mengandung state di F. Contoh 9 : Carilah sebuah DFA M=( Q,,s,F,) yang ekivalen dengan NFA M=(Q,,s,F,) pada contoh

(3)



a b

q0

q1

aq2

b

.

(1) (2) (3) (4)

(5)

= = {a,b} s = s = [q0] Qmula-mula = {[q0],[q1],[q2]} (q0,a) = {q1} (q0,a) = [q1] (q0,b) = {} (q0,b) = [ ] (state baru) (q1,a) = {} (q1,a) = [ ] (q1,b) = {q0,q2} (q1,b) = [q0, q2] (state baru) (q2,a) = {q0} (q2,a) = [q0] (q2,b) = {} (q2,b) = [ ] maka Q = {[q0],[q1],[q2], [],[q0, q2]} ( [] , a) = [] ( [] , b) = [] ( [q0, q2], a ) = (q0,a) (q2,a) = {q1} {q0} = {q0,q1} [q0,q1] ( [q0, q2], b ) = (q0,b) (q2,b) = {} {} = {} [] ( [q0, q1], a ) = (q0,a) (q1,a) = {q1} {} = {q1} [q1] ( [q0, q1], b ) = (q0,b) (q1,b) = {} {q0,q2} = {q0,q2}

Tidak ada state baru. (6) F = {[q0], [q0,q2],{qo,q1}} Maka kita mendapatkan sebuah DFA M = (Q,,s,F,) dengan Q = {[q0], [q1], [q2], [], [q0,q1], [q0,q2]}, = {a,b}, s = [q0], F = {[q0], [q0,q2], [qo,q1]}, dan : a [q1] [] [q0] [] [q0,q1] [q1] b [] [q0,q2] [] [] [] [q0,q2]

[q0] [q1] [q2] [] [q0,q2] [q0,q1]

FINITE AUTOMATA DENGAN TRANSISI HAMPA (-TRANSITION)Adalah NFA yang mempunyai transisi yang tidak bergantung dari suatu input tertentu. Atau dengan kata lain, dapat berpindah dari satu state ke state lain tanpa membaca input apapun. Contoh :



a

q

0

q 1

-CLOSERUntuk sebuah state q Q dari NFA M=(Q,,s,F,) dengan transisi-, didefinisikan penutup- (-closer) dari q dimana : -cl(q) = {p | p Q dan p dapat dicapai dari q tanpa input apapun} sedangkan

-cl({qi1 , qi2, qi3, , qik}) =

cl (qk =1

n

ik

)

dimana a ., qi Q. dan d(q,a) = {p | p Q dimana ada transisi dari q ke p dengan input a}

d ({qi1 , qi 2 ,..., qik }, a ) = (q ik , a) dk =1

n

Setiap state punya tran sisi- ke state itu sendiri, meskipun tidak digambarkan.

Eliminasi Transisi-Jika NFA M=(Q,,s,F,) dengan transisi-, maka terdapat NFA lain M=(Q,,s,F,) tanpa transisi- yang mendefinisikan bahasa yang sama dimana :

dan

(q,a) = -cl (d ( -cl (q), a))F = F { q | ( -cl(q) F) }b

Contoh 10 : Hilangkan transisi- dari NFA berikut :a

q 0

q 1

Dari gambar diatas kita dapat menentukan bahwa = {a,b}, F = {q1} dan d(q0,a) = {} -cl(q0) = {q0, q1} d(q0,b) = {q0} -cl(q1) = {q1} d(q1,a) = {q1} d(q1,b) = {} Maka : (1) (q0,a) -cl(q0) = {q0, q1} d({q0, q1},a) = d(q0,a) d(q1,a) = {} {q1} = {q1} -cl(q1) = {q1} maka (q0,a) = {q1}



(2) (q0,b) -cl(q0) = {q0, q1} d({q0, q1},b) = d(q0,b) d(q1,b) = {q0} {} = {q0} -cl(q0) = {q0, q1} maka (q0,b) = {q0, q1} (3) (q1,a) -cl(q1) = {q1} d(q1,a) = {q1} -cl(q1) = {q1} maka (q1,a) = {q1} (4) (q1,b) -cl(q1) = {q1} d(q1,b) = {} -cl({}) = {} maka (q1,a) = {} (5) F = {q1} {q0, q1} = {q0, q1}Jadi NFA tanpa transisi- adalah :b a, bq0 q0 q1

a

FINITE AUTOMATA & EKSPRESI REGULARJika r1 dan r2 adalah ekspresi regular yang mendefinisikan sebuah bahasa regular L, maka kita dapat membentuk sebuah NFA dari bahasa regular L tersebut, dimana (1) RE : FA :

(2) RE : FA :

(3) RE : r FA :r

(4) RE : r1 + r2



FA :r 1

r 2

(5) RE : r1.r2FA :r 1 r 2

(6) RE : r1*FA :

r 1

Jika diketahui RE sebuah bahasa regular L, maka kita dapat membentuk sebuah DFA yang menerima bahasa L dengan langkah-langkah : (1) Bentuklah NFA dengan transisi- dari RE tersebut (2) Eliminasi transisi- dari NFA di langkah (1) (3) Rubah NFA yang diperoleh di langkah (2) menjadi DFA Sebaliknya jika terdapat sebuah FA M = (Q,,s,F,) yang menerima bahasa L, maka kita dapat menentukan RE dari bahasa L dimana jika qj (qi,) dan maka terdapat persamaan :

Ai = A j | q j ( qi , )

dan A0 = L(M)

Lemma Arden : Persamaan X = AX + B ekivalen dengan X = A*.B

Contoh 11: Tentukan RE dari FA berikut



a bA0 A1

Kita dapatkan persamaan : A0 = aA0 + bA1 ..(1) A1 = .(2) Persamaan (2) disubstitusikan ke persamaan (1) sehingga : A0 = aA0 + b. A0 = aA0 + b (3) Menurut lemma Arden, persamaan (3) ekivalen dengan : A0 = a*.b RE yang mendefinisikan bahasa L, didapatkan dari A0. Jadi RE : a*b

EKIVALENSI DUA DFAJika M = (Q,,s,F,) adalah DFA yang menerima bahasa L dan M=(Q,,s,F,) adalah DFA yang menerima bahasa L, maka M dan M dikatakan ekivalen jika M dan M menerima bahasa yang sama (L = L). Kita dapat menentukan apakah dua DFA M dan M ekivalen dengan menggunakan algoritma Moore sebagai berikut, misalkan = {a,b}: (1) Setiap state dari M dan M diberi label/nama yang semuanya berbeda (tidak boleh ada duplikat label) (2) Buat tabel perbandingan yang terdiri dari N(3 karena jumlah symbol ada 2) kolom. Elemen dari tabel berbentuk pasangan (q,q) dimana qQ dan qQ. Sebagai inisial, pasangan (s,s) ditempatkan di kolom pertama baris pertama. (3) Tempatkan di kolom pertama, baris pertama pasangan (s,s). Dan di kolom kedua diisi dengan pasangan ((s,a),(s,a)) dan di kolom ketiga diisi dengan pasangan ((s,b), (s,b)) (4) Dari hasil langkah (3), jika elemen di kolom kedua dan kolom ketiga belum pernah muncul di kolom pertama, maka kita tempatkan di kolom pertama baris berikutnya. (5) Jika dalam proses muncul pasangan (q,q) dimana q F dan q F atau sebaliknya q F dan qF maka proses berhenti dan disimpulkan bahwa M dan M tidak ekivalen. (6) Proses berhenti dengan kesimpulan bahwa M ekivalen dengan M jika sudah tidak ada lagi pasangan baru yang ditempatkan di kolom pertama.

Contoh 12: Tentukan apakah dua DFA berikut ekivalen



a b1

a

4

5

b b b a2 3

b a b7 6

a b

a

a

Tabel perbandingan : a(1,4) (2,5) (3,6) (2,7) (1,4) (3,6) (2,7) (3,6)

b(2,5) (1,4) (3,6) (1,4)

Maka kedua DFA diatas ekivalen

MINIMIZE DFAMisalkan M = (Q,,s,F,) adalah sebuah DFA dengan n buah state, maka terdapat DFA lain M= (Q,,s,F,) yang mempunyai < n buah state, yang menerima bahasa yang sama dengan M. Untuk mendapatkan M yang jumlah statenya lebih minimum digunakan algoritma sebagai berikut : (1) Buat sebuah partisi yang mula-mula berisi dua kelas/grup. Kelas pertama berisi state akhir dan kelas kedua beranggotakan state-state yang bukan state akhir. (2) Untuk setiap grup dalam dipecah (split) menjadi subgrup-subgrup dimana state s dan t akan terletak dalam grup yang sama jika dan hanya jika dari state s dan t dengan input a akan menuju ke state yang terletak di grup yang sama (3) Proses berhenti jika sudah tidak ada lagi grup yang dapat dipecah. Contoh 13 : Minimalkan jumlah state dari DFA berikut :a aA B

b aC

a

bD

b bE

b

a

SOAL-SOAL



1.Tentukan RE dari bahasa regular berdasarkan = {a,b} berikut : (a) L = {abia | i 0 } (b) L = {(aa)i | i 0 }

(c) L = {(ab)ia | i 0 } (d) L = {aibj | i,j 0 } (e) Bahasa yang semua string didalamnya diakhiri dengan double b (f) Bahasa yang terdiri dari sebarang untai (g) Bahasa yang semua stringnya terdiri dari simbol b saja dengan panjang string ganjil. (h) Bahasa yang terdiri dari sebarang untai dengan panjang string genap. 2.Tentukan bahasa apa yang didefinisikan oleh RE berikut ini : (a) ab* (b) b*aa (c) (a+b)(a+b) (d) (a+b)*ab(a+b)*



BAB III Tata Bahasa (Grammar) Definisi Grammar terdiri dari 4 hal yaitu : 1. Suatu alfabet yang disebut terminal, T, yaitu sesuatu yang tidak dapat diganti atau diuraikan menjadi simbol lain 2. Himpunan simbol Nonterminal, N, yaitu simbol yang dapat diganti menjadi simbol-simbol lain. 3. Sebuah start simbol, S, merupakan elemen dari N. 4. Himpunan aturan penggantian yang disebut produksi, P, yang berbentuk , dimana , : sembarang barisan simbol terminal dan atau nonterminal. Macam-macam Grammar 1. Context Sensitive Grammar (Grammar tipe-1) yang mendefinisikan bahasa tipe-1 (bahasa context sensitive) 2. Context Free Grammar(Grammar tipe-2) yang mendefinisikan bahasa tipe-2 (bahasa context free) 3. Regular grammar (grammar tipe-3) yang mendefinisikan bahasa tipe-3 (bahasa regular) Derivasi Adalah proses pen urunan untuk mendapatkan suatu untai dengan menggunakan aturan produksi suatu grammar yang dimulai dari sebuah start simbol. Contoh 1: Diketahui grammar G = ( N = {S,E,A}; T = {a,b}; S = S; P ={ S aE; E A; AaA; Ab}) Lakukan proses derivasi untuk mendapatkan untai aab S aE aA aaA aab



GRAMMAR REGULAR Definisi Adl sebuah grammar G = (N,T,S,P) dengan produksi P berbentuk :

NONTERMINALAtauSEMIWORD

NONTERMINAL

WORD

Semiword : barisan terminal yang diakhiri dengan satu nonterminal (terminal)(terminal)(terminal)(Nonterminal) Word : barisan terminal (terminal)(terminal)(terminal) Contoh 2 : Grammar regular : A aaB | bbC B bB | b C cc | c Ekivalensi FA dengan grammar regular Misalkan M adalah sebuah FA dimana M = (,Q,s,F,) menerima bahasa L. Maka terdapat sebuah grammar G =(N,T,S,P) yang menerima bahasa L yang sama dimana : 1. N = Q 2. T = 3. S = s 4. P : Produksi (P) Transisi ( ) (X,a) = Y X aY F = {X} X Contoh 3: Diketahui FA = ({S,M,F},{a,b},S,{S,M},}b a a,b b a

S M F Tentukan grammar yang ekivalen dengan FA diatas Grammar : G = ({S,M,F},{a,b},S,P} P : S aS | bM | Materi Kuliah Teori Bahasa Dan Otomata Author : Fajar Astuti H, S.Kom

M aF | bS | F aF | bF Ekivalensi Grammar regular dengan FA Jika G = (N,T,S,P) adalah sebuah grammar regular, maka terdapat NFA M=(,Q,s,F,) yang menerima bahasa yang sama dengan bahasa yang didefinisikan oleh G. Dimana : 1. = T 2. Qmula-mula = N {f} ; f sebuah state baru. 3. s = S 4. F = {f} 5. : jika produksi berbentuk : A a1a2anB (semiword) maka ditambahkan (n-1) state baru : q1,q2,,qn-1 dengan transisi : (A,a1)=q1; (q1,a2)=q2; (qn-1,an) = Ba1 A q1 a2 an-1 qn-1 an B

jika produksi berbentuk : A a1a2an (word) maka ditambahkan (n-1) state baru : q1,q2,,qn-1 dengan transisi : (A,a1)=q1; (q1,a2)=q2; (qn-1,an) = fa1 A q1 a2 an-1 qn-1 an f

Contoh 4 : Tentukan FA dari grammar G = ({S,A,B},{a,b},S,P) dengan P : S aB | bA | A abaS B babS FA yang ekivalen terdiri dari : = T = {a,b}; Qmula-mula = N {f} = {S,A,B,f} s=S F = {f} : Produksi S aB S bA S A abaS

B babS

transisi (S,a) = B (S,b) = A (S,) = f (A,a) = q1 (q1,b) = q2 (q2,a) = S (B,b) = q3



(q3,a) = q4 (q4,b) = S

CONTEKS FREE GRAMMAR Definisi CFG adalah grammar dengan produksi berbentuk : dimana : sebuah Nonterminal dan : string terminal dan atau nonterminal. Contoh 5 : G = ({S,A,B},{a,b},S,P) dengan P : S ABA A aA | B bBb | Catatan : 1. Sebuah grammar regular pasti merupakan CFG 2. Sebuah CFG belum tentu grammar regular Macam Derivasi Derivasi dibedakan menjadi 2 yaitu : 1. Leftmost Derivation : penggantian Nonterminalnya dimulai dari Nonterminal yang paling kiri terlebih dahulu. 2. Rightmost Derivation : penggantian nonterminal dimulai dari nonterminal paling kanan. Contoh 6 : Dari grammar pada contoh 5 diatas lakukan leftmost derivation dan rightmost derivation untuk string : abbaa Leftmost derivation S ABA aABA aBA abBbA abbA abbaA abbaaA abbaa Rightmost derivation S ABA ABaA ABaaA ABaa AbBbaa Abbaa aAbbaa abbaa Parse Tree (Pohon Penguraian) Adalah sebuah pohon (tree) yang menggambarkan suatu proses derivasi dimana : Root : start simbol suatu grammar Branch node : simbol-simbol nonterminal yang diperoleh pada saat proses derivasi Leaf (daun) : simbol terminal Contoh 7 : Buatlah parse tree untuk string pada contoh 6 :SA B A



a A

b

B

b

a A aA

Grammar Ambiguous Adalah grammar dengan lebih dari satu parse tree untuk input yang sama. Contoh 8 : Tentukan parse tree dari grammar : S SbS | ScS | a untuk input abaca. Derivasi untuk input abaca : S SbS abS abScS abacS abaca Atau S ScS SbScS abScS abacS abaca Sehingga parse tree untuk input tersebut : S S a b S a S S S a Menentukan CFG dari RE b c S a S a S c S a

RE a a+b ab a* r1 + r2 r1r2 r1* Contoh 9 : Tentukan CFG dari RE : 1. RE : aa + bb CFG : S X | Y X aa

CFGS Sa Sa|b S ab S aS | SX|Y S XY S XS |



Y bb 2. RE : (a + b)* CFG : S XS | Xa|b 3. RE : a*bba* CFG : S XYX X aX | Y bb

atau S aS | bS |

Chomsky Normal Form (CNF) Produksi hampa (-production) Jika N sebuah Nonterminal maka produksi hampa (-production) adalah produksi yang berbentuk : N Definisi nonterminal nullable Sebuah Nonterminal N disebut Nullable jika : 1. Berbentuk N 2. Terdapat derivasi yang dimulai dari N dan mencapai suatu untai hampa ( N ) Replacement Rule (Aturan penggantian) Jika G adalah sebuah grammar yang mengandung produksi- maka terdapat grammar lain G yang tidak mengandung produksi- yang menerima bahasa yang sama dengan G, yang dapat ditentukan dengan aturan penggantian yaitu: 1. Hapus semua produksi- 2. Jika produksi dimana mengandung Nonterminal Nullable, tambahkan produksi baru dengan menggantikan Nonterminal Nullable di semua posisi A s1Ns2Ns3 dimana s1,s2,s3 : sembarang string N : nonterminal nullable Maka ditambahkan produksi : A s1s2Ns3 (N pertama diganti ) A s1Ns2s3 (N kedua diganti A s1s2s3 (N dikedua posisi diganti ) Contoh 9 : Tentukan grammar yang tidak mengandung produksi- dari grammar berikut: S a | Xb | aYa XY| Yb|X Jawab : 1. Menentukan nonterminal nullable - X nonterminal nullable, karena ada produksi X - Y nonterminal nullable, karena ada derivasi: Y X 2. Menghapus produksi- sehingga grammar diatas menjadi : S a | Xb | aYa XY



Y X/b 3. Menambahkan produksi baru : Produksi yang mengandung nonterminal nullable S Xb S aYa XY YX Maka grammar tanpa produksi- adalah : S a | Xb | aYa | b | aa XY Y X/b

Produksi baru Sb S aa -

Produksi unit (Unit Production) Jika A dan B nonterminal, maka produksi unit adalah produksi yang berbentuk : Satu Nonterminal Satu Nonterminal (A B) Jika G grammar yang mengandung produksi unit maka terdapat grammar G yang tidak mengandung produksi unit dan menerima bahasa yang sama dengan G yang dapat diperoleh dengan aturan eliminasi (Elimination Rule) yaitu : 1. Jika A B sebuah produksi unit dan terdapat produksi yang dimulai dari B yaitu B s1 | s2 | Maka pada grammar ditambahkan produksi : A s1 | s2 | 2. Jika A,B Nonterminal dan terdapat proses derivasi yang dimulai dari A dan berakhir di B : A X1 X2 B Dimana X1,X2 : Nonterminal dan terdapat produksi yang dimulai B : B s1 | s2 | Maka ditambahkan produksi : A s1 | s2 | 3. Hapus semua produksi unit Contoh 10 : Tentukan grammar yang tidak mengandung produksi unit yang ekivalen dengan grammar berikut : S A | bb AB|b BS|a Jawab : 1. Menentukan produksi unit Produksi unit Bukan produksi unit SA S bb AB Ab BS Ba 2. Menambahkan produksi baru Produksi baru



SA S A B AB A B S BS B S A

Sb Sa Aa A bb B bb Bb

Jadi grammar yang tidak mengandung produksi unit : S bb | b | a A b | a | bb B a | bb | b S A | bb AB|b BS|a Jika G adalah sebuah CFG dapat dirubah menjadi CFG lain yang ekivalen dan mempunyai produksi berbentuk : Nonterminal rangkaian Nonterminal Atau Nonterminal satu terminal Dengan cara : Mengganti setiap terminal dengan nonterminal baru. Misalkan produksi berbentuk : N a1a2a3 Dimana a1,a2,a3 adalah terminal, maka setiap terminal diganti dengan nonterminal baru misal X1,X2,X3, N X1X2X3 Menambahkan produksi baru, dari tiap nonterminal baru ke terminal yang digantikan : X1 a1 ; X2 a2 ; X3 a3

Contoh 11 : Rubah CFG berikut menjadi bentuk Nonterminal rangkaian nonterminal ; atau Nonterminal satu terminal. S X | YaY | aSb | b X YY | b Y aY | aaX Jawab : Produksi yang dirubah Produksi pengganti Produksi baru S YaY S YAY Aa S aSb S ASB Aa;Bb Y aY Y AY Aa Y aaX Y AAX Aa Jadi CFG baru yang didapat adalah sbb :



S X | YAY | ASB | b X YY | b Y AY | AAX Aa Bb Jika G adalah sebuah CFG dapat dirubah menjadi CFG lain yang ekivalen dan mempunyai produksi berbentuk : Nonterminal dua Nonterminal Atau Nonterminal satu terminal Dengan cara : Mengganti rangkaian Nonterminal pada posisi kedua dan seterusnya dengan sebuah nonterminal baru. Misal terdapat produksi : N X1X2X3; dimana X1,X2,X3 : Nonterminal maka produksi tsb dirubah menjadi : N X1R1 Menambah produksi baru dari nonterminal baru ke rangkaian Nonterminal yang digantikan, yaitu R1 X2X3

Contoh 12 : Rubah CFG berikut menjadi bentuk Nonterminal dua Nonterminal atau Nonterminal satu terminal S YAY | ASB | b X YY | b Y AY | AAX Aa Bb Jawab : Produksi yang diganti Produksi pengganti Produksi baru S YAY S YR1 R1 AY S ASB S AR2 R2 SB Y AAX Y AR3 R3 AX Jadi CFG baru yang diperoleh : S YR1 | AR2 | b X YY | b Y AY | AR3 R1 AY R2 SB R3 AX A a Bb S YAY | ASB | b X YY | b Y AY | AAX



Aa Bb Definisi Chomsky Normal Form (CNF) Adalah sebuah CFG yang mempunyai produksi berbentuk : Satu Nonterminal Dua Nonterminal Atau Satu Nonterminal satu terminal

a.

b.

c.

Langkah langkah merubah CFG menjadi CNF 1. Jika terdapat produksi-, hilangkan dengan replacement rule 2. Jika terdapat produksi unit, hilangkan dengan elimination rule 3. Rubah menjadi bentuk : Satu Nonterminal rangkaian Nonterminal ;atau Satu Nonterminal satu terminal 4. Rubah menjadi bentuk : Satu Nonterminal Dua Nonterminal ;atau Satu Nonterminal satu terminal Contoh 13 : Tentukan CNF dari CFG berikut : S AB AB B aB | Bb | Langkah-langkahnya : 1. Menghapus produksi- Nonterminal nullable adalah A dan B karena: B A B Menghapus produksi- sehingga menjadi : S AB AB B aB | Bb Menambah produksi baru : Produksi yang mengandung Produksi baru nonterminal nullable S AB SB SA AB B aB Ba B Bb Bb Jadi CFG1 baru : S AB | B | A AB B aB | Bb | a | b 2. Menghapus produksi unit dari CFG1



a.

Menentukan produksi unit Produksi Unit SA SB AB Menambah produksi baru : S A B atau SB AB Jadi CFG2 baru : S AB | aB | Bb | a | b A aB | Bb | a | b B aB | Bb | a | b

Bukan Produksi unit S AB B aB | Bb | a | b Produksi baru S aB | Bb | a | b A aB | Bb | a | b

b.

3. Merubah CFG2 menjadi bentuk rangkaian Nonterminal Produksi yang diganti Produksi pengganti Produksi baru S aB S XB Xa S Bb S BY Yb A aB A XB Xa A Bb A BY Yb B aB B XB Xa B Bb B BY Yb Jadi CNF yang didapat : S AB | XB | BY | a | b A XB | BY | a | b B XB | BY | a | b X->a Y->b



BAB IV Pushdown Automata (PDA) Definisi Pushdown automata terdiri dari 8 hal yaitu : 1. Himpunan alfabet sebagai input () 2. Sebuah input tape, yang mula-mula berisi string input diikuti beberapa simbol blank ( atau ). 3. Himpunan karakter stack () 4. Sebuah pushdown stack, yang mula-mula kosong. 5. Sebuah state awal (START) START 6. Beberapa state pemberhentian yaitu ACCEPT dan REJECT ACCEPT 7. Beberapa state PUSH PUSH X 8. Beberapa state percabangan : a. State READ : membaca input tape berikutnya. REA D b. State POP : membaca karakter di top of stack. POPMateri Kuliah Teori Bahasa Dan Otomata Author : Fajar Astuti H, S.Kom

REJECT

Contoh 14 :START

PUSH a

A

a

READ 1

b b b, POP1 aREAD 2

a,b POP2 ACCEPT REJECT

a REJECT REJECT

Analisa bagaimana PDA diatas menerima input : aaabbb StateSTART READ1 PUSH a READ1 PUSH a READ1 PUSH a READ1 POP1 READ2 POP1 READ2 POP1 READ2 POP2 ACCEPT

Input Tape aaabbb aaabbb aabbb aabbb abbb abbb bbb bbb bb bb b b

Stack a a aa aa aaa aaa aa aa a a

Ekivalensi PDA dan FA Jika diketahui sebuah FA M = (,Q,s,F,) maka terdapat sebuah PDA tanpa stack yang menerima bahasa yang sama Contoh 15: Tentukan PDA dari FA berikut : b B a a A PDA :START

A A

b

Read A

Materi Kuliah Teori Bahasa Dan OtomataREJECT

Read B

ACCEPT


b b a

a

Nondeterministik PDA Adalah suatu PDA dimana pada state percabangan terdapat transisi keluar dengan input yang sama ke state yang berbeda. Ekivalensi CFG dan PDA Jika L adalah bahasa yang didefinisikan oleh sebuah CFG, maka ada PDA yang menerima bahasa L tersebut. Adapun cara merubah CFG menjadi PDA sebagai berikut : 1. CFG dirubah ke bentuk CNF 2. Jika X1 sebuah start simbol maka :START

PUSH X1

POP

3. Jika Xi, Xj, Xk adalah nonterminal dan terdapat produksi : Xi XjXkPOP Xi PUSH X

k

PUSH Xj

4. Jika Xi : Nonterminal ; b : terminal dan terdapat produksi : Xi bb REA D Xi

POP

Contoh 16 : Tentukan PDA dari CFG berikut : S AB A BB | aMateri Kuliah Teori Bahasa Dan Otomata Author : Fajar Astuti H, S.Kom

B AB | a | b aSTART PDA : REA D

aREA D

bREA D

APUSH S

BPOP

B BPUSH BREA D

ACCEPT

SPUSH B

APUSH B

PUSH A

PUSH B

PUSH A

CONTEXT FREE LANGUAGE Jika L1 dan L2 merupakan CFL, maka L1+L2 juga merupakan CFL Dengan grammar Jika G1 = (N1,T1,S1,P1) adalah CFG yang mendefinisikan L1 dan G2=(N2,T2,S2,P2) adalah CFG yang mendefinisikan L2, maka L1+L2 didefinisikan oleh CFG : S S1 | S2 G1 (dengan subscript 1 di setiap nonterminal) G2 (dengan subscript 2 di setiap nonterminal) Contoh 17 : - L1 dinyatakan dengan CFG1 sbb : S1 aS1a | bS1b | a | b | - L2 dinyatakan dengan CFG2 sbb : S2 aS2b | - maka L1+L2 dinyatakan dengan CFG sbb : S S1 | S2 S1 aS1a | bS1b | a | b | S2 aS2b | Dengan PDA : Jika PDA1 menerima bahasa L1 dan PDA2 menerima bahasa L2 maka terdapat sebuah PDA yang menerima bahasa L1+L2 dimana : PDA1 dimulai dengan : PDA2 dimulai dengan:START START

Maka PDA untuk L1+L2 dimulai dengan :START



Contoh 18: - PDA1 :START

PUSH a

a

REA D

a

POP

a

ACCEPT

bPUSH b

- PDA2 :STARTREA D

a

ACCEPT

- PDA untuk L1+L2 :START REA D

a

PUSH a

a

REA D

a

POP

a

ACCEPT

bPUSH b

Jika L1 dan L2 adalah CFL maka L1L2 juga sebuah CFL Dengan grammar Jika G1 sebuah CFG yang mendefinisikan L1 dan G2 adalah CFG yang mendefinisikan bahasa L2, maka terdapat CFG yang mendefinisikan bahasa L1L2 dimana : S S1S2 G1 (dengan subscript 1 di setiap nonterminal) G2 (dengan subscript 2 di setiap nonterminal) Contoh 19: - L1 dinyatakan dengan CFG1 sbb : S aSa | bSb | a | b | - L2 dinyatakan dengan CFG2 sbb : S aSb | - maka L1L2 dinyatakan dengan CFG sbb : S S1S2 S1 aS1a | bS1b | a | b |



S2 aS2b | Dengan PDA Jika PDA1 menerima bahasa L1 dan PDA2 menerima bahasa L2 maka terdapat sebuah PDA yang menerima bahasa L1L2 dimana : PDA1 diakhiri dengan : PDA2 diakhiri dengan:ACCEPT START

Maka PDA yang menerima bahasa L1L2 :

Contoh 20 : - PDA1 :STARTREA D

a

ACCEPT

- PDA2 :START

aPUSH a

REA D

aPOP

aACCEPT

bPUSH b

- PDA untuk L1L2 :STARTREAD

a

PUSH a

a

REA D

a

POP

a

ACCEPT

PUSH b

b



Jika L1 adalah CFL maka L1* juga sebuah CFL Dengan grammar Jika G1 sebuah CFG yang mendefinisikan L1, maka terdapat CFG yang mendefinisikan bahasa L1* dimana : S S1S G1 (dengan subscript 1 di setiap nonterminal) Contoh 21: - L1 dinyatakan dengan CFG1 sbb : S aSa | bSb | a | b | - maka L1* dinyatakan dengan CFG sbb : S S1S S1 aS1a | bS1b | a | b |

BAB V Turing Machines Definisi Sebuah mesin turing (turing machine), TM, terdiri dari 6 hal yaitu : 1. Sebuah himpunan alfabet sebagai input 2. Sebuah tape yang terdiri dari tak hingga sel, dimana masing-masing sel dapat berisi sebuah karakter atau blank simbol (). Mula-mula tape berisi string input, mulai dari sel paling kiri dan diakhiri simbol blank 3. Sebuah tape head , yang tugasnya : - membaca isi sel tape - mengganti isinya dengan karakter lain - bergerak ke sel berikut, satu langkah, ke kiri atau ke kanan. Mula-mula tape head terletak di sel paling kiri. 4. Sebuah himpunan karakter, , yang dapat dicetak tape head ke dalam tape 5. Sebuah himpunan terhingga dari state, termasuk didalamnya sebuah state awal (START), dan beberapa state akhir / pemberhentian (HALT) 6. Sebuah program, yang merupakan himpunan aturan yang berisi informasi: - apa yang harus dibaca tape head - karakter apa yang akan dicetak ke tape - tape head harus bergerak kemana berbentuk : (x1, x2, arah) Keterangan : x1 : elemen dari atau atau berupa (blank), yang menunjukkan karakter apa yang dibaca tape head. x2 : elemen dari atau berupa (blank), yang menunjukkan karakter apa yang dicetak ke tape menggantikan x1. Arah : R (Right) : bergerak ke kanan satu langkah L (Left) : bergerak ke kiri satu langkah Contoh 22 :



Mesin Turing yang menerima bahasa (a+b)b(a+b)* (a,a,R)START 1

(b,b,R) 2 3

(,,R)HALT 4

(a,a,R) (b,b,R) Cara kerja mesin turing diatas menerima kata aba State Tape START 1 aba 2 aba 3 aba 3 aba HALT 4 aba

(b,b,R)

Soal soal1. Dari CFG berikut : S aS | bb Tunjukkan bahwa CFG tersebut mendefinisikan bahasa a*bb 2. Dari CFG berikut : S XYX X aX | bX | Y bbb Tunjukkan bahwa CFG tersebut mendefinisikan bahasa (a+b)*bbb(a+b)* 3. Dari CFG berikut : S aX X aX | bX | Tentukan bahasa apa yang didefinisikan CFG diatas ? 4. Dari CFG berikut : S XaXaX X aX | bX | Tentukan bahasa apa yang didefinisikan CFG diatas ? 5. Tentukan CFG untuk tiap-tiap bahasa berikut : (i) ab* (ii) a*b* (iii) (baa + abb)* 6. Gambarkan parse tree untuk masing-masing CFG berikut : CFG 1 : S aSb | ab CFG 2 : S aS | bS | a CFG 3 : S aS | aSb | X X aXa | a CFG 4 : S aAS | a A SbA | SS | ba



CFG 5 : S aB | bA A a | aS | bAA B b | bS | aBB Untuk input : ab, aaaa, aabb, abaa, abba, baaa, abab, bbaa, baab. 7. Tunjukkan bahwa CFG berikut ambigious dengan menemukan sebuah input yang mempunyai dua parse tree yang berbeda. (i) S SaSaS | b (ii) S aSb | S b | Sa | a (iii) S aaS | aaaS | a (iv) S aS | aSb | X X Xa | a 8. Tentukan CFG untuk bahasa regular berikut ini untuk = {a,b}: (i) bahasa yang didefinisikan dengan RE : (aaa + b)* (ii) bahasa yang didefinisikan dengan RE : (a+b)*(bbb+aaa)(a+b)* (iii) bahasa yang semua katanya diakhiri dengan b. (iv) bahasa yang semua katanya punya panjang kata ganjil. (v) Bahasa yang semua katanya terdiri dari a saja dengan panjang ganjil atau b saja dengan panjang genap. 9. Tentukan RE dan FA dari bahasa yang didefinisikan oleh CFG berikut : (i) S aX | bS | a | b X aX | a (ii) S bS | aX | b X bX | aS | a (iii) S aaS | abS | baS | bbS | (iv) S aB | bA | A aS B bS (v) S aB | bA A aB | a B bA | b (vi) S aS | bX | a X aX | bY | a Y aY | a (vii) S aS | bX | a X aX | bY | bZ | a Y aY | a Z aZ | bW W aW | a (viii) S bS | aX X bS | aY Y aY | bY | a | b 10. Untuk tiap-tiap CFG berikut tentukan CFG lain yang tidak mengandung produksi hampa. (-production) (i) S aX | bX Xa|b| (ii) S aX | bS | a | b



X aX | a | S aS | bX X aX | (iv) S XaX | bX X XaX | XbX | 11. Untuk tiap-tiap CFG berikut tentukan CFG lain yang tidak mengandung produksi unit (i) S aX | Yb XS Y bY | b (ii) S AA A B | BB B abB | b | bb (iii) S AB AB B aB | Bb | 12. Rubah CFG berikut ke dalam bentuk CNF (i) S SS | a (ii) S aSa | Ssa | a (iii) S aXX X aS | bS | a (iv) EE+E EE*E E (E) E7 (v) S ABABAB Aa| Bb| (vi) S SaS | SaSbS | SbSaS | (vii) S AS | SB A BS | SA | a B SS | b (viii) S X XY YZ Z aa (ix) S SS | A A SS | AS | a 13. Tentukan leftmost derivation untuk kata abba dari grammar berikut : S AA A aB B bB | 14. Tentukan leftmost derivation untuk kata abbabaabbbabbab dari CFG : S SSS | aXb X ba | bba | abb 15. Rubah FA berikut menjadi PDA : (i) a (iii)Materi Kuliah Teori Bahasa Dan Otomata Author : Fajar Astuti H, S.Kom

a b b a b b

a (ii) b a a b b b a a

16. Dari PDA berikut ini periksalah apakah input string berikut diterima oleh PDA tersebut : (i) abb (ii) abab (iii) aabb (iv) aabbbbSTART

ACCEPT

READ 1

aPUSH a

bREJECT

a

READ 2

REJECT

bREJECT STARTREAD 3

a,

REJECT

ACCEPT

a,b

READ 1

bREAD 4

a

PUSH a

b b,POP

POP

ACCEPT

a

READ 2

REJECT

17. Dari PDA berikut :POP1

aREAD 3

POP2


Author : Fajar Astuti H, S.KomACCEPT

a b

a,b

Tentukan apakah kata-kata berikut diterima oleh PDA tersebut : (i) aaabbb (ii) aaabab (iii) aaabaa (iv) aaaabb 18. Rancanglah sebuah PDA yang menerima bahasa : (i) L = {anb2n | n 1} (ii) L = {a2nbn | n 1} (iii) L = {an+1bn | n 1} (iv) L = {anbn+1 | n 1} 19. Tentukan PDA yang menerima bahasa yang sama dengan CFG berikut : (i) S aSbb | abb (ii) S SS | a | b (iii) S XaaX X aX | bX | (iv) S aS | aSbS | a (v) S XY X aX | bX | a Y Ya | Yb | a (vi) S Xa | Yb X Sb | b Y Sa | a 20. Tentukan CFG yang mendefinisikan bahasa-bahasa berikut untuk = {a,b} : (i) bahasa yang terdiri dari semua kata yang dimulai dengan a atau berbentuk anbn untuk n 1 (ii) bahasa yang terdiri dari semua kata yang dimulai dengan b atau berbentuk anbn untuk n 1 (iii) bahasa yang semua katanya berbentuk anbnambm dimana n,m 1 (iv) bahasa yang semua katanya berbentuk axbyaz dimana n,m 1 dan x+z =y (v) bahasa yang semua katanya berbentuk anb2namb2m dimana n,m 1 21. (i) Tentukan CFG untuk bahasa



L = a(bb)* (ii) Tentukan CFG untuk bahasa L* 22. Dari TM berikut ini :(a,a,L) (b,b,L) 7 (#,#,R) (b,#,R) (a,a,R),(b,b,R) (a,a,L),(b,b,L) 6 (b,#,L),(a,#,L) 5 (,,L) (#,#,L)2

START1

4

(a,a,R) (b,b,R)

(a,#,R) 3 (#,#,R) (,,R) HALT

(a,a,R) (b,b,R)

Tentukan apakah input string berikut diterima oleh TM tersebut : (i) aaa (iii) baaba aba (iv) ababb

1. Tentukan CFG dari a*bb 2. Tentukan CFG dari (a+b)*bbb(a+b)* 3. Hilangkan produksi dibawah ini S -> aB/A/aAbB B -> aSb/bA/ A -> B/aS/bAaB 4. Tentukan RG dari FA dibawah inia aA B

b aC

a

bD

b bE

b

a



handout automata

Documents