Transcription

Modul PraktikumTeori Bahasa & OtomataLanguageFiniteAutomataContext yNormal FormOleh:Sri HandayaningsihAndri Pranolo

Sejarah Revisi Modul Praktikum Teori Bahasa AutomataNo1TahunRevisi2017RevisiPenggunaan tool JFLAP

Detail Sejarah Revisi Modul Praktikum Teori Bahasa AutomataModul Revisi ke 1 tahun 2016Modul Revisi ke 2 tahun 2017Pertemuan I. Pengolahan StringPertemuan I. Pengolahan StringPertemuan II. Pengolahan String IIPertemuan II. Pengolahan String IIPertemuan III. Operasi pada BahasaPertemuan III. Operasi pada BahasaPertemuan IV. Finite State Authomata(FSA)Pertemuan IV. Finite State Automata(FSA) dengan JFLAPPertemuan V. Deterministic FiniteAutomataPertemuan V. NonDeterministic FiniteAutomat.Pertemuan VI. NonDeterministic FiniteAutomataPertemuan VI. Deterministic FiniteAutomataPertemuan VII. NFA dengan transisiEpsilonPertemuan VII. Pushdown AutomataPertemuan VIII. Chomsky Normal FormPertemuan VIII. Chomsky Normal FormPertemuan IX. Penghilangan Rekursif KiriPertemuan IX. Penghilangan Rekursif KiriPertemuan X. Normal Greibac.Pertemuan X. Normal GreibachYogyakarta, Agustus 2017Penulis

Daftar IsiHalaman Revisi . iDaftar Isi iiPertemuan I. Pengolahan String . .1Pertemuan II. Pengolahan String II 7Pertemuan III. Operasi pada Bahasa .12Pertemuan IV. Finite State Automata (FSA) dengan JFLAP . 18Pertemuan V. NonDeterministic Finite Automata . .26Pertemuan VI. Deterministic Finite Automata . .31Pertemuan VII. Pushdown Autoamta 36Pertemuan VIII. Chomsky Normal Form .41Pertemuan IX. Penghilangan Rekursif Kiri .45Pertemuan X. Normal Greibach .49

Pengolahan StringPertemuan: IAlokasi Waktu: 1,5 jamKompetensi Dasar:1. Mahasiswamampumembuatrancanganinterface untuk pengolahan string denganmenggunakan visual programming2. Mahasiswa mampu memahami algoritam daripengolahan string dalam hal ini panjang string,Reverse dan ConcatenationIndikator:1. Mahasiswa mampu membuat interface denganmenggunakan visual programming2. Mahasiswa mampu membuat fungsi se, dan concatenationA. Dasar TeoriTerminologi dasar yang penting dalam memahami teori bahasa adalahalphabet, penyambungan (Contatenation) dan string pada alphabet V.alphabet digunakan untuk membentuk kata-kata di bahasa. Pada beberapabuku alphabet dilambangkan dengan .Kumpulan alphabet atau symbol disebut string. Ada banyak operasipengolahan yang bisa dilakukan pada string yaitu contetenation, panjangstring dan pembalikan (reverse).1. Concatenation : penyambungan 2 karakter atau lebih membentuk suatubarisan karakter.2. Panjang string : proses penghitungan jumlah karakter yang dimuat dalamsuatu string3. Reverse : pembalikan stringMisalnya u abbbba1

v bbbbbauv abbbbabbbbba (penyambungan), uv u v 6 6 12 (panjang string)(uv)R (abbbbabbbbba)R abbbbbabbbbaB. Langkah Praktikum1. Buka program visual programming (dalam modul ini menggunakanBorland Delphi 7).2. Buat Desain form seperti gambar 1.112435Gambar 1.1 . Desain form pengolahan stringNoNama variable1 Label2Edit3Checkbox4Memo5ButtonPropertiesPosisi Tab standardCaption : diubah sesuai kebutuhanPosisi tab standardName : sesuaikan dengan input datanyaPosisi tab standardCaption : ubah sesuai dengan permintaanPosisi tab standardName : sesuaikan dengan kegunaan (missalmemohasil)Lines : hapus semua teks yang ada didalamnyaPosisi Tab standardCaption : disesuai dengan kebutuhanName : sesuai dengan nama caption2

3. Jika desain form sudah selesai dilakukan masukkan coding di bawah ini :Prosedur untuk menghitung panjang stringprocedure TfrmUtama.Panjangstring;vari: Integer;beginu : edtstringu.Text;v : edtstringv.Text;if chkpenyambungan.Checked thenbeginmmohasil.Lines.Add(' uv u v ' IntToStr(Length(uv)))endelse beginmmohasil.Lines.Add(' u ' IntToStr(Length(u)));mmohasil.Lines.Add(' v ' IntToStr(Length(v)));end;end;Prosedur untuk proses pembalikan pada stringprocedure TfrmUtama.Pembalikan;varpanjangu, panjangv: Integer;i,j, total: Integer;beginu : edtstringu.Text;v : edtstringv.Text;panjangv : length(v);panjangu : length(u);total : Length(uv);if chkpenyambungan.Checked thenbeginedttampung.Text : '';for i : 0 to Length(uv) dobeginedttampung.Text : edttampung.Text '' uv[total - i];end;mmohasil.Lines.Add('hasil pembalikan string penyambungan uv ' edttampung.Text);3

endelse beginedttampung.Text : '';for i: 0 to Length(v) dobeginedttampung.Text : edttampung.Text '' v[panjangv - i];end;mmohasil.Lines.Add('hasil pembalikan string v ' edttampung.Text);edttampung.Text : '';for j: 0 to Length(u) dobeginedttampung.Text : edttampung.Text '' u[panjangu - j];end;mmohasil.Lines.Add('hasil pembalikan string u ' edttampung.Text);end;end;Prosedur Penyambunganprocedure TfrmUtama.Penyambungan;beginu : edtstringu.Text;v : edtstringv.Text;if chkpenyambungan.Checked thenbeginuv : u '' v;mmohasil.Lines.Add('hasil penyambungan string (uv) ' uv);endelse beginmmohasil.Lines.Add('Tidak ada Penyambungan string')end;end;4

4. Tekan F9 atau tombol rununtuk menjalankan program5. Coba masukkan 2 buah string dan lihat hasilnya cocokkan dengan hasilmanualnya (contoh di bawah ini)Gambar 1.2. form pengolahan string dengan contoh outputC. Tugas PraktikumBuat program untuk melakukan pembalikan dan untuk menghitung panjang 3buah string dengan ketentuan sebagai berikut u aaaabbbbb , v bbbbcccca ,w ccccbbbbaaa5

NilaiYogyakarta, .Paraf asisten Jawaban Postest6

Pengolahan String 2Pertemuan: IIAlokasi Waktu: 1,5 jamKompetensi Dasar:1. Mahasiswamampumembuatrancanganinterface untuk pengolahan string denganmenggunakan visual programming2. Mahasiswa mampu memahami algoritma daripengolahan string dalam hal ini Prefix, Suffix,Star Clouser dan Positif ClouserIndikator:1. Mahasiswa mampu membuat interface denganmenggunakan visual programming2. Mahasiswa mampu membuat fungsi pengolahanstring untuk Prefix, Suffix, Star Clouser danPositif ClouserA. Dasar TeoriSelain operasi penyambungan dan pembalikan ada beberapa operasi dasarpada string diantaranya Prefix, suffix, star clouser dan positif clouser.Prefix string w adalah string yang dihasilkan dari string w dengan menghilangkannol atau lebih simbol-simbol paling belakang dari string w tersebut.Contoh : abc, ab, a, dan e adalah semua Prefix(x)Postfix (atau Suffix) string w adalah string yang dihasilkan dari string wdengan menghilangkan nol atau lebih simbol-simbol paling depan dari stringw tersebut.Contoh : abc, bc, c, dan e adalah semua Postfix(x).Bahasa UniversalJika adalah alphabet, kita menggunakan * untuk menotasikan himpunanstring(bahasa universal) yang dihasilkan oleh penggabungan nol atau lebih7

symbol . * selalu mengandung λ agar bisa mengeluarkan string yangkosong. Sedangkan tidak mengandung string kosong λ atau *- λ.Contoh * { λ ,a,aa,aaa,aaaa, } { a,aa,aaa,aaaa, }B. Petunjuk Praktikum1. Buka program visual programming (dalam modul ini menggunakanBorland Delphi 7).2. Buat Desain form seperti gambar 2.112435Gambar 2.1. Desain form pengolahan stringNo Nama variable1 Label2Edit3Checkbox4Memo5ButtonPropertiesPosisi Tab standardCaption : diubah sesuai kebutuhanPosisi tab standardName : sesuaikan dengan input datanyaPosisi tab standardCaption : ubah sesuai dengan permintaanPosisi tab standardName : sesuaikan dengan kegunaan (missalmemohasil)Lines : hapus semua teks yang ada di dalamnyaPosisi Tab standardCaption : disesuai dengan kebutuhanName : sesuai dengan nama caption8

3. Jika desain form sudah selesai dilakukan masukkan coding di bawah ini :Prosedur untuk membuat Prefix dari stringprocedure TfrmUtama.prefixmethod(karakter : string);vari: Integer;beginedttemplate.Text : '';mmohasil.Lines.Add('Hasil Prefix string ' ------------');for i : 0 to Length(karakter) dobeginedttemplate.Text : edttemplate.Text '' ----');end;Prosedur membuat starclouser dari stringprocedure TfrmUtama.starmethod(karakter : string;ulang : integer);vari: Integer;beginedttemplate.Text : '';mmohasil.Lines.Add('Hasil Operasi StarClouser -----');mmohasil.Lines.Add('');for i : 0 to ulang-1 dobeginedttemplate.Text : edttemplate.Text '' --');end;4. Tekan F9 atau tombol rununtuk menjalankan program5. Coba masukkan sebuah string dan lihat hasilnya cocokkan dengan hasilmanualnya (gambar 2.2)Gambar 2.2. form program ketika sudah di run9

C. Tugas PraktikumKembangkan program di atas, buat fungsi Suffix dan Positif clouser.Tentukan hasilnya untuk string :1. baababb2. aaaaabbbab3. babababbba4. acacccaa(fungsi dan hasil dari pengolahan string di tuliskan di modul)10

NilaiYogyakarta, .Paraf asisten Jawaban Postest11

Operasi BahasaPertemuan: IIIAlokasi Waktu: 1,5 jamKompetensi Dasar:1. Mahasiswamampumembuatrancanganinterface untuk pengolahan string denganmenggunakan visual programming2. Mahasiswa mampu memahami algoritma darioperasi 2 buah bahasa. Dalam hal ini Union,intersection, difference, concatenation, reverseIndikator:1. Mahasiswa mampu membuat interface denganmenggunakan visual programming2. Mahasiswa mampu membuat fungsi atenation, reverseA. Dasar TeoriBahasa adalah subset dari *Contoh: a, b * , a, b, aa, ab, ba, bb, aaa, Bahasa: a, aa, aab { , abba, baba, aa, ab, aaaaaa}Bahasa Tidak TerbatasL {a nb n : n 0} abaabb Labb Laaaaabbbbb12

Operasi dalam bahasaOperasi-operasi pada bahasa tidak jauh berbeda dengan operasi-operasi padastring. Ada Reverse, concatenation dan lain sebagainya. Selain itu juga samadengan operasi pada himpunan Union, Intersection danDiffrenceMenggunakan operasi himpunan : a, ab, aaaa bb, ab {a, ab, bb, aaaa} a, ab, aaaa bb, ab {ab} a, ab, aaaa bb, ab a, aaaa L * LComplement: a, ba , b, aa, ab, bb, aaa, ReverseDefinisi:LR {w R : w L}Contoh: ab, aab, baba R ba, baa, abab L {a n b n : n 0}LR {b n a n : n 0}ConcatenationDefinisi :L1 L2 xy : x L1 , y L2 Contoh a, ab, ba b, aa ab, aaa, abb, abaa, bab, baaa B. Petunjuk Praktikum1. Buka program visual programming(dalam modul menggunakan BorlandDelphi 7)2. Desain form seperti di bawah ini (gambar 3.1)13

Gambar 3.1. desain form aplikasi pembuatan bahasaNoNama variable1 Label2Edit3Checkbox4Memo5ButtonPropertiesPosisi Tab standardCaption : diubah sesuai kebutuhanPosisi tab standardName : sesuaikan dengan input datanyaPosisi tab standardCaption : ubah sesuai dengan permintaanPosisi tab standardName : sesuaikan dengan kegunaan (missalmemohasil)Lines : hapus semua teks yang ada didalamnyaPosisi Tab standardCaption : disesuai dengan kebutuhanName : sesuai dengan nama caption3. Buat fungsi untuk proses union dan intersection4. Tekan F9 atau tombol rununtuk menjalankan program5. Coba masukkan sebuah string dan lihat hasilnya cocokkan dengan hasilmanualnya (contoh di bawah ini)14

Gambar 3.2. contoh hasil pengolahan pada bahasa (operasi penggabungan)Prosedur lengkap proses union (penggabugan 2 bahasa)procedure Tfrmutama.memecahkanbahasa(kata : string);varj: Integer;i: Integer;stringdata: string;beginj : 0;for i : 1 to Length(kata) 1 dobeginif (kata[i] ',') and (kata[i] '') thenbeginstringdata : stringdata '' kata[i];endelse beginlstdata.Items.Strings[j] : stringdata;Inc(j);stringdata: '';end;end;end;15

procedure Tfrmutama.Union;vark: Integer;j: Integer;hasilgabung: string;stringdata: string;i: Integer;beginfor i : lstdata.Items.Count - 1 downto 0 dobeginif lstdata1.Items.IndexOf(lstdata.Items[i]) 0 thenlstdata.Items.Delete(i);end;hasilgabung : l Penggabungan 2 bahasa');for j : 1 to lstdata.Items.Count - 1 dobeginif lstdata.Items.Strings[j] '' thenhasilgabung : hasilgabung ' , ' lstdata.Items.Strings[j];end;for k : 0 to lstdata1.Items.Count - 1 dobeginhasilgabung : hasilgabung ' , ' asilgabung);hasilgabung: ''end;C. Tugas PraktikumDari program di atas tambahkan fungsi untuk proses Concatenation. Cekhasilnya untuk bahasa di bawah ini:1. L1 {ab,bba} dan L2 {bb,aba}2. L1 {ac, bc} dan L3 {bc, ab, ac}16

NilaiYogyakarta, .Paraf asisten Jawaban Postest17

Finite State Automata (FSA) dengan JFLAPPertemuan: IVAlokasi Waktu: 1,5 jamKompetensi Dasar:1. Mahasiswa mampu memahami Finite StateAutomata dalam JFLAP2. Mahasiswa mampu memahami algoritma FiniteState AutomataIndikator:1. Mahasiswa mampu membuat simulasi FSAdengan JFLAP2. Mahasiswa mampu menjelaskan hasil simulasiFSA dengan JFLAPA. Dasar TeoriFinite automata adalah mesin abstrak berupa sistem modelmatematika dengan masukan dan keluaran diskrit yang dapat mengenalibahasa paling sederhana (bahasa reguler) dan dapat diimplementasikan secaranyata dimana sistem dapat berada disalah satu dari sejumlah berhinggakonfigurasi internal disebut state. State sistem merupakan ringkasan informasiyang berkaitan dengan masukan-masukan sebelumnya yang diperlukan untukmenentukan perilaku sistem pada masukan-masukan berikutnya.Finite Automata menggunakan prosedur yang saat diberikan masukan"string berhingga" akan berhenti. Finite Automata menyatakan "ya" dengansejumlah berhingga komputasi jika string tersebut merupakan elemen bahasasehingga lebih berfokus pada pengenalan dimana bila diberikan suatuprogram (string) akan menyatakan apakah string tersebut termasuk di bahasaatau tidak.JFLAP mendepfinsikan sebuah a Finite State Automata (FA) Msebagai quin tupel, M (Q, Σ, δ, qs/S, F) dimana18

1. Q adalah sebuah himpunan finite states {qi I merupakan non-negatifinteger}2. himpunan symbol input berupa alphabet3. δ fungsi transisi, δ : D 2Q dimana D adalah sub himpunan finite statedari Q Σ*4. qs merupakan anggota himpunan Q, menunjukan initial state.5. F adalah sub himpunan dari Q, merupakan state-state akhir.B. Petunjuk Praktikum1. Lakukan instalasi JFLAP2. Jalankan JFLAP sehingga muncul halaman Utama JFLAP seperti Nampakpada Gambar 4.1.Gambar 4.1. Tampilan rancangan form FSA19

3. Pilih Finite Automata, maka akan tampil laman untuk simulasi FinitaAutomata seperti tampak pada gambar 4.2.Undo dan redo (untuk mengembalikan perintah)Untuk menghapus objekUntuk membuat transisi antar stateUntuk membuat stateHalaman CanvasEditor attributeGambar 4.2. Halaman utama simulasi Finite Automata4. Membuat State q0, q1, dan q2.Gambar 4.3. Membuat state q0, q1, dan q2.20

5. Menentukan initial state qs, dan final state F atau qf., klik kanan pada q0dan pilih initial. Selanjutnya, klik kanan pada q3 dan pilih final (Gambar4.4.).Gambar 4.4. Menentukan initial state (q0), dan final state (q2).6. Tentukan transisi seperti tampak pada gambar 4.5.Gambar 4.5. Membuat transisi antar state.7. Running mesin Finite State Automate tersebut dengan memilih menuinput, dan multiple run. Kemudian inputkan string seperti tampak pada21

gambar 4.6. Kemudian, klik Run Inputs. Contoh Traceback untuk string“abbbbbb” disajikan pada Gambar 4.7 dengan cara pilih string tersebut padainput, dan klik tombol View Trace.Gambar 4.6. Running input untuk mesin FSA.Gambar 4.7. Traceback string “abbbbbb” untuk mesin FSA22

C. Tugas PraktikumSeperti yang anda ketahui di kelas, bahwa Finite stete automate terdiri dariDeterministics finite automata (DFA), dan Non-Deterministics FiniteAuthomata (NDFA), perhatikan Gambar 4.8, dan tentukan:1. Q, Σ, δ, qs/S, dan F !2. Lakukan identifikasi jenis mesin tersebut apakah masuk ke dalam DFAatau NFA! Jelaskan !3. Buat struktur Mesin tersebut dengan menggunakan JFLAP.4. Cek L1 “ababababab “ dan L2 “bababababa”, apakah diterima mesintersebut ?Gambar 4.8. Graph FSA M123

NilaiYogyakarta, .Paraf asisten 24

Jawaban Postest25

Non-Deterministic Finite Automata (NFA)Pertemuan: VAlokasi Waktu: 1,5 jamKompetensi Dasar:1. terministicFiniteAutomata2. Mahasiswa mampu memahami algoritma NonDeterministic Finite AutomataIndikator:1. Mahasiswa mampu membuat interface denganmenggunakan visual programming2. inisticdanFiniteAutomataA. Dasar TeoriNondeterministic Finite Automata (NFA) adalah salah satu bagian dariotomata berhingga atau Finite State Automata (FSA). Pada NondeterministicFinite Automata (NFA) dimungkinkan satu simbol menimbulkan transisi kelebih dari satu kondisi dan memberikan beberapa kemungkinan gerakansehingga keluarannya tidak dapat dipastikan. Selain itu dimungkinkan jugaterjadinya transisi spontan atau transisi –ε.Nondeterministic Finite Automata (NFA) didefenisikan sebagai M yangmerupakan sebuah koleksi dari 5 obyek (Q , Σ , s , F , ) dimana :1. Q adalah sebuah himpunan hingga dari kedudukan-kedudukan.2. Σ adalah sebuah abjad masukan.3. s adalah salah satu kedudukan di dalam Q yang ditetapkan sebagaikedudukan permulaan.4. F adalah sebuah koleksi dari kedudukan-kedudukan yang diterima ataufinal (koleksi / himpunan dari kondisi akhir).26

5. adalah sebuah relasi pada (Q x Σ) x Q dan dinamakan relasi transisi.Salah satu rangkaian Nondeterministic Finite Automata (NFA) terlihat padagambar.Gambar 5.2. Rangkaian Nondeterministic Finite Automata (NFA)Rangkaian pada Gambar tergolong dalam Nondeterministic Finite Automata(NFA) karena beberapa transisi yang berasal dari satu kondisi yaitu kondisi q 0memiliki inputan yang sama yaitu ‘a’. Rangkaian tersebut akan menerimastring ab, aab, aabaab, aba, dan abaaba, tetapi tidak akan menerima string abbdan aabb.B. Petunjuk Praktikum1. Jalankan visual programming2. Buat desain form seperti praktikum 3 dan 4 (lihat gambar 5.2).Gambar 5.2 Tampilan form NFA27

3. Tambahkan fungsi yang menandakan bahwa graf tersebut NFA denganaturana. Dalam table transisi ada yang kosong maka dianggap sebagai grafNFAprocedure Tfrmutama.cekNFA;varj: Integer;i: Integer;begin// TODO -cMM: Tfrmutama.cekDFA default body inserted{for i : 1 to strngrdtransisi.RowCount dobeginInputStateA[i] : strngrdtransisi.Cells[1,i];InputStateB[i] : strngrdtransisi.Cells[2,i];end; }j: 1;if (strngrdtransisi.Cells[1,j] '') and(strngrdtransisi.Cells[2,j] '') thenbeginShowMessage('tidak ksosong');Inc(j);endelse beginShowMessage('GRAF dari tabel Transisi:' #13 'NonDeterministic Finite Automata');end;end;b. Jika input transisi yang sama lebih dari 1 state maka di anggap sebagaiNFAGambar 5.3 hasil pengecekan graf dari table traansisi28

C. Tugas PraktikumBuat NFA yang menerima string di bawah ini : ab,aab,abb,aaab,abbb.Gunakan NFA dari kasus di atas dan kembangkan untuk mendapatkan stringyang ditentukan. Gambar Graf transisinya.29

NilaiYogyakarta, .Paraf asisten Jawaban Postest30

Deterministic Finite Automata (DFA)Pertemuan: VIAlokasi Waktu: 1,5 jamKompetensi Dasar:1. Mahasiswamampumembuatrancanganinterface untuk Deterministic Finite Automata2. MahasiswamampumemahamialgoritmaDeterministic Finite Automata (DFA)Indikator:1. Mahasiswa mampu membuat interface denganmenggunakan visual programming2. Mahasiswa mampu membuat fungsi untukmengecek DFA dan aplikasi DFAA. Dasar TeoriFinite state automata berdasarkan kemampuan berubah state-statenya bisadikelompokkan ke dalam deterministic maupun non-deterministic.DFA mempunyai cirri utama yaitu dari satu state tepat satu state berikutnyauntuk setiap simbol masukkan yang diterima. Lihat gambar di bawah1startq000q21q1010q31Q {q0 , q1 , q2 , q3 } {0,1}S q0F { q0}31

fungsi transisi q0q1q2q30q2q3q0q11q1q0q3q2Jika ada string0011 : diterima.10010 : ditolak, karena banyaknya 0 ganjil ( q0,011) ( q2,11) ( q3,1) q2Ditolak ( q0,1010) ( q1,010) ( q3,10) ( q2,0) q0DiterimaB. Petunjuk Praktikum1. Jalankan program visual programming2. Buat program seperti pada finite state automataGambar 6.1. tampilan form Deterministic Finite Automata3. Gunakan Diagram DFA di bawah ini untuk membuat programa,baq0bq132

Tabel Transisiabq0q0q0q1q1q14. Tambahkan fungsi untuk pengecekan bahwa graf DFAprocedure Tfrmutama.cekDFA;varj: Integer;i: Integer;beginfor j : 1 to strngrdtransisi.RowCount - 1 dobeginif (strngrdtransisi.Cells[1,j] '') and(strngrdtransisi.Cells[2,j] '') thenbeginShowMessage('bukan GRAF DFA, karena ada input yang kosong');endelse beginShowMessage('GRAF yang dibuat dari tabel transisi adalahDFA');end;end;end;Gambar 6.2. Tampilan form DFA cek graf33

C. Tugas PraktikumTambahkan 1 state dengan nama q2. Dan table transisinyaABq0q0q0q1q2q1q2q2q2Gambar graf transisinya dan tentukan 2 string yang diterima dan ditolak(tuliskan hasilnya pada lembar jawaban di modul)34

NilaiYogyakarta, .Paraf asisten Jawaban Postest35

Pushdown Automata (PDA)Pertemuan: VIIAlokasi Waktu: 1,5 jamKompetensi Dasar:1. Mahasiswa mampu mensimulasikan PushdownAutomata (PDA), khususnya non-deterministikPDA dengan menggunakan JFLAP.2. Mahasiswamampumemahaminon-deterministik PDA (NDFA)Indikator:1. Mahasiswa mampu membuat struktur NDFAdan mensimulasikannya.2. Mahasiswa mampu menjelaskan proses NDFA.A. Dasar TeoriPushdown Automata (PDA) adalah sebuah finite automata yang memilikimemori berdasarkan stack (tumpukan). Di dalam sebuah PDA setiap transisididasarkan pada input symbol yang terbaca terakhir, dan juga input symbolyang berada pada tumpukan (stack) teratas. Operasi stack ini terdiri dari popdan push. Pop mengeluarkan input symbol dari tumpukan, dan pushmemasukkan symbol ke dalam tumpukan. Sebagai initial, di dalam tumpukanterdapat symbol Z0 yang mengindikasikan tumpukan paling bawah.Di dalam JFLAP, sebuah nondeterministic pushdown automata (NPDA) Mdidefinnisikan menggunakan 7 tupel yaitu M (Q, Σ, Γ, δ, qs, Z, F) dimana,Q merupakan sebuah himpunan finite state {qi i adalah nonnegative integer}Σ merupakan input symbol, alphabet.Γ adalah finite stack alphabet.δ adalah fungsi transisi, δ : Q Σ* Γ* finite subsets of Q Γ*qs (anggota Q) yang merupakan initial state.Z adalah symbol untuk stack awal (harus ditulis dengan kapital Z)36

F (anggota himpunan Q) adalah himpunan final stateB. Petunjuk Praktikum1. Jalankan aplikasi JFLAP, dan pilih menu “Pushdown Automata”.2. Buat State q0 sd q3, tentukan q0 sebagai initial state dan q3 sebagai finalstate (Gambar 7.1). Input PDA berbeda dengan kita menentukan inputpada finite automata. Pada PDA kita memerlukan 3 buah input dalamsetiap transisi (Gambar 7.2).Gambar 7.1. Menentukan state.Nilai input pertama dalam setiap transisi menunjukkan input yangdiproses. Nilai berikutnya menunjukkan nilai pada top stack, dan nilaiketiga pada sebuah transisi menunjukkan nilai baru yang dipush menjaditop stack ketika transisi setelah mem-pop nilai yang berada pada topstack.Gambar 7.2. Input pada PDA37

3. Kontruksipak PDA seperti tampak pada Gambar 7.3.Gambar 7.3. Kontruksi PDA (m1)4. Masukkan input L “aabb”.5. Hasil ketika dilakukan trace tampak pada Gambar 7.4.Gambar 7.4. Hasil Trace string “aabb”38

C. Tugas Praktikum1. Tentukan masing-masing 5 buah string atau L yang diterima dan ditolakoleh mesin m12. Kontruksikan PDA dari tabel transisi M2 sebagai berikut.Q {q0, q1 } {a,b}Γ {A,B,Z}qs q0Z ZF {q1}δ (Fungsi transisi):δ(q0, ,Z) {(q1,Z)}δ (q0,a,Z) {(q0,AZ)}δ (q0,b,Z) {(q0,BZ)}δ (q0,a,A) {(q0,AA)}δ (q0,b,A) {(q0, )}δ (q0,a,B) {(q0, )}δ (q0,b,B) {(q0, BB)}Tentukan 5 string atau L yang diterima oleh M2 tersebut.39

NilaiYogyakarta, .Paraf asisten Jawaban Postest40

Chomsky Normal Form (CNF)Pertemuan: VIIIAlokasi Waktu: 1,5 jamKompetensi Dasar:1. Mahasiswamampumembuatrancanganinterface CNF2. Mahasiswa mampu memahami algoritama ddari proses CNFIndikator:1. Mahasiswa mampu membuat interface denganmenggunakan visual programming2. Mahasiswa mampu membuat fungsi untuk CNFA. Dasar TeoriSalah satu bentuk yang normal yang berguna untuk tata bahasa rmalChomsky/Chomsky Normal Form (CNF). CNF dari sebuah CFG dapatdibentuk setelah CFG disederhanakan, yaitu setelah CFG tidak memilikiproduksi Useless, Unit, dan Nullable (ɛ). CFG telah dalam bentuk CNFapabila sisi kanan (β) dari sebuah CNF berisi (Cole, 2007):a) Maksimal sebuah terminal, contoh A b, ataub) Maksimal terdiri dari dua buah variable A BC, atauc) Khusus pada aturan produksi symbol awal S ɛ , jika ɛ di dihasilkan olehproduksi S (dalam bahasa),d) Simbol awal S hanya muncul pada sisi kiri (α) aturan produksi.Contoh bentuk normal Chomsky:S CDC AB BDA aB bD d41

B. Petunjuk Praktikum1. Jalankan visual programming atau bahasa pemrograman lain yangdikuasai2. Buat desain form input dan luaran untuk proses pembentukan normalChomsky3. Buat prosedur dan fungsi untuk membuat normal Chomsky berdasarkanalgoritma sebagai berikut (Branicky, 2004):1. Untuk setiap aturan produksi A B1B2 . Bk yangberisi sebuah terminal σ1) Tambahkansymbolvariablebaru(nonterminal) dan bentuk aturan produksi barumenjadi Cσ σ (kecuali aturan produksitersebut telah tersedia)2) Ganti setiap Bi σ dengan Cσ2. Ubah setiap aturan produksi A B1B2 Bk denganB1 . Bk berupa symbol variable dan k 3, makalakukan1) A B1A12) A1 B2A23) A2 B3A34) .5) Ak-2 Bk-1Bk dimana Ai adalah variable baru3. Gabungkan hasil pada langkah 1 dan 24. Lakukan testing untuk memastikan program berjalan dengan benar5. Dokumentasikan form/interface, prosedur, fungsi, input dan luaranprogram yang dibuat dalam kertas A4, diketik dengan huruf times newroman 12 dengan 1 spasi.42

C. Pretest PraktikumBuatlah bentuk CNF dari CFG sebagai berikut menggunakan program yangtelah anda buat.S AB BaA dB bB Bb aC cD. Postest PraktikumGunakan program yang anda buat untuk membuat CNF dari CFG berikut:S ABCD BCd CDA bB CdB cD bC cD aBc dE. ReferensiBranicky, M. (2004). EECS 343 Handout: Chomsky Normal Form. Retrievedfrom http://dora.eeap.cwru.edu/msb/343/normal.pdfCole, R. (2007). Converting CFGs to CNF (Chomsky Normal Form). Retrievedfrom cnf.pdf43

NilaiYogyakarta, .Paraf asisten Jawaban Postest44

Penghilangan Rekursif KiriPertemuan: IXAlokasi Waktu: 1,5 jamKompetensi Dasar:1. Mahasiswamampumembuatrancanganinterface penghilangan rekursif kiri2. Mahasiswa mampu memahami algoritama ddari proses penghilangan rekursif kiriIndikator:1. Mahasiswa mampu membuat interface denganmenggunakan visual programming atau bahasapemrograman lain yang dikuasai2. Mahasiswa mampu membuat prosedur/fungsiuntuk penghilangan rekursif kiriA. Dasar TeoriConext Free Grammar (CFG) dikatakan rekursif kiri apabila aturanproduksinya dalam bentuk (Maza, 2004):A A Dimana A merupakan symbol variable (non terminal) dan adalah string darisymbol-simbol CFG. Rekursif kiri akan mengakibatkan perulanganpenurunan CFG yang tidak akan pernah berhenti (Weimar et al., 2015). Olehkarena itu, rekursif kiri dalam CFG harus dihilangkan.Contoh aturan produksi rekursif kiri:S SdBaA AbCDC CdaD DbacBaLangkah-langkah untuk penghilangan rekursif kiri (Moore, 2001;Utdirartamo, 2005):1. Pisahkan aturan produksi yang rekursif kiri dan yang tidak, missal:a. Aturan produksi yang rekursif kiri A A 1 A 2 A 3 A n,sehingga dapat diketahui 1, 2, 3, , nb. Aturan produksi yang tidak rekursif kiri A 1 2 3 m,sehingga dapat diketahui 1, 2, 3, , m45

2. Lakukan penggantian aturan produksi yang terdapat rekursif kiriberdasarkan rumus sebagai berikut:A 1 1A’ 2 2 A’ 3 3 A’ m m A’A’ 1 1A’ 2 2A’ 3 1A’ n n A’Dimana A’ marupakan symbol variable (non terminal) yang tidakdigunakan di aturan produksi lain dalam CFG tersebut.B. Petunjuk Praktikum1. Jalankan visual programming atau bahasa pemrograman lain yangdikuasai2. Buat desain form input dan luaran untuk proses penghilangan rekursif kiri.3. Buat prosedur/fungsi untuk proses penghilangan rekursif kiri berdasarkanalgoritma sebagai berikut:1. Pisahkan produksi yang rekursif kiri dan tidak1) Produksi rekursif kiri A 1, A 2, A 3, ,A n2) Produksi tidak rekursif kiri 1, 2, 3, , m2. Ganti setiap produksi dalam bentuk Ai Aj dengan produksi Ai 1 1A’ 2 2 A’ 3 3 A’ m m A’, Dan A’ 1 1A’ 2 2A’ 3 1A’ n n A’3. Lakukanlangkah1dan2untuksemuaaturanproduksi pada CFG4. Lakukan testing untuk memastikan program berjalan dengan benar5. Dokumentasikan form/interface, prosedur, fungsi, input dan luaranprogram yang dibuat dalam kertas A4, diketik dengan huruf times newroman 12 dengan 1 spasi.C. Pretest PraktikumBuatlah bentuk CNF dari CFG sebagai berikut menggunakan program yangtelah anda buat.S SABC Ba ab a c46

D. Postest PraktikumGunakan program yang anda buat untuk membuat CNF pada kasus CFGberikut:S Sba Abc bA AbB ab Ac dB BcA bE. ReferensiMaza, M. M. (2004). Elimination of left recursion. Retrieved fromhttp://www.csd.uwo.ca/ , R. C. (2001). Removing Left Recursion from Context-Free Grammars.Revised version of paper appearing in Proceedings of the 1st Meeting of theNorth American Chapter of the Association for Computational Linguistics,ANLP-NAACL 2000.Utdirartamo, F. (2005). Teori Bahasa dan Otomata. Yogyakarta: Penerbit GrahaIlmu.Weimar, W., Leach, K., Thomason, Wi., Recto, R., Roberts, J., & Leath, H.(2015). Eliminating Immediate Left Recursion. Retrieved fromhtt

Contoh : abc, ab, a, dan e adalah semua Prefix(x) Postfix (atau Suffix) string w adalah string yang dihasilkan dari string w dengan menghilangkan nol atau lebih simbol-simbol paling depan dari string w tersebut. Contoh : ab