Change Background of This Blog!


Pasang Seperti Ini
=========================Selamat Datang Di Situs Resmi Ulum Computer ====================
  • hhjjjjjjjjjjjjjjj
  • 1
  • 1
  • 1
  • 1

Sabtu, 17 Maret 2012

CorelDraw


 
 
 
 
 
 
i
 
Rate This
Quantcast
Corel adalah perusahaan pembuat perangkat lunak komputer. Produk Corel yang paling dikenal dan banyak digunakan oleh masyarakat Indonesia adalah Corel Draw, sebuah perangkat lunak yang dibuat untuk gambar vektor atau pembuatan vektor. Corel menyediakan paket dalam penjualan perangkat lunaknya, yaitu Corel Graphic Suite, yang didalamnya terdiri dari Corel Draw, Corel R.A.V.E, Corel PhotoPaint, Corel Trace, Corel Capture, Corel update, Font Navigator, dan SB profiler. Perusahan Corel didirikan tahun 1985 dan memiliki markas di Ottawa, Kanada.Berdasarkan data, pengguna produk Corel telah mencapai lebih dari 40 juta dan produk Corel telah dijual di lebih dari 75 negara. bagi anada yang mau belajar coreldraw, bisa lihat tutorialnya seperti berikut.
  1. Membuat Logo Telkom
  2. Membuat Logo Shell
  3. Membuat Logo Pertamina
  4. Membuat Logo Adidas
  5. Membuat Logo Master Card
  6. Menggabungkan Beberapa Vector

KIAT MENDAPATKAN IPK (NILAI KULIAH) TINGGI....... (yang pengen mendapatkan nilai kuliah bagus dan membanggakan Ortu, WAJIB BACA NIE......)


Tulisan ini hanya bersifat share aja sob, ga ada maksud apapun. So stay positive thinking . Dolo pas awal masuk ke dunia kampus, memang sempat terlintas cara-cara gimana sie kita bisa dapet IPK bagus alias tinggi (bagi yang belum tau IPK, coba deh tanya ama kakak tinggat or dosen loe or mbah wiki or om google or tetangga loe deh or tukang bakso kek or penjual es kek, pokoke tanya siapapun yg tau jawabannya) Jadi begini sob, secara prinsip cara belajar di kampus ama di sekolah itu laen men. Jangan disamakan. Belajar di kampus memerlukan kemandirian karena dosen bersifat pasif dan mahasiswa yang bersifat aktif. Hal ini kan berbeda ama pas kita di skull. beTul ga ??? So bagaimana kiat-kiat nya ?? 1. Pas Kuliahnya Sob Agar dapat memahami dan mengikuti kuliah dari para dosen kita tercinta (ceeeeiiileee......), biasain sebelum berangkat ke kampus persiapkan diri sob dengan membaca terlebih dahulu materi kuliah. Eitts....jangan lupa jurus yang satu ini sob, dekatilah kakak tingkat loe. Tanyain mereka seputar kegiatan perkuliahan, gimana dosennya ?? (maksudnya killer apa ga tuh dosen). Kalo perlu sampe kebiasaan-kebiasaan dosennya sob (maksudnya tuh kalo pas kuliah gimana, trus kalo quis tuh soalnya gimana). Dan yang paling penting sob, minta soal-soal ke kakak tingkat. Kale aja soalnya keluar pas ujian sob, kan rejeki nomplok tuh Jangan datang terlambat sob pas kuliah, kebiasaan sangat buruk nie sob. (Tapi kalo memang kepepet dan terpaksa, ga pa2 sob....namanya juga kepepet). Karena kalo telat, ntar ga bisa ngikutin materi kuliah dari awal. Satu lagi nie sob, kalo memang dosen loe emang suka ngaret.....ga pa2 deh loe ngaret juga. Kan kalo guru kencing berdiri, murid kencingnya berlari sob (emang bisa ?? kencing sambil lari.....) Setelah masuk ke dalam kelas, cari tempat duduk yang uueeeeenak sob (kalo ane sie biasanya di bawah kipas angin, maklum sob....panas banget kalo di dalam kelas. hehehehehehe.....). Posisi tempat duduk nie sangat mempengaruhi loe dalam menyimak materi kuliah. Kalo kata temen ane nie sob, tempat duduk yang paling strategis ya ada di depan sendiri. Banyak keuntungannya tuh sob. loe pasti melihat dengan jelas tulisan dosen (nie bagi dosen yang tulisannya kecil-kecil...hehehehehehe....). Trus, dosen pasti mengenali wajah loe deh (poin plus tuh...). Soalnya kalo dosen pas lagi butuh spidol ato penghapus, pasti deh loe yang pertama dipanggil..... wkwkwkwkwkwkw. just kidding sob....yang jelas posisi duduk di depan menguntungkan banget deh sob. Kalo ga percaya, coba aja..... Kalo udah duduk di depan, coba deh aktif selalu di setiap perkuliahan sob 2. Belajar di Rumah Sesibuk apapun loe... entah loe kerja, aktif di organisasi, maen PB, nongkrong, mbantu emak, dll deh...jangan lupain buat belajar di rumah. Sempatkan aja walau cuman 1-2 jam setiap harinya. Buatlah belajar di rumah senyaman dan seenak mungkin sehingga loe betah. Cobalah bikin kelompok belajar ato gabung ama komunitas belajar. Tapi kalo udah terbentuk kelompok belajar, jangan hanya asal nebeng aja sob, kalo ada tugas tinggal copy paste (soalnya masih enakan kopi susu. hehehehehe) 3. Manfaatin tuh Perpustakaan Bagi orang-orang yang kere kayak ane nie....yang tiap berangkat ngampus pake sepeda butut, perpustakaan merupakan tongkrongan wajib. Kalo mau beli buku ga ada duit sob. Minta emak juga sungkan, masak udah gede minta melulu. Mana belum gawe lagi, dapet duit darimana buat beli buku. Padahal buku merupakan salah satu alat kita dalam belajar dan menambah wawasan. 4. Kejar Nilai-nya sob Kejar nilai untuk mata pelajaran atau mata kuliah yang secara umum tidak terlalu loe senangi sob. Apa itu? Oh banyak sob, misalnya nie geografi, agama, kesenian, dsb atau untuk yang kuliah di jurusan computing, ada fisika dasar, teknik kompilasi, automaton/formal language, dsb. Lakukan survey kecil-kecilan ke temen seangkatan atau kakak angkatan, ane yakin banyak sekali mata kuliah yang tidak digemari mahasiswa. Intinya di mata kuliah yang diemohi mahasiswa itu, mereka biasanya down nilainya. Nah ini dia kesempatan kita, di saat nilai mereka “pasti rendah”, kita berjuang untuk nilai “pasti tinggi” … hehehe. Nah hasil dari tahap ini yaitu kalau ada IPK khusus untuk “mata kuliah tidak populer” kita pasti nomor satu Sudah mantab dengan langkah diatas? Langkah selanjutnya adalah jangan berhenti, lanjutkan mengejar nilai untuk mata pelajaran atau mata kuliah yang secara umum kamu senangi … hehehe. Belajar keras, kerjakan semua tugas, kalau perlu kejar terus dosen kalau ada yang masih nggak ngerti di mata kuliah “populer” itu. Kalaupun kita tidak bisa mendapatkan nilai sempurna alias sedang-sedang saja ya nggak apa-apa, asal sudah berusaha. Yang pasti karena IPK adalah nilai kumulatif dari mata kuliah “tidak populer” dan “populer”, total nilai kita akan tetap tinggi tho. Lha kan kita sudah jadi the first rank untuk mata kuliah “tidak populer” … hihihi. 5. Jangan Lupa Berdo’a, Sholat Malam, Puasa Sunnah, Sedekah, dll Yang satu ini jangan dilupakan sob. Setelah kita berikhtiar dengan segenap tenaga dan sekeras baja, tinggal kita berdo’a. Tambahin juga sholat malam sob. Puasa sunnahnya coba dijalanin sob. Jangan lupa juga bersedekah, kalo punya rezeki. Akhir semester silakan dilihat nilai IPK atau raportnya, ane yakin nilai loe akan meningkat. Kalau masih belum naik, lanjutkan tahap 1 dan 2 di semester berikutnya. Kalaupun sampai akhir kuliah tidak naik-naik juga, ya apa boleh buat, memang level kekuatan loe seperti itu sob. Mungkin loe kurang berdoa, kurang sholat malam atau kurang puasa senin-kamis, kurang sedekah, sehingga ridha dan “lucky” dari yang Allah SWT tidak menyertai anda. Tapi jangan khawatir, IPK bukan segalanya sob, masih banyak cara lain dan perlu juga dicatat banyak orang sukses yang IPKnya hancur kok. Untuk yang sudah ber-IPK bagus, jangan cepat puas apalagi sombong dan takabur, karena faktor-faktor itulah yang membuat orang seperti loe tidak sukses ketika masuk ke dunia kerja. Wallahu ‘allam (samubay)

Cara Menghilangkan Tampilan Iklan Di FB


Ketika kita membuka halaman FB kita, terkadang terasa lama karena kita mau tidak mau harus menunggu loading dari iklan yang harus tampil di sisi samping halaman kita tersebut. Apakah berguna iklan tersebut..? tentu sangat berguna, karena kita akan membutuhkan informasi dari iklan-iklan tersebut. Tapi..... jikalau internet yang kita gunakan bandwidth nya sangat terbatas, semua itu akan membuat kita bosan harus menunggu loading dari iklan-iklan tersebut.

Pada kesempatan kali ini saya akan mencoba berbagi dengan sobat sekalian bagaimana cara menghilangkan tampilan iklan tersebut, agar tidak tampil lagi di sisi sampiang halaman FB kita. Tujuan nya jelas sekali adalah agar kita lebih cepat dalam mengakses halaman kita itu. Dan trik ini pada saat ini hanya berlaku bagi para sobat yang browsing menggunakan Mozilla Firefox saja, untuk yang menggunakan browser yang lain mungkin akan kita bahas lagi di lain waktu.

Silahkan ikuti langkah-langkah berikut ini :

1. Buka browser Mozilla Firefox anda
2. Klik Tab Tools
3. Klik pilihan menu Add-ons
4. Klik Tab Get Add-ons
5. Pada kolom Search All Add-ons silahkan ketik "remove all facebook ads" (tanpa tanda kutip) lalu enter
6. Jika sudah ketemu, klik pilihan menu Add to Firefox yang ada di samping kanan
7. Kemudian klik pilhan menu Install Now
8. Setelah selesai terinstall, silahkan klik pilhan menu Restart Firefox
9. Selesai.

Trik ini hanya bekerja pada perangkat yang telah terinstall Add-ons tersebut di atas, jika anda sign in ID FB anda di perangkat yang lain yang belum terinstall Add-ons tersebut pasti akan tetap tampil iklan-iklannya.

Selamat mencoba, semoga bermanfaat

cara merawat USB modem

Tips Komputer (Surabaya, 2011)

Online online online online bukan mejadi lagu saja sekarang, tetapi merupakan bagian dari gaya hidup masyarakat millenium kedua. Dari orang dewasa sampai anak-anak, dari kalangan borju sampai rakyat jelata modem adalah simbol kehausan mereka akan informasi atau sekedar arus yang telah menyeret mereka masuk kedua maya, dunia yang kadang oleh mereka menjadi dunia yang ideal karena apa yang mereka peroleh di dunia nyata tidak seperti apa yang mereka peroleh di dunia maya.
Para jutawan baru lahir di era informasi sekarang ini berkat desakan ekonomi di dunia nyata yang semakin terpuruk sehingga arus pencari kerja beralih ke dunia maya. Dengan bantuan modem mereka menggelar lapak-lapak online memenuhi belantara internet. Klik demi klik sangat berharga bagi mereka. Keberuntungan demi keberuntungan di dapat melalui internet. Dan tentu saja jasa besar telah dicapai karena modem :-). Bisnis online pun menjadi lancar.
Namun apa yang terjadi jika modem tersebut rusak? Maka tertutuplah peluang untuk mengais rizki dari internet, terputuslah klien-klien seperti tiba-tiba saja dunia kita ditutup hanya karena modem yang rusak (lebay hehehe) :-). Agar hal tersebut tidak terjadi tips-komputer.com akan berbagi tips maknyus cara merawat modem USB yang baik dan benar.
1. Gunakan modem secukupnya, berilah waktu istirahat buat modem Anda karena pemakaian secara terus menerus akan menyebabkan sedikit demi sedikit komponennya aus.
2. Berilah gantungan modem agar mudah untuk dibawa dan dipegang.
3. Jangan sekali-kali mencabut modem tanpa melakukan disconnect dan eject dari komputer Anda.
4. Pastikan modem USB menancap kuat dan benar di port USB komputer atau laptop Anda.
5. Simpan modem Anda ditempat yang aman dan tidak lembab karena dapat menyebabkan korosi di sekitar colokan modem.
6. Tutup modem sangatlah penting, jangan sampai kehilangan tutup modem. Jika perlu belilah modem dengan tutup yang tersegel dengan modemnya oleh tali.
7. Hindarkan modem dari barang cair.
8. Jauhkan modem dari anak-anak.
9. Hindarkan modem dari benturan keras karena jatuh atau terbentur benda-benda yang keras.
Demikianlah Tips Trik Komputer tentang Tips Maknyus Cara Merawat Modem USB semoga membantu Anda. Terimakasih atas kunjungan Anda, semoga menjadikan belajar komputer

TEORI BAHASA DAN AUTOMATA


I. PENDAHULUAN
Teori Bahasa
Teori bahasa membicarakan bahasa formal (formal language), terutama untuk
kepentingan perancangan kompilator (compiler) dan pemroses naskah (text
processor). Bahasa formal adalah kumpulan kalimat. Semua kalimat dalam sebuah
bahasa dibangkitkan oleh sebuah tata bahasa (grammar) yang sama. Sebuah bahasa
formal bisa dibangkitkan oleh dua atau lebih tata bahasa berbeda. Dikatakan bahasa
formal karena grammar diciptakan mendahului pembangkitan setiap kalimatnya.
Bahasa manusia bersifat sebaliknya; grammar diciptakan untuk meresmikan kata-kata
yang hidup di masyarakat. Dalam pembicaraan selanjutnya ‘bahasa formal’ akan
disebut ‘bahasa’ saja.
Automata
Automata adalah mesin abstrak yang dapat mengenali (recognize), menerima
(accept), atau membangkitkan (generate) sebuah kalimat dalam bahasa tertentu.
Beberapa Pengertian Dasar
• Simbol adalah sebuah entitas abstrak (seperti halnya pengertian titik dalam
geometri). Sebuah huruf atau sebuah angka adalah contoh simbol.
• String adalah deretan terbatas (finite) simbol-simbol. Sebagai contoh, jika a, b,
dan c adalah tiga buah simbol maka abcb adalah sebuah string yang dibangun dari
ketiga simbol tersebut.
• Jika w adalah sebuah string maka panjang string dinyatakan sebagai w dan
didefinisikan sebagai cacahan (banyaknya) simbol yang menyusun string tersebut.
Sebagai contoh, jika w = abcb maka w= 4.
• String hampa adalah sebuah string dengan nol buah simbol. String hampa
dinyatakan dengan simbol ε (atau ^) sehingga ε= 0. String hampa dapat
dipandang sebagai simbol hampa karena keduanya tersusun dari nol buah simbol.
• Alfabet adalah hinpunan hingga (finite set) simbol-simbol
Operasi Dasar String
Diberikan dua string : x = abc, dan y = 123
• Prefik string w adalah string yang dihasilkan dari string w dengan menghilangkan
nol atau lebih simbol-simbol paling belakang dari string w tersebut.
Contoh : abc, ab, a, dan ε adalah semua Prefix(x)
• ProperPrefix string w adalah string yang dihasilkan dari string w dengan
menghilangkan satu atau lebih simbol-simbol paling belakang dari string w
tersebut.
Contoh : ab, a, dan ε adalah semua ProperPrefix(x)
• Postfix (atau Sufix) string w adalah string yang dihasilkan dari string w dengan
menghilangkan nol atau lebih simbol-simbol paling depan dari string w tersebut.
Contoh : abc, bc, c, dan ε adalah semua Postfix(x)
• ProperPostfix (atau PoperSufix) string w adalah string yang dihasilkan dari string
w dengan menghilangkan satu atau lebih simbol-simbol paling depan dari string w
tersebut.
Contoh : bc, c, dan ε adalah semua ProperPostfix(x)
• Head string w adalah simbol paling depan dari string w.
Contoh : a adalah Head(x)
Asep Juarna, Catatan Teori Bahasa dan Automata, hal 1









Tail string w adalah string yang dihasilkan dari string w dengan menghilangkan
simbol paling depan dari string w tersebut.
Contoh : bc adalah Tail(x)
Substring string w adalah string yang dihasilkan dari string w dengan
menghilangkan nol atau lebih simbol-simbol paling depan dan/atau simbol-simbol
paling belakang dari string w tersebut.
Contoh : abc, ab, bc, a, b, c, dan ε adalah semua Substring(x)
ProperSubstring string w adalah string yang dihasilkan dari string w dengan
menghilangkan satu atau lebih simbol-simbol paling depan dan/atau simbol-
simbol paling belakang dari string w tersebut.
Contoh : ab, bc, a, b, c, dan ε adalah semua Substring(x)
Subsequence string w adalah string yang dihasilkan dari string w dengan
menghilangkan nol atau lebih simbol-simbol dari string w tersebut.
Contoh : abc, ab, bc, ac, a, b, c, dan ε adalah semua Subsequence(x)
ProperSubsequence string w adalah string yang dihasilkan dari string w dengan
menghilangkan satu atau lebih simbol-simbol dari string w tersebut.
Contoh : ab, bc, ac, a, b, c, dan ε adalah semua Subsequence(x)
Concatenation adalah penyambungan dua buah string. Operator concatenation
adalah concate atau tanpa lambang apapun.
Contoh : concate(xy) = xy = abc123
Alternation adalah pilihan satu di antara dua buah string. Operator alternation
adalah alternate atau .
Contoh : alternate(xy) = xy = abc atau 123
Kleene Closure : x* = εxxxxxx... = εxx 2 x 3 ...
Positive Closure : x + = xxxxxx... = xx 2 x 3 ...
Beberapa Sifat Operasi
• Tidak selalu berlaku : x = Prefix(x)Postfix(x)
• Selalu berlaku : x = Head(x)Tail(x)
• Tidak selalu berlaku : Prefix(x) = Postfix(x) atau Prefix(x) ≠ Postfix(x)
• Selalu berlaku : ProperPrefix(x) ≠ ProperPostfix(x)
• Selalu berlaku : Head(x) ≠ Tail(x)
• Setiap Prefix(x), ProperPrefix(x), Postfix(x), ProperPostfix(x), Head(x), dan
Tail(x) adalah Substring(x), tetapi tidak sebaliknya
• Setiap Substring(x) adalah Subsequence(x), tetapi tidak sebaliknya
• Dua sifat aljabar concatenation :
♦ Operasi concatenation bersifat asosiatif : x(yz) = (xy)z
♦ Elemen identitas operasi concatenation adalah ε : εx = xε = x
• Tiga sifat aljabar alternation :
♦ Operasi alternation bersifat komutatif : xy = yx
♦ Operasi alternation bersifat asosiatif : x(yz) = (xy)z
♦ Elemen identitas operasi alternation adalah dirinya sendiri : xx = x
• Sifat distributif concatenation terhadap alternation : x (yz) = xyxz
• Beberapa kesamaan :
♦ Kesamaan ke-1 : (x*)* = (x*)
♦ Kesamaan ke-2 : εx + = x + ε = x*
♦ Kesamaan ke-3 : (xy)* = εxyxxyyxyyx... = semua string yang
merupakan concatenation dari nol atau lebih x, y, atau keduanya.
Asep Juarna, Catatan Teori Bahasa dan Automata, hal 2
II. GRAMMAR DAN BAHASA
Konsep Dasar
1. Dalam pembicaraan grammar, anggota alfabet dinamakan simbol terminal atau
token.
2. Kalimat adalah deretan hingga simbol-simbol terminal.
3. Bahasa adalah himpunan kalimat-kalimat. Anggota bahasa bisa tak hingga
kalimat.
4. Simbol-simbol berikut adalah simbol terminal :
• huruf kecil awal alfabet, misalnya : a, b, c
• simbol operator, misalnya : +, −, dan ×
• simbol tanda baca, misalnya : (, ), dan ;
• string yang tercetak tebal, misalnya : if, then, dan else.
5. Simbol-simbol berikut adalah simbol non terminal :
• huruf besar awal alfabet, misalnya : A, B, C
• huruf S sebagai simbol awal
• string yang tercetak miring, misalnya : expr dan stmt.
6. Huruf besar akhir alfabet melambangkan simbol terminal atau non terminal,
misalnya : X, Y, Z.
7. Huruf kecil akhir alfabet melambangkan string yang tersusun atas simbol-simbol
terminal, misalnya : x, y, z.
8. Huruf yunani melambangkan string yang tersusun atas simbol-simbol terminal
atau simbol-simbol non terminal atau campuran keduanya, misalnya : α, β, dan γ.
9. Sebuah produksi dilambangkan sebagai α → β, artinya : dalam sebuah derivasi
dapat dilakukan penggantian simbol α dengan simbol β.
10. Simbol α dalam produksi berbentuk α → β disebut ruas kiri produksi sedangkan
simbol β disebut ruas kanan produksi.
11. Derivasi adalah proses pembentukan sebuah kalimat atau sentensial. Sebuah
derivasi dilambangkan sebagai : α ⇒ β.
12. Sentensial adalah string yang tersusun atas simbol-simbol terminal atau simbol-
simbol non terminal atau campuran keduanya.
13. Kalimat adalah string yang tersusun atas simbol-simbol terminal. Jelaslah bahwa
kalimat adalah kasus khusus dari sentensial.
14. Pengertian terminal berasal dari kata terminate (berakhir), maksudnya derivasi
berakhir jika sentensial yang dihasilkan adalah sebuah kalimat (yang tersusun atas
simbol-simbol terminal itu).
15. Pengertian non terminal berasal dari kata not terminate (belum/tidak berakhir),
maksudnya derivasi belum/tidak berakhir jika sentensial yang dihasilkan
mengandung simbol non terminal.
Grammar dan Klasifikasi Chomsky
Grammar G didefinisikan sebagai pasangan 4 tuple : V T , V N , S, dan Q, dan
dituliskan sebagai G(V T , V N , S, Q), dimana :
VT
: himpunan simbol-simbol terminal (atau himpunan token -token, atau
alfabet)
VN
: himpunan simbol-simbol non terminal
S ∈ V N : simbol awal (atau simbol start)
Q
: himpunan produksi
Asep Juarna, Catatan Teori Bahasa dan Automata, hal 3
Berdasarkan komposisi bentuk ruas kiri dan ruas kanan produksinya (α → β), Noam
Chomsky mengklasifikasikan 4 tipe grammar :
1. Grammar tipe ke-0 : Unrestricted Grammar (UG)
Ciri : α, β ∈ (V T V N )*, α> 0
2. Grammar tipe ke-1 : Context Sensitive Grammar (CSG)
Ciri : α, β ∈ (V T V N )*, 0 < α ≤ β
3. Grammar tipe ke-2 : Context Free Grammar (CFG)
Ciri : α ∈ V N , β ∈ (V T V N )*
4. Grammar tipe ke-3 : Regular Grammar (RG)
Ciri : α ∈ V N , β ∈ {V T , V T V N } atau α ∈ V N , β ∈ {V T , V N V T }
Mengingat ketentuan simbol-simbol (hal. 3 no. 4 dan 5), ciri-ciri RG sering
dituliskan sebagai : α ∈ V N , β ∈ {a, bC} atau α ∈ V N , β ∈ {a, Bc}
Tipe sebuah grammar (atau bahasa) ditentukan dengan aturan sebagai berikut :
A language is said to be type-i (i = 0, 1, 2, 3) language if it can be
specified by a type-i grammar but can’t be specified any type-(i+1)
grammar.
Contoh Analisa Penentuan Type Grammar
1. Grammar G 1 dengan Q 1 = {S → aB, B → bB, B → b}. Ruas kiri semua
produksinya terdiri dari sebuah V N maka G 1 kemungkinan tipe CFG atau RG.
Selanjutnya karena semua ruas kanannya terdiri dari sebuah V T atau string
V T V N maka G 1 adalah RG.
2. Grammar G 2 dengan Q 2 = {S → Ba, B → Bb, B → b}. Ruas kiri semua
produksinya terdiri dari sebuah V N maka G 2 kemungkinan tipe CFG atau RG.
Selanjutnya karena semua ruas kanannya terdiri dari sebuah V T atau string
V N V T maka G 2 adalah RG.
3. Grammar G 3 dengan Q 3 = {S → Ba, B → bB, B → b}. Ruas kiri semua
produksinya terdiri dari sebuah V N maka G 3 kemungkinan tipe CFG atau RG.
Selanjutnya karena ruas kanannya mengandung string V T V N (yaitu bB) dan juga
string V N V T (Ba) maka G 3 bukan RG, dengan kata lain G 3 adalah CFG.
4. Grammar G 4 dengan Q 4 = {S → aAb, B → aB}. Ruas kiri semua produksinya
terdiri dari sebuah V N maka G 4 kemungkinan tipe CFG atau RG. Selanjutnya
karena ruas kanannya mengandung string yang panjangnya lebih dari 2 (yaitu
aAb) maka G 4 bukan RG, dengan kata lain G 4 adalah CFG.
5. Grammar G 5 dengan Q 5 = {S → aA, S → aB, aAb → aBCb}. Ruas kirinya
mengandung string yang panjangnya lebih dari 1 (yaitu aAb) maka G 5
kemungkinan tipe CSG atau UG. Selanjutnya karena semua ruas kirinya lebih
pendek atau sama dengan ruas kananya maka G 5 adalah CSG.
6. Grammar G 6 dengan Q 6 = {aS → ab, SAc → bc}. Ruas kirinya mengandung
string yang panjangnya lebih dari 1 maka G 6 kemungkinan tipe CSG atau UG.
Selanjutnya karena terdapat ruas kirinya yang lebih panjang daripada ruas
kananya (yaitu SAc) maka G 6 adalah UG.
Asep Juarna, Catatan Teori Bahasa dan Automata, hal 4
Derivasi Kalimat dan Penentuan Bahasa
Tentukan bahasa dari masing-masing gramar berikut :
1. G 1 dengan Q 1 = {1. S → aAa, 2. A → aAa, 3. A → b}.
Jawab :
Derivasi kalimat terpendek :
Derivasi kalimat umum :
S ⇒ aAa (1)
S ⇒ aAa
(1)
⇒ aba (3)
⇒ aaAaa
(2)
...
⇒ a n Aa n (2)
⇒ a n ba n (3)
Dari pola kedua kalimat disimpulkan : L 1 (G 1 ) = { a n ba n  n ≥ 1}
2. G 2 dengan Q 2 = {1. S → aS, 2. S → aB, 3. B → bC, 4. C → aC, 5. C → a}.
Jawab :
Derivasi kalimat terpendek :
Derivasi kalimat umum :
S ⇒ aB (2)
S ⇒ aS
(1)
⇒ abC (3)
...
⇒ aba (5)
⇒ a n -1 S
(1)
n
⇒a B
(2)
n
⇒ a bC
(3)
n
⇒ a baC
(4)
...
⇒ a n ba m -1 C
(4)
n
m
(5)
⇒ a ba
n
m
Dari pola kedua kalimat disimpulkan : L 2 (G 2 ) = { a ba  n ≥ 1, m ≥ 1}
3. G 3 dengan Q 3 = {1. S → aSBC, 2. S → abC, 3. bB → bb,
4. bC → bc, 5. CB → BC, 6. cC → cc}.
Jawab :
Derivasi kalimat terpendek 1:
Derivasi kalimat terpendek 3 :
S ⇒ abC (2)
S ⇒ aSBC
(1)
⇒ abc (4)
⇒ aaSBCBC
(1)
Derivasi kalimat terpendek 2 :
⇒ aaabCBCBC
(2)
S ⇒ aSBC
(1)
⇒ aaabBCCBC
(5)
⇒ aabCBC
(2)
⇒ aaabBCBCC
(5)
⇒ aabBCC
(5)
⇒ aaabBBCCC
(5)
⇒ aabbCC
(3)
⇒ aaabbBCCC
(3)
⇒ aabbcC
(4)
⇒ aaabbbCCC
(3)
⇒ aabbcc
(6)
⇒ aaabbbcCC
(4)
⇒ aaabbbccC
(6)
⇒ aaabbbccc
(6)
n n n
Dari pola ketiga kalimat disimpulkan : L 3 (G 3 ) = { a b c  n ≥ 1}
Asep Juarna, Catatan Teori Bahasa dan Automata, hal 5
Menentukan Grammar Sebuah Bahasa
1. Tentukan sebuah gramar regular untuk bahasa L 1 = { a n  n ≥ 1}
Jawab :
Q 1 (L 1 ) = {S → aSa}
2. Tentukan sebuah gramar bebas konteks untuk bahasa :
L 2 : himpunan bilangan bulat non negatif ganjil
Jawab :
Langkah kunci : digit terakhir bilangan harus ganjil.
Buat dua buah himpunan bilangan terpisah : genap (G) dan ganjil (J)
Q 2 (L 2 ) = {S → JGSJS, G → 02468, J → 13579}
3. Tentukan sebuah gramar bebas konteks untuk bahasa :
L 3 = himpunan semua identifier yang sah menurut bahasa pemrograman Pascal
dengan batasan : terdiri dari simbol huruf kecil dan angka, panjang identifier
boleh lebih dari 8 karakter
Jawab :
Langkah kunci : karakter pertama identifier harus huruf.
Buat dua buah himpunan bilangan terpisah : huruf (H) dan angka (A)
Q 3 (L 3 ) = {S → HHT, T → ATHTHA, H → abc..., A → 012...}
4. Tentukan gramar bebas konteks untuk bahasa L 4 (G 4 ) = {a n b m n,m ≥ 1, n ≠ m}
Jawab :
Langkah kunci : sulit untuk mendefinisikan L 4 (G 4 ) secara langsung. Jalan
keluarnya adalah dengan mengingat bahwa x ≠ y berarti x > y atau x < y.
L 4 = L A ∪ L B , L A ={a n b m n > m ≥ 1}, L B = {a n b m 1 ≤ n < m}.
Q A (L A ) = {A → aAaC, C → aCbab}, Q(L B ) = {B → BbDb, D→ aDbab}
Q 4 (L 4 ) = {S→ AB, A → aAaC, C → aCbab, B → BbDb, D→ aDbab}
5. Tentukan sebuah gramar bebas konteks untuk bahasa :
L 5 = bilangan bulat non negatif genap. Jika bilangan tersebut terdiri dari dua digit
atau lebih maka nol tidak boleh muncul sebagai digit pertama.
Jawab :
Langkah kunci : Digit terakhir bilangan harus genap. Digit pertama tidak boleh
nol. Buat tiga himpunan terpisah : bilangan genap tanpa nol (G), bilangan genap
dengan nol (N), serta bilangan ganjil (J).
Q 5 (L 5 ) = {S → NGAJA, A → NNAJA, G→ 2468, N→ 02468,
J → 13579}
Asep Juarna, Catatan Teori Bahasa dan Automata, hal 6
Mesin Pengenal Bahasa
Untuk setiap kelas bahasa Chomsky, terdapat sebuah mesin pengenal bahasa. Masing-masing
mesin tersebut adalah :
Kelas Bahasa
Mesin Pengenal Bahasa
Unrestricted Grammar (UG)
Mesin Turing (Turing Machine), TM
Context Sensitive Grammar (CSG) Linear Bounded Automaton, LBA
Context Free Gammar (CFG)
Automata Pushdown (Pushdown Automata), PDA
Regular Grammar, RG
Automata Hingga (Finite Automata), FA
Catatan :
1. Pengenal bahasa adalah salah satu kemampuan mesin turing.
2. LBA adalah variasi dari Mesin Turing Nondeterministik.
3. Yang akan dibahasa dalam kuliah Teori Bahasa dan Automata adalah : TM (sekilas), FA,
dan PDA.
III. MESIN TURING
Ilustrasi TM sebagai sebuah ‘mesin’:
Pita TM. Terbatas di kiri. Setiap sel berisi sebuah karakter dari
kalimat yang akan dikenali. Di kanan kalimat terdapat tak hingga
simbol hampa.
Head : membaca dan menulisi sel pita TM, bisa bergerak ke kiri atau ke akan
Finite State
Control (FSC)
FSC : otak dari TM, diimplementasikan dari algoritma pengenalan
kalimat.
Ilustrasi TM sebagai sebuah graf berarah :
1. Sebagaimana graf, TM terdiri dari beberapa node dan beberapa edge. Dari satu node
mungkin terdapat satu atau lebih edge yang menuju node lainnya atau dirinya sendiri.
2. Sebuah node menyatakan sebuah stata (state). Dua stata penting adalah stata awal S
(start) dan stata penerima H (halt). Sesaat sebelum proses pengenalan sebuah kalimat,
TM berada pada stata S. Jika kalimat tersebut dikenali maka, setelah selesai membaca
kalimat tersebut, TM akan akan berhenti pada stata H.
3. Sebuah edge mempunyai ‘bobot’ yang dinotasikan sebagai triple : (a, b, d). a adalah
karakter acuan bagi karakter dalam sel pita TM yang sedang dibaca head. Jika yang
dibaca head adalah karakter a maka a akan di-overwrite dengan karakter b dan head akan
berpindah satu sel ke arah d (kanan atau kiri).
4. Kondisi crash akan terjadi jika ditemui keadaan sebagai berikut :
j1
(a1, b1, c1)
(a2, b2, c2)
i
j2
(an, bn, cn)
TM sedang berada pada stata i. Jika TM sedang
membaca simbol ax ≠ a1 ≠ a2 ≠ ... ≠ an maka
TM tidak mungkin beranjak dari stata i. Jadi
pada kasus ini penelusuran (tracing) TM ber-
akhir pada stata i.
jn
Asep Juarna, Catatan Teori Bahasa dan Atutomata, Hal 7
Contoh :
Rancanglah sebuah mesin turing pengenal bahasa L = {a n b n | n ≥ 0).
Jawab :
L tersebut terdiri dari 2 kelompok kalimat yaitu ε dan non-ε. Kelompok non-ε adalah : ab,
aabb, aaabbb, dan seterusnya. Untuk dapat menerima kalimat ε TM harus mempunyai edge
dari S ke H dengan bobot (ε ,ε , R). TM menerima kalimat-kalimat : ab, aabb, aaabbb, dan
seterusnya, dengan algoritma sebagai berikut :
1. Mulai dari S, head membaca simbol a.
2. Head membaca simbol a. Tandai simbol a yang sudah dibaca tersebut, head bergerak ke
kanan mencari simbol b pasangannya.
3. Head membaca simbol b. Tandai simbol b yang sudah dibaca tersebut, head bergerak ke
kiri mencari simbol a baru yang belum dibaca/ditandai.
4. Ulangi langkah 2 dan 3.
5. Head sampai ke H hanya jika semua simbol a dan simbol b dalam kalimat a n b n selesai
dibaca.
Algoritma di atas lebih diperinci lagi sebagai berikut :
1. Mulai dari S, head membaca simbol a.
2. Overwrite a tersebut dengan suatu simbol (misalkan A) untuk menandakan bahwa a
tersebut sudah dibaca. Selanjutnya head harus bergerak ke kanan untuk mencari sebuah b
sebagai pasangan a yang sudah dibaca tersebut.
i) Jika yang ditemukan adalah simbol a maka a tersebut harus dilewati (tidak boleh
dioverwrite), dengan kata lain a dioverwrite dengan a juga dan head bergerak ke
kanan.
ii) Jika TM pernah membaca simbol b ada kemungkinan ditemukan simbol B. Simbol B
tersebut harus dilewati (tidak boleh dioverwrite), artinya B diover-write dengan B
juga dan head bergerak ke kanan.
3. Head membaca simbol b, maka b tersebut harus dioverwrite dengan simbol lain (misalnya
B) untuk menandakan bahwa b tersebut (sebagai pasangan dari a) telah dibaca, dan head
bergerak ke kiri untuk mencari simbol A.
i) Jika ditemukan B maka B tersebut harus dilewati (tidak boleh dioverwrite), dengan
kata lain B dioverwrite dengan B juga dan head bergerak ke kiri.
ii) Jika ditemukan a maka a tersebut harus dilewati (tidak boleh dioverwrite), dengan
kata lain a dioverwrite dengan a juga dan head bergerak ke kiri.
4. Head membaca simbol A, maka A tersebut harus dilewati (tidak boleh dioverwrite),
dengan kata lain A dioverwrite dengan A juga dan head bergerak ke kanan.
5. Head membaca simbol a, ulangi langkah 2 dan 3.
6. (Setelah langkah 3) head membaca simbol A, maka A tersebut harus dilewati (tidak boleh
dioverwrite), dengan kata lain A dioverwrite dengan A juga dan head bergerak ke kanan.
7. Head membaca simbol B, maka B tersebut harus dilewati (tidak boleh dioverwrite),
dengan kata lain B dioverwrite dengan A juga dan head bergerak ke kanan.
8. Head membaca simbol ε, maka ε dioverwrite dengan ε dan head bergerak ke kanan
menuju stata H.
Asep Juarna, Catatan Teori Bahasa dan Atutomata, Hal 8
Skema graf Mesin Turing di atas adalah :
(ε, ε, R)
(B, B, R)
(a, A, R)
S
(B, B, L)
(b, B, L)
1
(B, B, R)
(ε, ε, R)
(A, A, R)
2
4
H
(a, a, R)
(a, a, L)
(A, A, R)
3
(a, a, L)
Contoh :
Lakukan tracing dengan mesin turing di atas untuk kalimat-kalimat : aabb, aab.
Jawab :
i) (S,aabb) ⇒ (1,Aabb) ⇒ (1,Aabb) ⇒ (2,AaBb) ⇒ (3,AaBb) ⇒ (S,AaBb)
⇒ (1,AABb) ⇒ (1,AABb) ⇒ (2,AABB) ⇒ (2,AABB) ⇒ (4,AABB)
⇒ (4,AABB) ⇒ (4,AABBε) ⇒ (H,AABBεε)
ii) (S,aab)
⇒ (1,Aab) ⇒ (1,Aab) ⇒ (2,AaB) ⇒ (3,AaB) ⇒ (S,AaB) ⇒ (1,AAB)
⇒ (1,AAbε) ⇒ crash, karena dari node 1 tidak ada edge dengan bobot
komponen pertamanya hampa (ε)
IV. AUTOMATA HINGGA (AH)
• AH didefinisikan sebagai pasangan 5 tupel : (K, V T , M, S, Z).
K : himpunan hingga stata,
V T : himpunan hingga simbol input (alfabet)
M : fungsi transisi, menggambarkan transisi stata AH akibat pembacaan simbol
input.
Fungsi transisi ini biasanya diberikan dalam bentuk tabel.
S ∈ K : stata awal
Z ⊂ K : himpunan stata penerima
• Ada dua jenis automata hingga : deterministik (AHD, DFA = deterministic finite
automata) dan non deterministik (AHN, NFA = non deterministik finite automata).
- AHD : transisi stata AH akibat pembacaan sebuah simbol bersifat tertentu.
M(AHD) : K × V T → K
- AHN : transisi stata AH akibat pembacaan sebuah simbol bersifat tak tentu.
M(AHN) : K × V T → 2K
Asep Juarna, Catatan Teori Bahasa dan Atutomata, Hal 9
IV. 1. Automata Hingga Deterministik (AHD)
Berikut ini sebuah contoh AHD F(K, V T , M, S, Z), dimana :
K = {q0, q1, q2}
M diberikan dalam tabel berikut :
a
b
V T = {a, b}
S = q0
q0
q0
q1
Z = {q0, q1}
q1
q0
q2
q2
q2
q2
Ilustrasi graf untuk AHD F adalah sebagai berikut :
Lambang stata awal adalah node dengan anak panah.
Lambang stata awal adalah node ganda.
a
b
a
q0
q1
a
q2
b
b
Contoh kalimat yang diterima AHD : a, b, aa, ab, ba, aba, bab, abab, baba
Contoh kalimat yang tidak diterima AHD : bb, abb, abba
AHD ini menerima semua kalimat yang tersusun dari simbol a dan b yang tidak mengandung
substring bb.
Contoh :
Telusurilah, apakah kalimat-kalimat berikut diterima AHD :
abababaa, aaaabab, aaabbaba
Jawab :
i) M(q0,abababaa) ⇒ M(q0,bababaa) ⇒ M(q1,ababaa) ⇒ M(q0,babaa)
⇒ M(q1,abaa) ⇒ M(q0,baa) ⇒ M(q1,aa) ⇒ M(q0,a) ⇒ q0
Tracing berakhir di q0 (stata penerima) ⇒ kalimat abababaa diterima
ii) M(q0, aaaabab) a M(q0,aaabab) a M(q0,aabab) a M(q0,abab)
⇒ M(q0,bab) ⇒ M(q1,ab) ⇒ M(q0,b) a q1
Tracing berakhir di q1 (stata penerima) ⇒ kalimat aaaababa diterima
iii) M(q0, aaabbaba) ⇒ M(q0, aabbaba) ⇒ M(q0, abbaba) ⇒ M(q0, bbaba)
⇒ M(q1,bbaba) ⇒ M(q2,baba) ⇒ M(q2,aba) ⇒ M(q2,ba) ⇒ M(q2,a) a q2
Tracing berakhir di q2 (bukan stata penerima) ⇒ kalimat aaabbaba ditolak
Kesimpulan : sebuah kalimat diterima oleh AHD jika tracingnya berakhir di salah satu stata
penerima.
Asep Juarna, Catatan Teori Bahasa dan Atutomata, Hal 10
IV.2. Equivalensi 2 AHD
Dua buah AHD dikatakan equivalen jika keduanya dapat menerima bahasa yang
sama. Misalkan kedua AHD tersebut adalah A dan A’. Misalkan pula bahasa yang
diterima adalah bahasa L yang dibangun oleh alfabet V T = {a1, a2, a3, ..., an}.
Berikut ini algoritma untuk menguji equivalensi dua buah AHD.
1. Berikan nama kepada semua stata masing-masing AHD dengan nama berbeda.
Misalkan nama-nama tersebut adalah : S, A1, A2, ... untuk AHD A, dan : S’, A1’,
A2’, ... untuk AHD A’.
2. Buat tabel (n+1) kolom, yaitu kolom-kolom : (v, v’), (v a 1 , v a 1 ’), ..., (v a n ,
v a n ’), yaitu pasangan terurut (stata AHD A, stata AHD A’).
3. Isikan (S, S’) pada baris pertama kolom (v, v’), dimana S dan S’ masing-masing
adalah stata awal masing-masing AHD.
4. Jika terdapat edge dari S ke A1 dengan label a1 dan jika terdapat edge dari S’ ke
A1’ juga dengan label a1, isikan pasangan terurut (A1, A1’) sebagai pada baris
pertama kolom (v a 1 , v a 1 ’). Lakukan hal yang sama untuk kolom-kolom
berikutnya.
5. Perhatikan nilai-nilai pasangan terurut pada baris pertama. Jika terdapat nilai
pasangan terurut pada kolom (v a 1 , v a 1 ’) s/d (v a n , v a n ’) yang tidak sama
dengan nilai pasangan terurut (v, v’), tempatkan nilai tersebut pada kolom (v, v’)
baris-baris berikutnya. Lakukan hal yang sama seperti yang dilakukan pada
langkah (4). Lanjutkan dengan langkah (5).
6. Jika selama proses di atas dihasilkan sebuah nilai pada kolom (v, v’), dengan
komponen v merupakan stata penerima sedangkan komponen v’ bukan, atau
sebaliknya, maka kedua AHD tersebut tidak ekuivalen. Proses dihentikan.
7. Jika kondisi (6) tidak dipenuhi dan jika tidak ada lagi pasangan terurut baru yang
harus ditempatkan pada kolom (v, v’) maka proses dihentikan dan kedua AHD
tersebut ekuivalen.
Contoh :
Periksalah ekuivalensi kedua AHD berikut :
a
b
1
a
4
5
a
b
a
b
a
a
a
2
3
b
a
7
6
a
AHD A
AHD A’
Jawab :
Dengan menggunakan menggunakan algoritma di atas maka dapat dibentuk tabel
berikut :
(v, v’)
(v b , v b ’) Keterangan :
(v a , v a ’)
(1, 4)
(2,5)
(3, 6)
(2, 7)
(1, 4)
(3, 6)
(2, 7)
(3, 6)
(2, 5)
(1, 4)
(3, 6)
(1, 4)
(2, 5) adalah pasangan terurut baru
(3, 6) adalah pasangan terurut baru
(2, 7) adalah pasangan terurut baru
tidak adal lagi pasangan terurut baru
Asep Juarna : Catatan Teori Bahasa dan Automata, hal 11
b
IV. 3. Mesin Stata Hingga (MSH)
• MSH atau FSM (Finite State Machine) adalah sebuah varians automata hingga.
MSH sering juga disebut sebagai automata hingga beroutput atau mesin
sekuensial.
• MSH didefinisikan sebagai pasangan 6 tupel F(K, V T , S, Z, f, g) dimana :
K : himpunan hingga stata,
V T : himpunan hingga simbol input (alfabet)
S ∈ K : stata awal
Z : himpunan hingga simbol output
f : K × V T → K disebut fungsi next state
g : K × V T → Z disebut fungsi output
Contoh :
Berikut ini adalah contoh MSH dengan 2 simbol input, 3 stata, dan 3 simbol output :
K = {q0, q1, q2}
fungsi f :
fungsi g :
S = q0
f(q0,a) = q1
f(q0,b) = q2
f(q0,a) = x
f(q0,b) = y
f(q1,a) = q2
f(q1,b) = q1
f(q1,a) = x
f(q1,b) = z
V T = {a, b}
Z = {x, y, z}
f(q2,a) = q0
f(q2,b) = q1
f(q2,a) = z
f(q2,b) = y
MSH dapat disajikan dalam bentuk tabel atau graf. Untuk MSH contoh di atas tabel
dan grafnya masing-masing adalah :
a
a b q1, x q2, y b
q1 q2, x q1, z q2 q0, z q1, y
b
q0
q0
x
z
q1
x
y
a
a
b
q2
y
x
Jika MSH di atas mendapat untai masukan “aaba” maka akan dihasilkan :
- untai keluaran : xxyx
- untai stata : q0 q1 q2 q1 q2
IV. 4. MSH penjumlah biner
MSH dapat disajikan sebagai penjumlah biner. Sifat penjumlahan biner bergantung
pada statusnya : carry atau not carry.
Pada status not carry berlaku : 0 + 0 = 0,
1 + 0 = 0 + 1 = 1,
1+1=0
Pada status carry berlaku
: 0 + 0 = 1,
1 + 0 = 0 + 1 = 0,
1+1=1
Pada status not carry blank (b) menjadi b, sedangkan pada status carry menjadi 1.
Nilai setiap tupel untuk MSH ini adalah :
K = N (not carry), C (carry), dan S (stop)
S=N
V T = {00, 01, 10, 11, b}
Z = {0, 1, b}
N
C
00
N, 0
N, 1
Tabel MSH
01
10
N, 1 N, 1
C, 0 C, 0
11
C, 0
C, 1
b
S, b
S, 1
Asep Juarna : Catatan Teori Bahasa dan Automata, hal 12
Graf MSH penjumlah biner :
00
1
0
1
00
01
0
10
N
11
0
C
01
0
1
10
1
b
11
b
b
1
S
Contoh :
Hitunglah : 1101011 + 0111011
Jawab :
Input = pasangan digit kedua bilangan, mulai dari LSB (least significant bit)
=
11, 11, 00, 11, 01, 11, 11, b
Output =
0, 1, 1, 0, 0, 1, 1, 1 (jawab : dibaca dari kanan)
Stata = N, C, C, N, C, C, C, C, S
Periksa :
1101011
0111011 +
11100110
IV. 5. Ekspresi Regular
• Bahasa regular dapat dinyatakan sebagai ekspresi regular dengan menggunakan 3
operator : concate, alternate, dan closure.
• Dua buah ekspresi regular adalah ekuivalen jika keduanya menyatakan bahasa
yang sama
Contoh :
L 1 = {a n ba m  n ≥ 1, m ≥ 1} ⇔ er 1 = a + b a +
L 2 = {a n ba m  n ≥ 0, m ≥ 0} ⇔ er 2 = a* b a*
Perhatikan bahwa kita tidak bisa membuat ekspresi regular dari bahasa
L 3 = {a n ba n  n ≥ 1} atau L 4 = {a n ba n  n ≥ 0}, karena keduanya tidak dihasilkan
dari grammar regular.
Kesamaan 2 ekspresi regular :
(a b)* a = a (b a)*
Bukti :
(a b)* a = (ε(ab)(abab)...) a = (ε a(aba)(ababa)...) = (a(aba)(ababa)...)
= a (ε(ba)(baba)...) = a (b a)*
Latihan 2. Buktikan kesamaan ekspresi regular berikut :
1. (a*b)* = (ab)*
2. (ab*)* = (ab)*
3. (a* b)* a* = a* (b a*)*
4. (a a*)(εa) = a*
5. a(b aa)* b = a a* b(a a* b)*
Asep Juarna : Catatan Teori Bahasa dan Automata, hal 13
IV. 6. Automata Hingga Nondeterministik (AHN)
Berikut ini sebuah contoh AHN F(K, V T , M, S, Z), dimana :
K = {q 0 , q 1, q 2 ,q 3 , q 4 }
M diberikan dalam tabel berikut :
a
V T = {a, b,c}
b c
S = q0 q0 {q 0 , q 1} {q 0 , q 2 } {q 0 , q 3 }
Z = {q 4 } q1 {q 1, q 4 } {q 1} {q 1}
q2 {q 2 } {q 2 , q 4 } {q 2 }
q3 {q 3 } {q 3 } {q 3 , q 4 }
q4 ∅ ∅ ∅
Ilustrasi graf untuk AHN F adalah sebagai berikut :
a, b, c
a, b, c
a
q1
q0
c
b
a
b
q3 q2
a, b, c a, b, c
q4
c
Contoh kalimat yang diterima AHN di atas : aa, bb, cc, aaa, abb, bcc, cbb
Contoh kalimat yang tidak diterima AHN di atas : a, b, c, ab, ba, ac, bc
Fungsi transisi M sebuah AHN dapat diperluas sebagai berikut :
1. M(q, ε) = {q} untuk setiap q ∈ K
2. M(q, t T) = ∪ M(p i , T) dimana t ∈ V T , T adalah V T *, dan M(q, t) = {p i }
3. M({q 1, q 2 , ..., q n }, x) = ∪ M(q i ,x), untuk x ∈ V T *
Sebuah kalimat di terima AHN jika :
• salah satu tracing-nya berakhir di stata penerima, atau
• himpunan stata setelah membaca string tersebut mengandung stata penerima
Asep Juarna : Catatan Teori Bahasa dan Automata, hal 10
Contoh :
Telusurilah, apakah kalimat-kalimat berikut diterima AHN : ab, abc, aabc, aabb
Jawab :
i) M(q 0 ,ab) ⇒ M(q 0 ,b) ∪ M(q 1 ,b) ⇒ {q 0 , q 2 } ∪ {q 1 } = {q 0 , q 1, q 2 }
Himpunan stata tidak mengandung stata penerima ⇒ kalimat ab tidak diterima
ii) M(q 0 ,abc) ⇒ M(q 0 ,bc) ∪ M(q 1 ,bc) ⇒ {M(q 0 ,c) ∪ M(q 2 ,c)} ∪ M(q 1, c)
⇒ {{ q 0 , q 3 }∪{ q 2 }}∪{ q 1} = {q 0 , q 1, q 2 ,q 3 }
Himpunan stata tidak mengandung stata penerima ⇒ kalimat abc tidak diterima
iii) M(q 0 ,aabc) ⇒ M(q 0 ,abc) ∪ M(q 1 ,abc) ⇒ {M(q 0 ,bc) ∪ M(q 1 ,bc)} ∪ M(q 1 ,bc)
⇒ {{M(q 0 , c) ∪ M(q 2 ,c)} ∪ M(q 1 , c)} ∪ M(q 1, c)
⇒ {{{ q 0 , q 3 }∪ { q 2 }} ∪ {q 1}} ∪ {q 1} = {q 0 , q 1, q 2 ,q 3 }
Himpunan stata tidak mengandung stata penerima ⇒ kalimat aabc tidak diterima
iv) M(q 0 ,aabb) ⇒ M(q 0 ,abb) ∪ M(q 1 ,abb) ⇒ {M(q 0 ,bb) ∪ M(q 1 ,bb)} ∪ M(q 1 ,bb)
⇒ {{M(q 0 , b) ∪ M(q 2 ,b)} ∪ M(q 1, b)} ∪ M(q 1, b)
⇒ {{{ q 0 , q 2 }∪ { q 2 , q 4 }} ∪ {q 1}} ∪ {q 1} = {q 0 , q 1, q 2 , q 4 }
Himpunan stata tidak mengandung stata penerima ⇒ kalimat aabb diterima
AHN Dengan Transisi Hampa
Perhatikan AHN berikut.
1
ε
q0
0
q1
AHN di atas mengandung ruas dengan bobot ε. AHN demikian dinamakan AHN dengan
transisi ε, atau singkatnya AHN-ε. AHN-ε di atas menerima bahasa L = {1 i 0 j i , j ≥ 0}
IV. 7. Ekuivalensi AHN, AHD, dan GR
AHD bisa dibentuk dari AHN.
GR bisa dibentuk dari AHD.
AHN bisa dibentuk dari GR.
AHN
AHD
GR
Pembentukan AHD dari AHN
Diberikan sebuah AHN F = (K, V T , M, S, Z). Akan dibentuk sebuah AHD F’ = (K’,
V T ’, M’, S’, Z’) dari AHN F tersebut. Algoritma pembentukannya adalah sbb. :
1. Tetapkan : S’ = S dan V T ’ = V T
2. Copykan tabel AHN F sebagai tabel AHD F’. Mula-mula K’ = K dan M’ = M
3. Setiap stata q yang merupakan nilai (atau peta) dari fungsi M dan q ∉ K, ditetapkan
sebagai elemen baru dari K’. Tempatkan q tersebut pada kolom Stata M’, lakukan
pemetaan berdasarkan fungsi M.
4. Ulangi langkah (3) sampai tidak diperoleh stata baru.
5. Elemen Z’ adalah semua stata yang mengandung stata elemen Z.
Asep Juarna : Catatan Teori Bahasa dan Automata, hal 11
Contoh :
Berikut ini diberikan sebuah AHN F = (K, V T , M, S, Z) dengan :
K = {A, B, C}, V T = {a, b}, S = A, Z = {C}, dan M didefinisikan sebagai berikut :
Stata K
Input
AHN F
a
b
A
[A,B]
C
B
A
B
C
B
[A,B]
Tentukan AHD hasil transformasinya.
Jawab :
Berdasarkan algoritma di atas, maka :
1. S’ = S = A, V T ’ = V T = {a, b}.
2. Hasil copy tabel AHN F menghasilkan tabel AHD F’ berikut :
Stata K’
Input
AHD F’
a
b
A
[A,B]
C
B
A
B
C
B
[A,B]
3. Pada tabel AHD F’ di atas terdapat stata baru yaitu [A,B]. Pemetaan [A,B] adalah :
M([A,B],a) = M(A,a) ∪ M(B,a) = [A,B] ∪ A = [A,B], dan
M([A,B],b) = M(A,b) ∪ M(B,b) = C ∪ B = [B,C], sehingga diperoleh tabel berikut :
Stata K’
Input
dari AHD F’
a
b
A
[A,B]
C
B
A
B
C
B
[A,B]
[A,B]
[A,B]
[B,C]
4. Langkah (3) di atas menghasilkan stata baru yaitu [B,C]. Setelah pemetaan terhadap
[B,C] diperoleh tabel berikut :
Stata K’
Input
dari AHD F’
a
b
A
[A,B]
C
B
A
B
C
B
[A,B]
[A,B]
[A,B]
[B,C]
[B,C]
[A,B]
[A,B]
5. Setelah langkah (4) di atas tidak terdapat lagi stata baru.
Dengan demikian AHD F’ yang dihasilkan adalah : AHD F’ = (K’, V T ’, M’, S’, Z’),
dimana : K’ = {A, B, C, [A,B], [B,C]}, V T ’ = {a, b}, S’ = A, Z’ = {C, [B,C]}. Fungsi
transisi M’ serta graf dari AHD F’ adalah sebagai berikut :
Asep Juarna : Catatan Teori Bahasa dan Automata, hal 12
B
Stata K’
dari AHD F’
A
B
C
[A,B]
[B,C]
Input
a
[A,B]
A
B
[A,B]
[A,B]
b
a
b
C
B
[A,B]
[B,C]
[A,B]
A
a
a
C
b
b
[A,B]
b
[B,C]
a, b
a
Pembentukan GR dari AHD
Diketahui sebuah AHD F = (K, V T , M, S, Z). Akan dibentuk GR G = (V T ’,V N , S’, Q).
Algoritma pembentukan GR dari AHD adalah sebagai berikut :
1. Tetapkan V T ’ = V T , S’ = S, V N = S
2. Jika A p , A q ∈ K dan a ∈ V T , maka :
 A p → aA q , jika A q ∉ Z
M(A p , a) = A q ekuivalen dengan produksi : 
jika A q ∈ Z
A p → a ,
Contoh
Diketahui sebuah AHD F dengan Z = {S} dan fungsi transisi M sebagai berikut :
Stata K
Input
Dengan algoritma di atas maka diperoleh Q(GR) sbb. :
AHD F
0
1
M(S,0) = B ⇔ S → 0B
M(S,1) = A⇔ S → 1A
S
B
A
M(A,0) = C ⇔ A → 0C
M(A,1) = S⇔ A → 1
A
C
S
M(B,0) = S ⇔ B → 0
M(B,1) = C⇔ B→ 1C
B
S
C
M(C,0) = A ⇔ C → 0A
M(C,1) = B⇔ C → 1B
C
A
B
GR yang dihasilkan adalah G(V T ’,V N , S’, Q), dengan V T ’ = {0,1}, V N = {S, A, B, C},
S’ = S, dan Q = {S → 0B, S → 1A, A → 0C, B→ 1C, C → 0A, C → 1B, A → 1, B → 0}
Pembentukan AHN dari GR
Diketahui GR G = (V T ,V N , S, Q). Akan dibentuk AHN F = (K,V T ’, M, S’, Z).
Algoritma pembentukan AHN dari GR :
1. Tetapkan V T ’ = V T , S’ = S, K = V N
2. Produksi A p → a A q ekuivalen dengan M(A p , a) = A q
Produksi A p → a ekuivalen dengan M(A p , a) = X, dimana X ∉ V N
3. K = K ∪ {X}
4. Z = {X}
Asep Juarna : Catatan Teori Bahasa dan Automata, hal 13
Contoh
Diketahui GR G = (V T ,V N , S, Q) dengan : V T = {a, b}, V N = {S, A, B}, S = S, dan
Q = {S → aS, S → bA, A → aA, A → aB, B → b}
Terapkan algoritma di atas untuk memperoleh AHN F sebagai berikut :
1. V T ’ = V T = {a, b}, S’ = S, K = V N = {S, A, B}
2. S → aS ⇔ M(S,a) = S, S → bA ⇔ M(S,b) = A,
A → aA ⇔ M(A,a) = A, A → aB ⇔ M(A,a) = B,
B → b ⇔ M(B,b) = X
AHN yang diperoleh : F(K,V T ’, M, S’, Z), dengan
K = {S, A, B, X}, V T ’ = {a, b}, S’ = S, Z = {X},
Stata K
AHN F
S
A
B
X
Tabel M :
Input
a
S
[A,B]
φ
φ
b
A
φ
X
φ
IV.8. Ekuivalensi Ahn-ε Dengan ER (Ekspresi Regular)
Jenis ER
Simbol hampa
ER hampa
Simbol ER AHN
ε q0
φ atau {}
q1
q0
r
ER umum r
Alternation r1 | r2
q0
q1
ε
r1
ε
q0
ε
ε
q1
r2
Concatenation
r1 r2
ε
ε
r1
q0
ε
r2
q1
ε
Kleene Clossure
r*
ε
q0
ε
r
q1
ε
Asep Juarna : Catatan Teori Bahasa dan Automata, hal 14
Contoh :
Tentukan AHN untuk ekspresi regular r = 0(1 | 23)*
Jawab :
0
r1 = 0 ⇔ q0
r2 = 1 ⇔ q3
r 3 = 23 ⇔ q5
q1
1
q4
2
3
q6
q7
1
q3
r 4 = r 2 | r 3 = 1| 23 ⇔
q4
ε
ε
q2
q8
ε
ε
2
3
q5
q6
q7
ε
1
q3
ε
r 5 = r 4 * = (1| 23)* ⇔
q1
q4
ε
ε
ε
q2
q8
ε
2
q5
q9
ε
3
q6
q7
ε
1
q3
ε
0
r = r 5 = 0(1| 23)* ⇔
q0
q1
q4
ε
ε
ε
q2
q8
ε
2
q5
ε
3
q6
q9
q7
Asep Juarna : Catatan Teori Bahasa dan Automata, hal 15
V. GRAMMAR CONTEXT-FREE DAN PARSING
Bentuk umum produksi CFG adalah : α → β, α ∈ V N , β ∈ (V N V T )*
Analisis sintaks adalah penelusuran sebuah kalimat (atau sentensial) sampai pada simbol
awal grammar. Analisis sintaks dapat dilakukan melalui derivasi atau parsing.
Penelusuran melalui parsing menghasilkan pohon sintaks.
Contoh 1 :
Diketahui grammar G 1 = {I → HI HIA, H → abc...z, A → 012...9}
dengan I adalah simbol awal. Berikut ini kedua cara analisa sintaks untuk kalimat x23b.
cara 1 (derivasi)
cara 2 (parsing)
I ⇒ IH
I
⇒ IAH
⇒ IAAH
I
H
⇒ HAAH
⇒ xAAH
I
A
b
⇒ x2AH
⇒ x23H
I
A
3
⇒ x23b
H
2
x
Sebuah kalimat dapat saja mempunyai lebih dari satu pohon.
Contoh 2 :
Diketahui grammar G 2 = {S → SOSA , O → *+, A → 012...9}
Kalimat : 2*3+7 mempunyai dua pohon sintaks berikut :
S
S
S O
A *
2
S
S
O S O S S O S
A + A A * A
S
+ A
7
3
7
2
3
Sebuah kalimat yang mempunyai lebih dari satu pohon sintaks disebut kalimat ambigu
(ambiguous). Grammar yang menghasilkan paling sedikit sebuah kalimat ambigu disebut
grammar ambigu.
5.1. Metoda Parsing
Ada 2 metoda parsing : top-down dan bottom-up.
Parsing top-down : Diberikan kalimat x sebagai input. Parsing dimulai dari simbol awal
S sampai kalimat x nyata (atau tidak nyata jika kalimat x memang
tidak bisa diturunkan dari S) dari pembacaan semua leaf dari pohon
parsing jika dibaca dari kiri ke kanan.
Parsing bottom-up : Diberikan kalimat x sebagai input. Parsing dimulai dari kalimat x
yang nyata dari pembacaan semua leaf pohon parsing dari kiri ke
kanan sampai tiba di simbol awal S (atau tidak sampai di S jika
kalimat x memang tidak bisa diturunkan dari S)
Parsing Top-down
Ada 2 kelas metoda parsing top-down, yaitu kelas metoda dengan backup dan kelas
metoda tanpa backup. Contoh metoda kelas dengan backup adalah metoda Brute-Force,
sedangkan contoh metoda kelas tanpa backup adalah metoda recursive descent.
Metoda Brute-Force
Kelas metoda dengan backup, termasuk metoda Brute-Force, adalah kelas metoda
parsing yang menggunakan produksi alternatif, jika ada, ketika hasil penggunaan sebuah
produksi tidak sesuai dengan simbol input. Penggunaan produksi sesuai dengan nomor
urut produksi.
Contoh 3 :
Diberikan grammar G = {S → aAdaB, A → bc, B → ccdddc}. Gunakan metoda
Brute-Force untuk melakukan analisis sintaks terhadap kalimat x = accd.
S
S
S
a
a
A
A
d
d
Hasil : Hasil : a Hasil : ab
Input : Input : a Input : ac
Sisa : accd Sisa : ccd Sisa : cd
Penjelasan : Gunakan produk- Penjelasan : Hasil = Input. Penjelasan : Hasil ≠ Input.
si S pertama. Masukkan sim- Gunakan produksi A pertama. Backup : Gunakan produksi A
bol terkiri kalimat sebagai alternatif pertama.
input.
S S S
a
A
d
b
a
A
d
a
c c
Hasil : ac Hasil : acd
Input : ac Input : acc
Sisa : cd Sisa : c
Penjelasan : Hasil = Input. Penjelasan : Hasil ≠ Input.
Karakter berikutnya adalah Tidak ada lagi produksi A
simbol alternatif, backup : gunakan
terminal, produksi S alternatif pertama.
Hasil
dibandingkan dengan Input.
B
Hasil : a
Input : a
Sisa : ccd
Penjelasan : Hasil = Input.
Gunakan produksi B pertama.
S
a
S
B
c
c
a
B
d
c
Hasil : ac
Input : ac
Sisa : cd
Penjelasan : Hasil = Input.
Karakter berikutnya adalah
simbol
terminal,
Hasil
dibandingkan dengan Input.
S
a
c
d
B
c
Hasil : acc
Input : acc
Sisa : d
Penjelasan : Hasil = Input.
Karakter berikutnya adalah
simbol
terminal,
Hasil
dibandingkan dengan Input.
c
d
Hasil : accd
Input : accd
Sisa :
Penjelasan : Hasil = Input.
SELESAI, SUKSES
Metoda Brute-Force tidak dapat menggunakan grammar rekursi kiri, yaitu grammar yang
mengandung produksi rekursi kiri (left recursion) : A → A∝. Produksi rekursi kiri akan
menyebabkan parsing mengalami looping tak hingga.
Contoh 4 :
Diberikan grammar G = {S → aAc, A → Abε}. Gunakan metoda Brute-Force untuk
melakukan analisis sintaks terhadap kalimat x = ac.
S
S
S
a
a
A
A
A
Hasil :
Input :
Sisa : ac
Penjelasan : Masukkan simbol
terkiri kalimat sebagai input.
Gunakan produksi S pertama.
S
A
A
A
b
Hasil : a
Input : a
Sisa : c
Hasil : a
Penjelasan : Hasil = Input. Input : a
Sisa : c
Gunakan produksi A pertama. Penjelasan : Hasil = Input.
Gunakan produksi A pertama.
S
a
c
c
c
a
A
A
b
A
b
A
Hasil : a
Input : a
Sisa : c
Penjelasan : Hasil = Input.
Gunakan produksi A pertama.
b
b
b
dan seterusnya...... (looping)
Hasil : a
Input : a
Sisa : c
Penjelasan : Hasil = Input.
Gunakan produksi A pertama.
Agar tidak menghasilkan looping tak hingga, grammar rekursi kiri harus ditransformasi.
Untuk contoh di atas transformasi berarti merubah produksi A → Ab menjadi A → bA.
Metoda Recursive-Descent
• Kelas metoda tanpa backup, termasuk metoda recursive descent, adalah kelas metoda
parsing yang tidak menggunakan produksi alternatif ketika hasil akibat penggunaan
sebuah produksi tidak sesuai dengan simbol input. Jika produksi A mempunyai dua
buah ruas kanan atau lebih maka produksi yang dipilih untuk digunakan adalah
produksi dengan simbol pertama ruas kanannya sama dengan input yang sedang
dibaca. Jika tidak ada produksi yang demikian maka dikatakan bahwa parsing tidak
dapat dilakukan.
• Ketentuan produksi yang digunakan metoda recursive descent adalah : Jika terdapat
dua atau lebih produksi dengan ruas kiri yang sama maka karakter pertama dari
semua ruas kanan produksi tersebut tidak boleh sama. Ketentuan ini tidak melarang
adanya produksi yang bersifat rekursi kiri.
Contoh 5 :
Diketahui grammar G = {S → aBA, A → a, B → bd}. Gunakan metoda recursive
descent untuk melakukan analisis sintaks terhadap kalimat x = ac.
S
S
a
Hasil :
Input :
Sisa : ab
Penjelasan : Masukkan simbol
terkiri kalimat sebagai input.
Gunakan produksi S dengan
simbol pertama ruas kanan = a
B
Hasil : a
Input : a
Sisa : c
Penjelasan : Hasil = Input.
Gunakan produksi B dengan
simbol pertama ruas kanan =
c. Karena produksi demikian
maka parsing gagal dilakukan.
SELESAI,
PARSING GAGAL
Parsing Bottom-Up
Salah satu contoh menarik dari parsing bottom-up adalah parsing pada grammar preseden
sederhana (GPS). Sebelum sampai ke parsing tersebut, akan dikemukakan beberapa
pengertian dasar serta relasi yang ada pada GPS.
Pengertian Dasar
• Jika α dan x keduanya diderivasi dari simbol awal grammar tertentu, maka α disebut
sentensial jika α ∈ (V T  V N )*, dan x disebut kalimat jika x ∈ (V T )*
• Misalkan α = Q 1 β Q 2 adalah sentensial dan A ∈ V N :
- β adalah frase dari sentensial α jika : S ⇒ ... ⇒ Q 1 A Q 2 dan A⇒ ... ⇒ β
- β adalah simple frase dari sentensial α jika : S ⇒ ... ⇒ Q 1 A Q 2 dan A⇒ β
- Simple frase terkiri dinamakan handel
- frase, simple frase, dan handel adalah string dengan panjang 0 atau lebih..
Contoh 6 :
(1) I ⇒ I H
Hb adalah sentensial dan b adalah simple frase
⇒ H H (dibandingkan dengan Q 1 β Q 2 maka Q 1 = H, β = b, dan Q 2 = ε)
⇒ H b Perhatikan : simple frase (b) adalah yang terakhir diturunkan
(2) I ⇒ I H
Hb adalah sentensial dan H adalah simple frase
⇒Ib
(dibandingkan dengan Q 1 β Q 2 maka Q 1 = ε, β = H, dan Q 2 = b)
⇒Hb
Perhatikan : simple frase (H) adalah yang terakhir diturunkan
Sentensial Hb mempunyai dua simple frase (b dan H), sedangkan handelnya adalah H.
Relasi Preseden dan Grammar Preseden Sederhana
• Relasi preseden adalah relasi antara 2 simbol grammar (baik V T maupun V N )
dimana paling tidak salah satu simbol tersebut adalah komponen handel.
• Misalkan S dan R adalah 2 simbol. Ada 3 relasi preseden yang : ←, ↔, dan →
U
U
U
............... R S
......R S......
R S...............
 handel 
 handel 
 handel 
Relasi : R → S
Relasi : R ↔ S
Relasi : R ← S
Perhatikan : komponen handel selalu ‘menunjuk’ yang simbol lainnya.
Contoh 7 :
Diketahui grammar dengan G = {Z → bMb, M → (L a, L → Ma)}. Dari 3 sentensial :
bab, b(Lb, b(Ma)b, tentukan handel dan relasi yang ada.
b(Lb
b(Ma)b
bab
Z
Z
Z
b
M
b
b
a
Handel : a
Relasi : b ← a, a → b
M
b
b
(
L
Handel : (L
Relasi : b ← (, (↔ L,
L→b
M
(
b
L
M
a
)
Handel : Ma)
Relasi : (←M, M ↔ a,
a ↔), ) → b
• Secara umum : jika A → aBc adalah sebuah produksi maka :
- aBc adalah handel dari sentensial yang mengandung string “aBc”
- relasi preseden antara a, B, dan c adalah : a ↔ B, B ↔ c
• Dengan memperhatikan ruas kanan produksi yang ada serta berbagai sentensial yang
dapat diderivasi dari Z maka semua relasi preseden tercantum dalam tabel berikut :
Z
b
M
L
a
(
)
Z
b
M
L
a
(
)
















Grammar G disebut grammar preseden sederhana jika :
1. paling banyak terdapat satu relasi antara setiap dua simbolnya
2. tidak terdapat dua produksi produksi dengan ruas kanan yang sama
Parsing Grammar Preseden Sederhana
Prosedur parsing :
1. Buat tabel 3 kolom dengan label : sentensial dan relasi, handel, dan ruas kiri produksi.
2. Tuliskan kalimat (atau sentensial) yang diselidiki pada baris pertama kolom pertama.
3. Dengan menggunakan tabel relasi preseden cantumkan relasi preseden antara setiap
dua simbol yang bertetangga.
4. Tentukan handel dari sentensial tersebut. Handel adalah string yang dibatasi “←“
terakhir dan “→ “ pertama jika dilakukan penelusuran dari kiri atau yang saling
mempunyai relasi “↔“. Handel tersebut pastilah merupakan ruas kanan produksi,
karena itu tentukan ruas kiri dari handel tersebut.
5. Ganti handel dengan ruas kiri produksinya. GOTO 3.
6. Kalimat yang diselidiki adalah benar dapat diderivasi dari simbol awal jika kolom
“ruas kiri produksi” menghasilkan simbol awal.
Contoh 8 :
Lakukan parsing atas kalimat x = b(aa)b berdasarkan grammar G di atas.
sentensial dan relasi
handel
ruas kiri produksi
a
M
b ← (← a → a ↔)→ b
Ma)
L
b ← (← M ↔ a ↔)→ b
(L
M
b ← (↔ L→ b
bMb
Z
b↔M↔b
Prosedur parsing sampai di simbol awal (Z). Maka kalimat “b(aa)b” memang dapat
diderivasi dari simbol awal Z dengan menggunakan grammar G.
5.2. Bentuk Normal Chomsky
• Bentuk normal Chomsky (Chomsky Normal Form, CNF) adalah grammar bebas
konteks (CFG) dengan setiap produksinya berbentuk : A → BC atau A → a.
• Transformasi CFG ke CNF adalah trnasformasi berikut :
A → α , dimana :
α ∈ (V N V T )*
A → BC, atau
A→a
• 4 langkah konversi CFG – CNF adalah sebagai berikut :
     1. Eliminir semua produksi hampa
    2. Eliminir semua produksi unitas
   3. Terapkan prinsip batasan bentuk ruas kanan produksi
  4. Terapkan prinsip batasan panjang ruas kanan produksi
• Penjelasan Tentang 4 Langkah Konversi
   1. Eliminasi produksi hampa
  Produksi hampa dikaitkan dengan pengertian nullable
 Suatu simbol A ∈ V N dikatakan nullable jika :
  (a) terkait dengan produksi berbentuk : A → ε, atau
    (b) terkait dengan derivasi berbentuk : A ⇒...⇒ ε
          Eliminasi yang dilakukan terhadap simbol nullable adalah :
         (a) Buang produksi hampa
        (b) Tambahkan produksi lain yang merupakan produksi lama tetapi simbol nullable-
       nya yang di ruas kanan produksi dicoret.
      Contoh 9 :
     Lakukan eliminasi produksi hampa terhadap himpunan produksi berikut :
    Q = { S → aXbaYa, X → Yε, Y → bX}
                  Solusi :
                 • Simbol nullable adalah X (karena X → ε) dan Y (karena Y ⇒ X ⇒ ε)
                          • Dua langkah eliminasi simbol nullable adalah :
                           - langkah (a) menghilangkan produksi X → ε
                             - langkah (b) menambahkan produksi S → b (pencoretan simbol nullable X pada
                              produksi S → Xb) dan produksi S → aa (pencoretan simbol nullable Y pada
                                 produksi S → aYa)
                                  • Himpunan produksi setelah dilakukan eliminasi produksi hampa adalah :
                                   Q = {S → aXbaYabaa, X → Y, Y → bX}
2. Eliminasi produksi unitas
Produksi unitas berbentuk A → B, dimana A,B ∈ V N

Jika ada produksi berbentuk : A → B , atau derivasi A ⇒ X1 ⇒ X 2 ⇒ ... ⇒ B ,
dan jika ada produksi non-unitas dari B berbentuk : B → α1 α 2 ...α n , maka
eliminasi yang dilakukan akan menghapus produksi A → B dan menghasilkan
produksi : A → α1 α 2 ...α n .
Asep Juarna, Catatan Teori Bahasa dan Automata, hal 26

Tidak dilakukan eliminasi terhadap derivasi tertutup karena tidak akan menghasil-
kan produksi baru. Bentuk derivasi tertutup adalah : A ⇒ X1 ⇒ X 2 ⇒ ... ⇒ A
Contoh 10 :
Lakukan eliminasi produksi unitas terhadap himpunan produksi berikut :
Q = {S → Abb, A → Bb, B → Sa}
Solusi :
Untuk memudahkan, pisahkan produksi unitas dan non-unitas :
Produksi unitas : S → A, A → B, B → S
Produksi non unitas : S → bb, A → b, B → a
Proses eliminasi yang dilakukan adalah :
S → A dan A → b menghapus S → A dan menghasilkan S → b
S ⇒ A ⇒ B dan B → a menghasilkan S → a
A → B dan B → a menghapus A → B dan menghasilkan A → a
A ⇒ B ⇒ S dan S → bb menghasilkan A → bb
B → S dan S → bb menghapus B → S dan menghasilkan B → bb
B ⇒ S ⇒ A dan A → b menghasilkan B → b
Perhatikan bahwa derivasi S ⇒ A ⇒ B ⇒ S (derivasi tertutup) dan produksi S → bb
akan menghasilkan produksi S → bb yang jelas bukan merupakan produksi baru.
Karena itu terhadap derivasi ini tidak dilakukan eliminasi.
3. Penerapan batasan bentuk ruas kanan produksi
Penerapan batasan bentuk ruas kanan produksi adalah mengubah semua bentuk
produksi ke dalam 2 bentuk berikut : A → a dan A → B1 B2 ... Bn , n ≥ 2.
Contoh 11:
Terapkan batasan bentuk ruas kanan produksi terhadap himpunan produksi berikut :
Q = {S → Aa, A → bAa}
Solusi :
- produksi S → Aa diubah menjadi : S → AX a , X a → a
- produksi A → bAa diubah menjdi : A → X b A X a , X a → a, X b → b
sehingga himpunan produksi menjadi :
Q = {S → AX a , A → X b A X a , X a → a, X b → b}
4. Penerapan batasan panjang ruas kanan produksi
Penerapan batasan panjang ruas kanan produksi adalah mengubah semua bentuk
produksi sehingga panjang untai ruas kanannya ≤ 2.
Contoh 12 :
Terapkan batasan panjang ruas kanan produksi terhadap himpunan produksi berikut :
Q = {S → ABCDABC, B → X b B X a }
Solusi :
- produksi S → ABCD diubah menjadi : S → AT1 , T1 → BT 2 , T 2 → CD
- produksi S → ABC diubah menjadi : S → AT 3 , T 3 → BC
- produksi B → X b B X a diubah menjadi : B → X b T 4 , T 4 → B X a
Asep Juarna, Catatan Teori Bahasa dan Automata, hal 27
sehingga himpunan produksi menjadi :
Q = {S → AT1 , T1 → BT 2 , T 2 → CD, S → AT 3 , T 3 → BC, B → X b T 4 ,
T4 → B X a }

Contoh 13 : Penyelesaian Konversi CFG ke CNF
Diberikan Q = {S → AACD , A → aAbε , C → aCa , D → aDabDbε }
Transformasikan himpunan produksi tersebut ke dalam bentuk CNF-nya.
1. Eliminasi Produksi Hampa
Dari bentuk Q di atas, maka simbol nullable adalah A dan D. Dua langkah
eliminasi yang dilakukan adalah :
- penghilangan produksi hampa A → ε dan D → ε
- pembentukan produksi hampa dari produksi yang mengandung simbol nullable :
• dari S → AACD dibentuk : S → ACDAACACCDC
• dari A → aAb dibentuk : A → ab
• dari D → aDabDb dibentuk : D → aabb
Dengan demikian Q berubah menjadi :
Q = {S → AACDACDAACACCDC ,
A → aAbab , C → aca , D → aDabDbaabb }
2. Eliminasi Produksi Unitas
Q hasil langkah pertama di atas mengandung satu produksi unitas : S → C. Proses
eliminasi yang dilakukan adalah :
S → C dan C → aca menghapus S → C dan menghasilkan S → aca
Dengan demikian Q berubah menjadi :
Q = {S → AACDACDAACACCDaca ,
A → aAbab , C → aca , D → aDabDbaabb }
3. Penerapan Batasan Bentuk Ruas Kanan
Setelah langkah 2, ternyata Q masih mengandung produksi-prosuksi yang tidak
ber-bentuk A → a dan A → B1 B2 ... Bn (n ≥ 2). Produksi-produksi tersebut
adalah :
S → aC, A → aAbab, C → aC, D → aDabDbaabb. Bentuk-bentuk
produksi ini diubah sebagai berikut :
S → aC menjadi S → X a C dan X a → a
A → aAbab menjadi A → X a A X b  X a X b dan X a → a, X b → b
C → aC menjadi C → X a C dan X a → a
D → aDabDbaabb menjadi D → X a D X a  X b D X b  X a X a  X b X b
dan X a → a, X b → b
Bentuk Grammar sampai langkah 3 ini adalah :
Q = { S → AACDACDAACACCD X a Ca , A → X a A X b  X a X b ,
C → X a Ca , D → X a D X a  X b D X b  X a X a  X b X b ,
Asep Juarna, Catatan Teori Bahasa dan Automata, hal 28
X a → a , X b → b}
4. Penerapan Batasan Panjang Ruas Kanan
Bentuk Q terakhir masih mengandung produksi-produksi dengan panjang untai
ruas kanan ≥ 2. Produksi-produksi tersebut adalah : S → AACDACDAAC ,
A → X a AX b , D → X a DX a X b DX b . Bentuk-bentuk produksi ini diubah
sebagai berikut :
S → AACD menjadi : S → A T1 , T1 → A T 2 , T 2 → CD
S → ACD menjadi : S → A T 2 , T 2 → CD
S → AAC menjadi : S → A T 3 , T 3 → AC
A → X a AX b menjadi : A → X a T 4 , T 4 → AX b
D → X a DX a menjadi : D → X a T 5 , T 5 → DX a
D → X b DX b menjadi : D → X b T 6 , T 6 → DX b
Bentuk grammar sampai langkah 4 ini adalah bentuk CNF, yaitu :
Q = {S → A T1  A T 2  A T 3  ACCDX a Ca,
T1 → A T 2 , T 2 → CD , T 3 → AC ,
A → X a T 4  Xa Xb , T 4 → A Xb,
C → X a Ca,
D → X a T 5  X b T 6  X a X a  X b X b , T 5 → DX a , T 6 → DX b ,
X a → a, X b → b }
Asep Juarna, Catatan Teori Bahasa dan Automata, hal 29
5.3. Automata Pushdown (APD)
• Definisi : PDA adalah pasangan 7 tuple M = (Q, Σ, Γ, q 0 , Z 0 , δ, A), dimana :
Q : himpunan hingga stata, Σ : alfabet input, Γ : alfabet stack, q 0 ∈ Q : stata awal,
Z 0 ∈ Γ : simbol awal stack, A ⊆ Q : himpunan stata penerima,
Q × Γ*
fungsi transisi δ : Q × (Σ ∪ {ε}) × Γ → 2
(himpunan bagian dari Q × Γ*)
• Untuk stata q ∈ Q, simbol input a ∈ Σ, dan simbol stack X∈ Γ, δ(q, a, X) = (p, α)
berarti : PDA bertransisi ke stata p dan mengganti X pada stack dengan string α.
• Konfigurasi PDA pada suatu saat dinyatakan sebagai triple (q, x, α), dimana :
q ∈ Q : stata pada saat tersebut, x ∈ Σ* : bagian string input yang belum dibaca,
dan α ∈ Γ* : string yang menyatakan isi stack dengan karakter terkiri menyatakan
top of stack.
• Misalkan (p, ay, Xβ) adalah sebuah konfigurasi, dimana : a ∈ Σ, y ∈ Σ*, X ∈ Γ,
dan β ∈ Γ*. Misalkan pula δ(p, a, X) = (q, γ) untuk q ∈ Q dan γ ∈ Γ*. Dapat kita
tuliskan bahwa : (p, ay, Xβ) ⇒ (q, y, γβ).
Contoh 14 (PDA Deterministik):
PDA M = (Q, Σ, Γ, q 0 , Z 0 , δ, A) pengenal palindrome L = {xcx T x ∈ (ab)*},
dimana x T adalah cermin(x), mempunyai tuple : Q = {q 0 , q 1 , q 2 }, A = { q 2 },
Σ = {a, b, c}, Γ = {a, b, Z 0 }, dan fungsi transisi δ terdefinisi melalui tabel berikut :
No. Stata Input TopStack
1 q0 a Z0
2 q0 b Z0
3 q0 a a
4 q0 b 5 q0 6 q0
Hasil
No. Stata Input TopStack
Hasil
(q 0 , aZ 0 ) 7 q0 c Z0 (q 1 , Z 0 )
(q 0 , bZ 0 ) 8 q0 c a (q 1 , a)
(q 0 , aa) 9 q0 c b (q 1 , b)
a (q 0 , ba) 10 q1 a a (q 1 , ε)
a b (q 0 , ab) 11 q1 b b (q 1 , ε)
b b (q 0 , bb) 12 q1 ε Z0 (q 2 , ε)
Sebagai contoh, perhatikan bahwa fungsi transisi No. 1 dapat dinyatakan sebagai :
δ(q 0 , a, Z 0 ) = (q 0 , aZ 0 ). Pada tabel transisi tersebut terlihat bahwa pada stata q 0
PDA akan melakukan PUSH jika mendapat input a atau b dan melakukan transisi
stata ke stata q 1 jika mendapat input c. Pada stata q 1 PDA akan melakukan POP.
Berikut ini pengenalan dua string oleh PDA di atas :
1. abcba : (q 0 , abcba, Z 0 ) ⇒ (q 0 , bcba, aZ 0 )
(1)
⇒ (q 0 , cba, baZ 0 ) (4)
⇒ (q 1 , ba, baZ 0 ) (9)
⇒ (q 1 , a, aZ 0 ) (11)
⇒ (q 1 , ε, Z 0 ) (10)
⇒ (q 2 , ε, Z 0 ) (12)
2. acb : (q 0 , acb, Z 0 ) ⇒ (q 0 , cb, aZ 0 )
(1)
⇒ (q 1 , b, aZ 0 )
3. ab : (q 0 , ab, Z 0 ) ⇒ (q 0 , b, aZ 0 )
⇒ (q 0 , ε, baZ 0 )
(diterima)
(8),
(crash → ditolak)
(1)
(4)
(crash → ditolak)
Asep Juarna, Catatan Teori Bahasa dan Automata, hal 30
Penerimaan dan penolakan tiga string di atas dapat dijelaskan sebagai berikut :
1. string abcba diterima karena tracing sampai di stata penerima (q 2 ) dan string
“abcba” selesai dibaca (string yang belum dibaca = ε)
2. string acb ditolak karena konfigurasi akhir (q 1 , b, a Z 0 ) sedangkan fungsi transisi
δ(q 1 , b, a) tidak terdefinsi
3. string ab ditolak karena konfigurasi akhir (q 0 , ε, baZ 0 ) sedangkan fungsi transisi
δ(q 0 , ε, b) tidak terdefinsi
Ilustrasi graf fungsi transisi PDA di atas ditunjukkan melalui gambar berikut :
b, Z 0 /bZ 0
a, Z 0 /aZ 0
a, a/ε
a, a/aa
c, a/a
c, b/b
c, Z 0 / Z 0
q0
a, b/ab

q2
b, b/bb
b, a/ba

ε, Z 0 / Z 0
q1
b, b/ε
Notasi (p, ay, Xβ) ⇒ (q, y, γβ) dapat diperluas menjadi : (p, x, α) ⇒* (q, y, β),
yang berarti konfigurasi (q, y, β) dicapai melalui sejumlah (0 atau lebih) transisi.
Ada dua cara penerimaan sebuah kalimat oleh PDA, yang masing-masing terlihat
dari konfigurasi akhir, sebagaimana penjelasan berikut :
Jika M = (Q, Σ, Γ, q 0 , Z 0 , δ, A) adalah PDA dan x ∈Σ*, maka x diterima dengan
stata akhir (accepted by final state) oleh PDA M jika : (q 0 , x, Z 0 ) ⇒* (q, ε, α)
untuk α ∈ Γ * dan q ∈ A. x diterima dengan stack hampa (accepted by empty
stack) oleh PDA M jika : (q 0 , x, Z 0 ) ⇒* (q, ε, ε) untuk q ∈ Q.
Contoh 15 (PDA Non-Deterministik):
PDA M = (Q, Σ, Γ, q 0 , Z 0 , δ, A) pengenal palindrome L = {xx T x ∈ (ab)*}
mempunyai komponen tuple berikut : Q = {q 0 , q 1 , q 2 }, A = { q 2 }, Σ = {a, b},
Γ = {a, b, Z 0 }, dan fungsi transisi δ terdefinisi melalui tabel berikut :
No. St.
In. TS Hasil
No. St. In. TS Hasil
1 q0 a Z0 (q 0 , aZ 0 ),(q 1 , Z 0 ) 7 q0 ε Z0 (q 1 , Z 0 )
2 q0 b Z0 (q 0 , bZ 0 ),(q 1 , Z 0 ) 8 q0 ε a (q 1 , a)
3 q0 a a (q 0 , aa),(q 1 , a) 9 q0 ε b (q 1 , b)
4 q0 b a (q 0 , ba),(q 1 , a) 10 q 1 a a (q 1 , ε)
5 q0 a b (q 0 , ab),(q 1 , b) 11 q1 b b (q 1 , ε)
6 q0 b b (q 0 , bb),(q 1 , b) 12 q1 ε Z0 (q 2 , ε)
Asep Juarna, Catatan Teori Bahasa dan Automata, hal 31
Pada tabel transisi tersebut terlihat bahwa pada stata q 0 PDA akan melakukan PUSH
jika mendapat input a atau b dan melakukan transisi stata ke stata q 1 jika mendapat
input ε. Pada stata q 1 PDA akan melakukan POP. Contoh 14 dan 15 menunjukkan
bahwa PDA dapat dinyatakan sebagai mesin PUSH-POP.
Berikut ini pengenalan string “baab” oleh PDA di atas :
⇒ (q 0 , aab, bZ 0 )
(2 kiri)
1. (q 0 , baab, Z 0 )
⇒ (q 0 , ab, abZ 0 ) (5 kiri)
⇒ (q 1 , ab, abZ 0 ) (3 kanan)
⇒ (q 1 , b, bZ 0 ) (11)
⇒ (q 1 , ε, Z 0 ) (10)
⇒ (q 2 , ε, Z 0 ) (12)
2. (q 0 , baab, Z 0 ) ⇒ (q 1 , baab, Z 0 ) (2 kanan) (crash → ditolak)
3. (q 0 , baab, Z 0 ) ⇒ (q 0 , aab, bZ 0 ) (2 kiri)
⇒ (q 0 , ab, abZ 0 ) (5 kiri)
⇒ (q 0 , b, aabZ 0 ) (3 kiri)
⇒ (q 1 , b, aabZ 0 ) (4 kanan) (crash → ditolak)
⇒ (q 0 , aab, bZ 0 ) (2 kiri)
⇒ (q 0 , ab, abZ 0 ) (5 kiri)
⇒ (q 0 , b, aabZ 0 ) (3 kiri)
⇒ (q 0 , ε, baabZ 0 ) (4 kiri)
⇒ (q 1 , ε, baabZ 0 ) (9) (crash → ditolak)
4. (q 0 , baab, Z 0 )
(diterima)
Asep Juarna, Catatan Teori Bahasa dan Automata, hal 32
VI. PENGANTAR KOMPILASI
6.1. Translator
Translator (penerjemah) adalah sebuah program yang menerjemahkan sebuah program
sumber (source program) menjadi program sasaran (target program).
input : program sumber
translator
output : program sasaran
Jenis-jenis translator berdasarkan bahasa pemrograman yang bersesuaian dengan input
dan outputnya adalah :
Jenis Translator
Assembler
Compiler (Kompilator)
Bahasa Pemrograman
Input
Output
Bahasa Rakitan
Bahasa tingkat tinggi
Bahasa mesin
Bahasa tingkat rendah
6.2. Kompilator dan komponennya
Black box sebuah kompilator dapat digambarkan melalui diagram berikut :
program sumber
kompilator
program sasaran
pesan-pesan kesalahan
(error messages)
sedangkan diagram rincinya adalah sebagai berikut :
Program
Sumber
Program
Sasaran
ANALISA
Penganalisa
Leksikal
(Scanner)
Penganalisa
Sintaks
(Parser)
SINTESA
Penganalisa
Semantik
Pembentuk
Kode
Tabel
Proses kompilasi dikelompokkan ke dalam dua kelompok besar :
Pengoptimal
Kode
1. analisa : program sumber dipecah-pecah dan dibentuk menjadi bentuk antara (inter-
mediate representation)
2. sintesa : membangun program sasaran yang diinginkan dari bentuk antara
Program sumber merupakan rangkaian karakter. Berikut ini hal-hal yang dilakukan oleh
setiap fase pada proses kompilasi terhadap program sumber tersebut :
1. Penganalisa leksikal :
membaca program sumber, karakter demi karakter. Sederetan (satu atau lebih)
karakter dikelompokkan menjadi satu kesatuan mengacu kepada pola kesatuan
kelompok karakter (token) yang ditentukan dalam bahasa sumber. Kelompok karakter
yang membentuk sebuah token dinamakan lexeme untuk token tersebut. Setiap token
yang dihasilkan disimpan di dalam tabel simbol. Sederetan karakter yang tidak
mengikuti pola token akan dilaporkan sebagai token tak dikenal (unidentified token).
Contoh : Misalnya pola token untuk identifier I adalah : I = huruf(hurufangka)*.
Lexeme ab2c dikenali sebagai token sementara lexeme 2abc atau abC tidak
dikenal.
2. Penganalisa sintaks :
memeriksa kesesuaian pola deretan token dengan aturan sintaks yang ditentukan
dalam bahasa sumber. Deretan token yang tidak sesuai aturan sintaks akan dilaporkan
sebagai kesalahan sintaks (sintax error). Secara logika deretan token yang berse-
suaian dengan sintaks tertentu akan dinyatakan sebagai pohon parsing (parse tree).
Contoh : Misalnya sintaks untuk ekspresi if-then E adalah : E → if L then, L → IOA,
I = huruf(hurufangka)*, O → <=><=>=, A → 01...9. Ekspresi
if a2 < 9 then adalah ekspresi sesuai sintaks; sementara ekspresi if a2 < 9 do
atau if then a2B < 9 tidak sesuai. Perhatikan bahwa contoh ekspresi terakhir
juga mengandung token yang tidak dikenal.
3. Penganalisa semantik :
memeriksa token dan ekspresi dengan acuan batasan-batasan yang ditetapkan.
Batasan-batasan tersebut misalnya :
a. panjang maksimum token identifier adalah 8 karakter,
b. panjang maksimum ekspresi tunggal adalah 80 karakter,
c. nilai bilangan bulat adalah -32768 s/d 32767,
d. operasi aritmatika harus melibatkan operan-operan yang bertipe sama.
4. Pembangkit kode (atau pembangkit kode antara):
membangkitkan kode antara (intermediate code) berdasarkan pohon parsing. Pohon
parse selanjutnya diterjemahkan oleh suatu penerjemah, misalnya oleh penerjemah
berdasarkan sintak (syntax-directed translator). Hasil penerjemahan ini biasanya
merupakan perintah tiga alamat (three-address code) yang merupakan representasi
program untuk suatu mesin abstrak. Perintah tiga alamat bisa berbentuk quadruples
(op, arg1, arg2, result), tripels (op, arg1, arg2). Ekspresi dengan satu argumen
dinyatakan dengan menetapkan arg2 dengan - (strip, dash).
5. Pengoptimal kode :
melakukan optimasi (penghematan space dan waktu komputasi), jika mungkin, terhadap
kode antara.

Lulusan Informatika bisa apa?

Tulisan ini dibuat setelah mendapat inspirasi dari salah seorang dosen yang sangat menginspirasi bernama Pak Budi Rahardjo biasa dipanggil Pak Beer.
Indonesia memang sudah kalah jauh dari negara-negara luar sana dalam bidang IT. Statement pertama ini akan sangat jauh apabila dibahas lebih lanjut. Mulai dari bidang ekonomi, politik, budaya, sampai sosial, bidang IT di Indonesia tidak begitu dapat berkembang dengan pesat, sampai beberapa puluh tahun lagi mungkin baru bisa, tapi itu entah kapan, seperti menunggu uang jatuh dari atas langit.
Bagaimana mungkin mengembangkan IT di Indonesia. Itu merupakan masalah pertama yang disampaikan oleh seorang engineer di bidang IT yang akan segera lulus mengarungi kehidupan nyata setelah tamat kuliah. Baru saja keluar dari kehidupan idealis, sudah dihadapkan dengan masalah sebesar batu raksasa yang jatuh dari tebing. IT di Indonesia sangat-sangat tidak menjanjikan untuk diselami. Bagaimana tidak, setiap insan yang penuh akan kreativitas tidak akan cukup kuat menghadapi pejabat-pejabat penguasa yang tidak mengerti akan perkembangan IT. Sedikit saja ada perubahan IT, bahkan bisa masuk penjara bila tidak hati-hati.
Satu kalimat penuh makna, bisa apa lulusan informatika? lulus dari kuliah saja sudah menderita dengan problematika kehidupan di negara. Ya wajar saja, para pengubah masa depan ini pergi jauh-jauh untuk mencari kehidupan. Otak-otak segar kreatif justru dipakai untuk melahirkan karya-karya luar biasa, tapi di negeri nan jauh disana, bukan di negeri sendiri.
Cukup sampai disitu saja pemikiran jelek ini. Jangan sampai negeri ini semakin rusak dengan pemikiran yang justru memperolok-olok negeri sendiri. Apabila balik bertanya, kalau seperti ini terus, siapa yang mau mengubahnya. Apakah jawabannya, bukan saya, tapi biarkan orang lain yang mengubahnya. Nampaknya jawaban itu bukanlah ciri orang yang benar-benar segar dan kreatif seperti yang dikatakan tadi. Hanya pemikir yang penakut saja.
Setiap lulusan informatika yang mencoba berkecimpung di negeri sendiri sangatlah dikhawatirkan keadaannya. Setiap gerak langkahnya ditakuti oleh hukum, undang-undang, dan peraturan-peraturan lainnya yang gelap oleh ilmu keinformatikaan. Bidang sana belum sama sekali tersentuh dengan ilmu Informatika. Ya jelas saja, bila dihadapkan dengan hukum, bidang ini justru sangatlah lemah adanya. Diserang sedikit saja sudah tidak bisa membela apa-apa. Justru ketika ingin melakukan kebaikan malah bisa jadi masuk penjara karena memang tidak ada dasar-dasar hukum atau bahkan ilmu-ilmu kenegaraan yang tersentuh oleh bidang Informatika ini. Petinggi-petinggi sana terlalu sibuk mengurusi negara, terlalu sibuk mengurusi perpolitikan yang tidak henti-hentinya, dikala negara lain justru gencar-gencarnya mengembangkan dunia IT yang sedang jadi senjata utama di era globalisasi.
Lulusan Informatika bisa apa? Jawabannya, lulusan Informatika bisa ke hukum, bisa ke ekonomi, bisa ke politik, bisa ke sosial budaya. Untuk apa? untuk mengubah negara. titik. Lulusan Informatika ini memang tidak mengerti apa-apa tentang dunia luar, tapi dunia luar ini sangatlah membutuhkan mereka, yang akan menyelamatkan teman-teman Informatika di negeri ini sekaligus memajukan negara di bidang IT.

MATERI KULIAH TEORI BAHASA DAN OTOMATA

MATERI KULIAH
TEORI BAHASA DAN OTOMATA
Oleh :
Heru Cahya Rustamaji, S.Si, M.T
JURUSAN TEKNIK INFORMATIKA
FAKULTAS TEKNOLOGI INDUSTRI
UNIVERSITAS PEMBANGUNAN NASIONAL “ VETERAN “
YOGYAKARTA
2004
1
PERTEMUAN I
Teori Bahasa dan Otomata
Buku
Teori Bahasa dan Otomata, Firrar Utdirartatmo
An Introduction to Formal Language and Automata, Peter Linz
Otomata
Arti menurut American Heritage Dictionary:
1. a robot
2. one that behaves in an automatic or mechanical fashion
Arti dalam dunia matematika
Berkaitan dengan teori mesin abstrak, yaitu mesin sekuensial yang menerima input, dan
mengeluarkan output, dalam bentuk diskrit.
Contoh :

Mesin Jaja / vending machine

Kunci kombinasi

Parser/compiler
Teori Otomata dan bahasa formal, berkaitan dalam hal :

Pembangkitan kalimat/generation : menghasilkan semua kalimat dalam bahasa L
berdasarkan aturan yang dimilikinya

Pengenalan kalimat / recognition : menentukan suatu string (kalimat) termasuk
sebagai salah satu anggota himpunan L.
Bahasa Formal
Suatu kalimat dibentuk dengan menerapkan serangkaian aturan produksi pada sebuah
simbol ‘akar’. Proses penerapan aturan produksi dapat digambarkan sebagai suatu
diagram pohon.
Teori dasar
Def. 1 sebuah string dengan panjang n yang dibentuk dari himpunan A adalah barisan
dari n simbol
ai ∈ A
a1a2...an
Panjang string x dituliskan dengan |x|
Def 2. String kosong (null string), dilambangkan dengan ε adalah untaian dengan panjang
0 dan tidak berisi apapun. Panjang string x dituliskan dengan |x|
Def 3. dua buah string a = a1a2...am dan b=b1b2...bn dapat disambungkan menjadi string c
dengan panjang m+n sebagai berikut c = a1a2...amb1b2...bn
Operasi penyambungan tersebut dapat pula diterapkan pada himpunan
Z=XY = {st | s ∈X ∧ t∈Y}
Def 4. (Closure) . An adalah himpunan string dengan panjang n yang dibentuk dari
simbol-simbol di himpunan simbol/alfabet A:
Transitif Closure/Kleen Closure adalah himpunan seluruh string yang dapat dibentuk dari
A dengan berbagai panjang
A* = A0 ∪ A1 ∪ A2 ∪ A3 ∪ ...
2
Jika string kosong dikeluarkan , akan diperoleh positive closure
A+ = A1 ∪ A2 ∪ A3 ∪ ...
Tata Bahasa
Aturan yang disebutkan pada proses pengenalan dan pembangkitan kalimat.
Secara formal, tata bahasa terdiri dari 4 komponen yaitu :
1. Himpunan berhingga, tidak kosong dari simbol-simbol non terminal T1
2. Himpunan berhingga, dari simbol-simbol non-terminal N
3. Simbol awal S ∈ N, yang merupakan salah satu anggota dari himpunan simbol non-
terminal.
4. Himpunan berhingga aturan produksi P yang setiap elemennya dituliskan dalam
bentuk :
α→β
dimana α dan β adalah string yang dibentuk dari himpunan T ∪ N dan α harus berisi
paling sedikit satu simbol non-terminal.
Keempat komponen tersebut sering dituliskan sbb :
G = (T,N,S,P)
Bahasa yang dihasilkan oleh G ditulis sebagai L(G), yaitu himpunan string yang dapat
diturunkan dari simbol awal S dengan menerapkan aturan-aturan produksi yang terdapat
pada P.
Aturan Produksi
Aturan produksi α→β yang diterapkan pada suatu string w=aαc mengganti kemunculan.
α menjadi β, sehingga string tersebut berubah menjadi w=aβc, sehingga dapat dituliskan
aαc ⇒ aβc (aαc memproduksi aβc).
Produksi tersebut dapat diterapkan berkali-kali
w1 ⇒ w2 ⇒ w3 ⇒ ... ⇒ wn
atau dapat dituliskan
w1 ⇒* wn
jika minimal harus ada 1 aturan produksi yang diterapkan :
w1 ⇒+ wn
Contoh 1
Tatabahasa G = {{S} , {a,b}, S , P } dengan aturan produksi P adalah
S → aSb
S→ε
maka dapat dihasilkan suatu string
S ⇒ aSb ⇒ aaSbb ⇒aabb
sehingga dapat dituliskan
S ⇒* aabb
Bahasa yang dihasilkan dari tatabahasa tersebut adalah
L(G) = { ε , ab, aabb , aaabbb , aaaabbbb, ... }
atau dapat pula dituliskan
L(G) = {anbn | n ≥ 0 }
Contoh 2
3
Tatabahasa G = {{S,A} , {a,b}, S , P } dengan aturan produksi P adalah
S → Ab
A → aAb
A→ε
maka dapat dihasilkan suatu string
S ⇒ Ab ⇒b
S ⇒ Ab ⇒ aAbb ⇒ abb
S ⇒ Ab ⇒ aAbb ⇒ aaAbbb ⇒ aaAbbb
Bahasa yang dihasilkan dari tatabahasa tersebut adalah
L(G) = { b , abb, aabbb , aaabbbb , aaaabbbbb, ... }
atau dapat pula dituliskan
L(G) = {anbn+1 | n ≥ 0 }
Hirarki Bahasa
Kelas
Regular language
Context free language
Context sensitive language
Unrestricted language
Mesin pengenal
Finite State Automata
Push Down Automata
Linear Bounded Automata
Turing Machine
Kelas Ruas kiri Ruas Kanan
Regular α∈N ≤ 1 non terminal
                (paling kiri/kanan)
Context free α∈N -
Context sensitive α ∈ (T∪N)+ |α| ≤ |β|
Unrestricted α ∈ (T∪N)+ -
Contoh
P → abR
Q → abc
R → Scac
P → aQb
Q → abPRS
aD → Da
AD → aCD
CB → DB
ADc → ε
NB : Ruas kiri harus memuat simbol non-terminal
Pelajari sendiri
Teori Himpunan
Relasi dan fungsi
Teori Pembuktian
Graph dan Tree
PR /Latihan di buku Firrar, bab I
4
PERTEMUAN II
Finite State Automata (FSA)




model matematika yang dapat menerima input dan mengeluarkan output
Memiliki state yang berhingga banyaknya dan dapat berpindah dari satu state ke
state lainnya berdasar input dan fungsi transisi
Tidak memiliki tempat penyimpanan/memory, hanya bisa mengingat state terkini.
Mekanisme kerja dapat diaplikasikan pada : elevator, text editor, analisa leksikal,
pencek parity.
0
1
0
1
1
0
1
FA
Contoh pencek parity ganjil
0
Genap
0
1
Ganjil
1
Misal input : 1101
Genap 1 Ganjil 1 Genap 0 Genap 1 Ganjil
diterima mesin
Misal input : 1100
Genap 1 Ganjil 1 Genap 0 Genap 0 Genap
ditolak mesin
Def 1. Finite State Automata dinyatakan oleh 5 tuple
M=(Q , Σ , δ , S , F )
Q = himpunan state
Σ = himpunan simbol input
5
δ = fungsi transisi δ : Q × Σ
S = state awal / initial state , S ∈ Q
F = state akhir, F ⊆ Q
Contoh diatas,
Q = {Genap, Ganjil}
Σ = {0,1}
S = Genap
F = {Ganjil }
δ
Genap
Ganjil
0
Genap
Ganjil
1
Ganjil
Genap
atau
δ(Genap,0) = Genap
δ(Genap,1) = Ganjil
δ(Ganjil,0) = Ganjil
δ(Ganjil,1) = Genap
Jenis FSA
Deterministic Finite Automata (DFA) : dari suatu state ada tepat satu state berikutnya
untuk setiap simbol masukan yang diterima
Non-deterministic Finite Automata (NFA) : dari suatu state ada 0, 1 atau lebih state
berikutnya untuk setiap simbol masukan yang diterima
Deterministic Finite Automata

Contoh : pengujian parity ganjil.

Contoh lain : Pengujian untuk menerima bit string dengan banyaknya 0 genap,
serta banyaknya 1 genap.

0011 : diterima.

10010 : ditolak, karena banyaknya 0 ganjil

Diagram transisi-nya :
1
start q0
0 0
q2
1
q1
0
1
0
q3
1
6
DFA nya
Q = {q0 , q1 , q2 , q3 }
Σ = {0,1}
S = q0
F = { q0 }
fungsi transisi
0
1
δ
q0
q2
q1
q1
q3
q0
q2
q0
q3
q3
q1
q2
δ( q0,011)= δ( q2,11) =δ( q3,1)= q2
Ditolak
δ( q0,1010)= δ( q1,010) =δ( q3,10)=δ( q2,0)= q0 Diterima

Contoh lain DFA : Variabel dalam bahasa pascal diawali oleh huruf (besar/kecil),
dan diikuti dengan huruf atau angka.

A..Z,a..z,0..9
start
q0
A..Z,a..z
q0
0..9
A..Z,a..z,0..9
q0

Contoh DFA lainnya :
0
q0
1
1
q1
0
0,1
q2
7
PERTEMUAN III
Nondeterministic Finite Automata


Perbedaan dengan NFA: fungsi transisi dapat memiliki 0 atau lebih fungsi transisi
G = ({q0 , q1 , q2 , q3, q4 }, {0,1}, δ , q0 , { q2 , q4}}
0
1
δ
q0
{ q0,q3}
{q0,q1}
q1
{q2}
ε
q2
{q2}
{q2}
q3
{q4}
ε
q4
{q4}
{q4}
0,1
q3
0,1
0
q4
0
q0
0,1
1
q1



q0
1
q2
String diterima NFA bila terdapat suatu urutan transisi berdasar input, dari state
awal ke state akhir.
harus mencoba semua kemungkinan.
Contoh : string 01001
0
q0
0
1
q0
1
q3
0
q0
0
q1
0
q0
0
q3
1
q0
1
q3
q1
0
q4
1
q4
Def 2. Dua buah FSA disebut ekuivalen apabila kedua FSA tersebut menerima bahasa
yang sama
Contoh : FSA yang menerima bahasa {an | n≥0 }
8
a
q4
a
a
q4
q4
Def 3. Dua buah state dari FSA disebut indistinguishable (tidak dapat dibedakan)
apabila :
δ(q,w)∈F sedangkan δ(p,w)∉F dan
δ(q,w) ∉F sedangkan δ(p,w) ∈F untuk semua w ∈ Σ*
Def 4. Dua buah state dari FSA disebut distinguishable (dapat dibedakan) bila terdapat
w ∈ Σ* sedemikian hingga:
δ(q,w)∈F sedangkan δ(p,w)∉F dan
δ(q,w) ∉F sedangkan δ(p,w) ∈F untuk semua w ∈ Σ*
Prosedur menentukan pasangan status indistinguishable
1. Hapus semua state yang tak dapat dicapai dari state awal.
2. Catat semua pasangan state (p,q) yang distinguishable, yaitu {(p,q) | p ∈ F ∧ q ∉ F}
3. Untuk setiap pasangan (p,q) sisanya,
untuk setiap a∈ Σ, tentukan δ(p,a) dan δ(q,a)
Contoh
q1
0
q0
0
q2
1
1
0
0
1
0,1
q4
1
q3
1. Hapus state yang tidak tercapai -> tidak ada
2. Pasangan distinguishable (q0,q4), (q1,q4), (q2,q4), (q3,q4).
3. Pasangan sisanya (q0,q1), (q0,q2), (q0,q3), (q1,q2) (q1,q3) (q2,q3)
pasangan
state 1
state 2
hasil
0
1
0
1
(q0,q1)
q1
q3
q2
q4
distinguishable
(q0,q2)
q1
q3
q1
q4
distinguishable
(q1,q2)
q2
q4
q1
q4
indistinguishable
(q0,q3)
q1
q3
q2
q4
distinguishable
(q1,q3)
q2
q4
q2
q4
indistinguishable
(q2,q3)
q1
q4
q2
q4
indistinguishable
9
 5
5!
C  =
= 10
Catatan : jumlah pasangan seluruhnya :
 2 2 ! 3!
Prosedur Reduksi DFA
1. Tentukan pasangan status indistinguishable.
2. Gabungkan setiap group indistinguishable state ke dalam satu state dengan relasi
pembentukan group secara berantai : Jika p dan q indistingishable dan jika q dan r
indistinguishable maka p dan r indistinguishable, dan p,q serta r indistinguishable
semua berada dalam satu group.
3. sesuaikan transisi dari dan ke state-state gabungan.
Contoh
1. pasangan status indistinguishable (q1,q2), (q1,q3) dan (q2,q3).
2. q1,q2,q3 ketiganya dapat digabung dalam satu state q123
3. Menyesuaikan transisi, sehingga DFA menjadi
0,1
0
q0
0,1
q123
1
q4
PR Buku Firrar Bab II nomor 3, 4, 8, 9, 12.
10
PERTEMUAN IV
Ekuivalensi NFA-DFA
Ada apa dengan NFA ? konsep yang sulit diimplemen-tasikan. Komputer
sepenuhnya deterministic.

Kenapa dipelajari ? Lebih dekat ke sistem nyata

Contoh : permainan catur, banyak alternatif pada suatu posisi tertentu ->
nondeterministic

Non deterministik dapat menyelesaikan problem tanpa backtrack, namun dapat
diekuivalensikan ke DFA.
Algoritma
1. Buat semua state yang merupakan subset dari state semula. jumlah state menjadi 2Q
2. Telusuri transisi state–state yang baru terbentuk, dari diagram transisi.
3. Tentukan state awal : {q0}
4. Tentukan state akhir adalah state yang elemennya mengandung state akhir.
5. Reduksi state yang tak tercapai oleh state awal.

Contoh Ubahlah NFA berikut menjadi DFA
M={{q0,q1}, {0,1}, δ, q0,{q1}} dengan tabel transisi
0
1
δ
q0
{q0,q1}
q1
q1
{}
{q0,q1}
1
0
q0
0,1
q1
1
1. State yang akan dibentuk : {}, {q0} {q1},{q0,q1}
2. Telusuri state
0
1
δ
{}
{}
{}
{q0}
{q0,q1}
{q1}
{q1}
{}
{q0,q1}
{q0,q1}
{q0,q1}
{q0,q1}
3. State awal : {q0}
4. State akhir yang mengandung q1, yaitu {q1},{q0,q1}
11
{q1}
0
1
0,1
1
{q0}
1
{}
{q0,q1}
Contoh : Ubahlah NFA berikut menjadi DFA
M={{q0,q1 ,q2}, {p,r}, δ, q0,{q1}} dengan tabel transisi
0
1
δ
q0
{q1,q2}
{}
q1
{}
{q0,q1}
q2
{q1}
{q1}
p,r
q0
p
q1
r
q2
p
1.
State yang akan dibentuk : {}, {q0} {q1},{q2}, {q0,q1}, {q0,q2}, {q1,q2}, {q0,q1,q2}
2.
Telusuri state:
p
r
δ
{}
{}
{}
{q0}
{q1,q2}
{}
{q1}
{}
{q2}
{q2}
{q1}
{q1}
{q0,q1}
{q1,q2}
{q2}
{q0,q2}
{q1,q2}
{q1}
{q1,q2}
{q1}
{q1,q2}
{q0,q1,q2 }
{q1,q2}
{q1,q2}
3. State awal : {q0}
4. State akhir yang mengandung q1, yaitu {q1},{q1,q2}
5. Reduksi {q0,q1}{q0,q2}{q0,q1,q2 } sehingga FSA menjadi
12
r
{q0}
p
{q1,q2}
r
p
{q1}
r
p
{}
p,r
{q2}
p,r
NFA dengan ε-move
q0 ε q1
b b ε
q3 b
ε
q4
q2
Def 1. ε-move adalah suatu transisi antara 2 status tanpa adanya input. Contoh gambar :
transisi antara status q1 ke q3
Def 2. ε-closure adalah himpunan state yang dapat dicapai dari suatu state tanpa adanya
input. Contoh gambar :
ε-closure(q0) = [q0,q1,q3]
ε-closure(q1) = [q1,q3]
ε-closure(q3) = [q3]
Ekuivalensi NFA dengan ε-move ke NFA tanpa ε-move
1. Buat tabel transisi NFA dengan ε-move
2. Tentukan ε-closure setiap state
3. Carilah fungsi transisi /tabel transisi yang baru, rumus :
δ’(state,input)=ε-closure(δ(ε-closure(state,input))
4. Tentukan state akhir ditambah dengan state yang ε-closure nya menuju state akhir,
rumusnya
13
F’ = F ∪ {q | (ε-closure(q) ∩ F ≠ ∅}
Contoh
q0
ε
q1
a
q2
b
q3
Tabel transisi-nya
0
1
δ
q0


q1
q2
q3
q2


q3


ε-closure dari FSA tersebut
ε-closure(q0) = [q0,q1]
ε-closure(q1) = [q1]
ε-closure(q2) = [q2]
ε-closure(q3) = [q3]
Cari tabel transisi yang baru (δ’) :
a
δ’
q0
ε-cl(δ(ε-cl(q0),a))
ε-cl(δ({q0,q1},a))
ε-cl(q2)
{q2}
q1
ε-cl(δ(ε-cl(q1),a))
ε-cl(δ({q1},a))
ε-cl(q2)
{q2}
q2
ε-cl(δ(ε-cl(q2),a))
ε-cl(δ({q3},a))
ε-cl(∅)

q3
ε-cl(δ(ε-cl(q3),a))
ε-cl(δ({q3},a))
ε-cl(∅)

b
ε-cl(δ(ε-cl(q0),b))
ε-cl(δ({q0,q1},b))
ε-cl(q3)
{q3}
ε-cl(δ(ε-cl(q1),b))
ε-cl(δ({q1},b))
ε-cl(q3)
{q3}
ε-cl(δ(ε-cl(q2),b))
ε-cl(δ({q2},b))
ε-cl(∅)

ε-cl(δ(ε-cl(q3),b))
ε-cl(δ({q3},b))
ε-cl(∅)

14
Hasilnya menjadi
a
a
q0
q2
q1
b
b
q3
Penggabungan FSA
Bila diketahui L1 adalah bahasa yang diterima oleh M1 dan L2 adalah bahasa yang
diterima oleh M2 maka
1. FSA M3 yang dapat menerima L1+L2 dibuat dengan cara

Tambahkan state awal untuk M3, hubungkan dengan state awal M1 dan state
awal M2 menggunakan transisi ε

Tambahkan state akhir untuk M3, hubungkan dengan state-state akhir M1
dan state-state akhir M2 menggunakan transisi ε
2. FSA M4 yang dapat menerima L1L2 dibuat dengan cara

State awal M1 menjadi state awal M4

State-state akhir M2 menjadi state-state akhir M4

Hubungkan state-state akhir M1 dengan state awal M2 menggunakan transisi
ε
Contoh FSA M1 dan M2
0
qA0
1
qA1
1
qB0
1
qB1
0
FSA M3
15
0
qA0
1
qA1
ε
qS
ε
1
ε
ε
qB0
1
qF
qB1
0
FSA M4
0
qA0
1
1
qA1
ε
qB0
1
qB1
0
PR, Buku firrar
bab 3 nomor 5 dan 6
bab 4 nomor 1 dan 4
16
PERTEMUAN V
Ekspressi reguler




Bahasa disebut reguler jika terdapat FSA yang dapat menerimanya.
Bahasa reguler dinyatakan secara sederhana dengan ekspresi reguler/regular
expression (RE).
Contoh penerapan : searching string pada file
RE -> NFA dengan ε Move -> DFA
Definisi ekspresi reguler
Jika Σ merupakan himpunan simbol, maka
1. ∅ , λ , dan a ∈Σ adalah ekspresi reguler dasar
2. jika r dan t masing masing merupakan ekspresi reguler maka komposisi berikut
merupakan ekspresi reguler :
Ekspresi
Makna
r+t
himpunan string gabungan R∪T
rt
operasi penyambungan string thd himpunan
r*
Kleene closure dari R
(r)
r
Contoh ekspresi reguler

(0+1)* : himpunan seluruh string yang dapat dibentuk dari simbol ‘0’ dan ‘1’

(0+1)*00(0+1)* : himpunan string biner yang mengandung paling sedikit satu
substring ‘00’

(0+1)*00 : himpunan string biner yang diakhiri dengan ‘00’
Bahasa Reguler
Apabila r adalah RE, maka L(r) adalah bahasa reguler yang dibentuk
menggunakan ekspressi reguler r.
Contoh
Tentukan bahasa reguler yang dibentuk oleh r=(aa)*
Jawab
L(r) =
L( (aa)* )
=
{ λ, aa, aaaa, aaaaaa, ... }
=
{ a2n | n ≥ 0 }
menyatakan himpunan string a dengan jumlah genap
Tentukan bahasa reguler yang dibentuk oleh r=(aa*)(bb)*b
Jawab
L(r) =
L( (aa)* (bb)*b )
=
{ a2n b2m+1 | n,m ≥ 0 }
17
Tentukan ekspresi reguler pembentuk bahasa pada Σ = {0,1}, yaitu
L(r) = { w ∈ Σ* | w memiliki substring ‘00’ }
Jawab
r = (0+1)*00(0+1)*
Tentukan ekspresi reguler pembentuk bahasa pada Σ = {a,b}, yaitu
L(r) = { abnw | n≥ 3 , w ∈ {a , b}+ }
Jawab
r = abbb(a+b)(a+b)*
Latihan :
1. Carilah seluruh string pada L((a+b)*b(a+ab)*) dengan panjang string kurang dari 4.
2. Tentukan ekspresi reguler pembentuk bahasa pada Σ = {a,b,c}, yaitu
a. L(r) = { w ∈ Σ* | w memiliki tepat sebuah simbol ‘a’ }
b. L(r) = { w ∈ Σ* | w mengandung tepat 3 buah simbol ‘a’}
c. L(r) = { w ∈ Σ* | w mengandung kemunculan masing masing simbol minimal satu
kali}
3. Tentukan ekspresi reguler pembentuk bahasa pada Σ = {0,1}, yaitu
a. L(r) = { w ∈ Σ* | w diakhiri dengan string 01 }
b. L(r) ={ w ∈ Σ* | w tidak diakhiri dengan string 01 }
c. L(r) ={ w ∈ Σ* | w mengandung simbol ‘0’ sebanyak
genap }
d. L(r) ={ w ∈ Σ* | kemunculan string ’00’ pada w
sebanyak kelipatan 3 }
4. Tentukan ekspresi reguler pembentuk bahasa pada Σ = {a,b}, yaitu L(r) = { w ∈
Σ* | |w| mod 3 = 0 }
Sifat Bahasa Reguler

Tertutup terhadap operasi himpunan sederhana
Jika L1 dan L2 adalah bahasa reguler, maka L1∪L2,
L1 ∩L2, L1L2, ~(L1) dan L1* adalah bahasa reguler juga

Tertutup terhadap homomorphic image.
Jika L1 adalah bahasa reguler, maka homomorphic image h(L1) adalah bahasa
reguler juga.
Dimisalkan Σ dan Γ adalah alfabet, maka fungsi homomorphic dinyatakan
dengan
h:Σ→ Γ
18
jika w = a1 a2 ... an
maka h(w) = h(a1) h(a2 ) ... h(an)
Jika L adalah bahasa pada Σ maka homomorphic
image bahasa L adalah
h(L)= { h(w) | w∈L}
Contoh
Dimisalkan Σ = {a,b} dan Γ = {a,b,c} dan didefinisikan h(a) = ab dan h(b) =bbc
homomorphic image bahasa L = {aa,aba } adalah
h(L)= { abab, abbbcab}
Dimisalkan Σ = {a,b} dan Γ = {b,c,d} dan didefinisikan h(a) = dbcc dan h(b)
=bdc
homomorphic image bahasa L(r) yang dibentuk dari ekspresi reguler
r = (a+b*)(aa)*
adalah h(L(r)) yang dibentuk dengan ekspresi reguler
r = (dbcc + (bdc)*) (dbccdbcc)*
Hubungan RE dan NFA

Setiap RE ada satu NFA dengan ε-move yang ekuivalen
Konversi ekspresi reguler ke FSA
Ekspresi
FSA
ε q0=qf
∅ q0
a q0
qf
a
qf
r+t
ε
q0
sR
R
fR
ε
ε
sT
T
fT
ε
qf
19
rt
q0 qf
ε ε
R
sR
r*
ε
fR
T
sT
fT
ε
q0
ε
sR
R
fR
ε
qf
ε
Contoh : Tentukan FSA untuk ekspresi reguler :
1. 01
2. 0+11
3. 01*+1
4. (0+1*)*
PR
Buku firrar bab V nomor 4 dan 8
20
PERTEMUAN VI
DFA dan Tatabahasa Reguler
Tatabahasa Linier kiri dan linier kanan
Suatu tatabahasa G (T,N,S,P) disebut linier kiri jika seluruh aturan produksinya
berbentuk
A → xB
A→x
dengan A, B ∈ N dan x ∈ T*
Suatu tatabahasa G (T,N,S,P) disebut linier kiri jika seluruh aturan produksinya
berbentuk
A → Bx
A→x
dengan A, B ∈ N dan x ∈ T*
Tatabahasa reguler bila bersifat linier kiri atau linier kanan.
Contoh 1
Tatabahasa G = {{S} , {a,b}, S , P } dengan aturan produksi P adalah
adalah tatabahasa linier kanan /reguler
S → abS |a
Tatabahasa G = {{S, S1,S2 } , {a,b}, S , P } dengan aturan produksi P adalah
S → S1ab
S1→ S1ab | S2
S2→ a
adalah tatabahasa linier kiri /reguler
Tatabahasa G = {{S, A, B} , {a,b}, S , P } dengan aturan produksi P adalah
S→A
A → aB | λ B → Ab
adalah bukan tatabahasa reguler
Konversi DFA ke tatabahasa linier
Setiap DFA dapat diubah menjadi tatabahasa yang memiliki aturan produksi yang linier.
Aturan pengubahan ini adalah sebagai berikut :

setiap transisi status δ(A,a)=B diubah menjadi aturan produksi A → aB

setiap status akhir P diubah menjadi aturan produksi P→ε
Contoh FSA berikut
q0
ε
q1
a
q2
b
q3
Tatabahasa linier untuk FSA tersebut yaitu G = ({a,b}, {S,S1,S2,S3},S, P ) dengan aturan
produksi P adalah :
21
S → S1
S1 → aS2
S2 → bS3
S3 → ε
Konversi tatabahasa linier ke DFA

setiap aturan produksi A → aB diubah menjadi transisi status δ(A,a)=B

setiap aturan produksi A → a diubah menjadi δ(A,a)=SF

untuk a ∈ T* dengan |a|>1 dapat dibuat state tambahan

setiap aturan produksi A → B diubah menjadi δ(A,ε)=B
Contoh
tatabahasa G = ({a,b},{V0,V1}, V0, P ) dengan P :
V0 →aV1
V1 →abV0 | b
Mesin FSA nya menjadi
V0
a
b
V1
b
Vf
a
PR / Latihan buku firrar bab 6 nomor 2,3,4,5
Pertanyaan mendasar tentang bahasa reguler
1. Apakah terdapat suatu algoritma untuk menentukan diterima atau tidaknya suatu suatu
string pada bahasa L ?
Jawab : YA, dengan menggunakan FSA.
2. Apakah terdapat suatu algoritma untuk menentukan suatu bahasa reguler kosong, finite
atau infinite ?
Jawab : YA

dengan DFA, jika terdapat lintasan dari simpul start ke simpul Final, maka
bahasa tersebut tidak kosong.

Cari simpul simpul yang membentuk siklus. Jika terdapat lintasan dari simpul
start ke simpul Final yang melalui simpul yang membentuk siklus, maka bahasa
tersebut infinite. Jika tidak, maka bahasa tersebut finite.
Penerapan ekspresi reguler

Digunakan untuk memerinci unit-unit leksikal sebuah bahasa pemrograman
(token).
22

contoh ekspresi reguler ‘bilangan real positif’
(0+1+...+9)(0+1+...+9)*.(0+1+...+9) (0+1+...+9)*
contoh ekspresi reguler ‘bilangan bulat’
(‘+’ + ’-‘ + λ) (0+1+...+9)(0+1+...+9)*
Editor text
Pumping lemma
Apabila suatu bahasa merupakan bahasa reguler maka akan dapat diterima oleh mesin
DFA M=(Q,Σ,δ,q0,F), dengan sejumlah state n.
Apabila string w dengan |w| ≥ n diinputkan dalam DFA, maka pasti ada simpul k dalam
DFA yang dikunjungi lebih dari satu kali.
Apabila string diantara simpul k yang sama tersebut ‘dipompa’, maka sisanya pasti masih
diterima oleh DFA tersebut.
Contoh
Bahasa yang menerima ekspresi reguler 0(10)*11
q0
0
q1
0
1
q3
1
q4
1
q2




Ambil string w∈L , dengan |w|≥ n: w= 01011
q0 0 q1 1 q2 0 q1 1 q3 1 q4
simpul q1 dikunjungi 2 kali.
string diantara simbol q1 tersebut ‘dipompa’ keluar
q0 0 q1 1 q3 1 q4
string 011 tersebut masih dapat diterima oleh FSA.
Secara formal
Misal L adalah sebuah bahasa reguler infinite, maka terdapat sebuah konstanta n
dengan sifat bahwa jika w adalah sebuah string dalam L yang panjangnya lebih besar atau
sama dengan n maka kita bisa menulis w=uvx sedemikian sehingga uvix ∈ L untuk
semua i ≥ 0. dengan |v|≥1 dan |uv|≤n .
Notasi matematisnya

z ∈ L ∧ z ≥ n ⇒
( ∀L)( ∃n)( ∀z ) 

(∃u, v , w) z = uvw ∧ uv ≤ n ∧ v ≥ 1 ∧ ( ∀i )(uv i w ∈ L) 



(
)
23
Penjelasan



Mengidentifikasi sifat yang harus dimiliki oleh suatu bahasa reguler.
Cara untuk menentukan apakah sebuah bahasa tidak reguler
Untuk memperlihatkan bahwa suatu bahasa infinite tidak reguler, maka kita
tunjukkan bahwa untuk nilai n yang cukup besar, sekurang-kurangnya satu
untai yang panjangnya n atau lebih besar gagal untuk dapat ‘dipompa’.
Contoh :
L=
{ai^2 | i≥1}
{a1, a4,a9, a16, ...}
{a , aaaa , aaaaaaaaa , aaaaaaaaaaaaaaaa, ... }
Suatu string dalam L harus mempunyai panjang yang berupa nilai kuadrat (1,4,9,16, ...,
n2, ...)
Misal bahwa L adalah bahasa reguler.
Perhatikan bahwa terdapat sebuah nilai n sedemikian sehingga an^2 ∈L,
Menurut pumping lemma dapat kita tuliskan an^2 =uvx, sedemikian hingga

1 ≤|v|≤ n

(∀i) (uviw ∈L)
karena |v|≥1 maka jelas bahwa
|uvw|<|uv2w|<|uv2w|< ...
ambil i=2 maka kita dapatkan
n2 = |uvw| < |uv2w| ≤ n2 + n < (n+1)2
Jelas
n2 < |uv2w| < (n+1)2
Panjang |uv2w| bukan merupakan kuadrat sempurna, karena berada diantara 2 nilai
kuadrat sempurna yang berurutan.
berarti uv2w ∉ L
Jadi disimpulkan bahwa
L=
{ai^2 | i≥1} bukan merupakan bahasa reguler.
24
PERTEMUAN VII
FSA dengan Output
FSA : accepter, dapat menerima atau tidak.
FSA dengan output : transducer
1. Mesin Moore :output berasosiasi dengan state
2. Mesin Mealy :output berasosiasi dengan transisi
Mesin Moore
M = (Q,Σ,δ,S,∆,λ)
Q : himpunan state
Σ : himpunan simbol input
δ : fungsi transisi
S : state awal S ∈Q
∆ : himpunan output
λ : fungsi output untuk setiap state
Contoh mesin moore untuk memperoleh modulus 3 pada suatu bilangan biner:
M = (Q,Σ,δ,S,∆,λ)
Q : q0,q1,q2
Σ : [0,1]
S : q0
∆ : [0,1,2]
λ(q0) =0
λ(q1) =1
λ(q2) =2
Prinsip:
jika i diikuti dengan 0, maka hasilnya 2i
1012 =5
10102 = 2*5 =10
jika i diikuti dengan 1, maka hasilnya 2i+1
10112 = 2*5+1 =11
1012=5
jika i/3 mempunyai sisa p, maka untuk input berikutnya bernilai 0 maka
2i/3 mempunyai sisa 2p mod 3
untuk p=0 maka 2p mod 3 = 0
untuk p=1 maka 2p mod 3 = 2
untuk p=2 maka 2p mod 3 = 1
jika i/3 mempunyai sisa p, maka untuk input berikutnya bernilai 1 maka
(2i+1)/3 mempunyai sisa (2p+1) mod 3
untuk p=0 maka (2p+1) mod 3 = 1
untuk p=1 maka (2p+1) mod 3 = 0
untuk p=2 maka (2p+1) mod 3 = 2
Sehingga didapat mesin FSA sbb :
25
0
q0/0
1
1
q1/1
1
0
q2/2
0
Contoh :
input 5 (1012) , state terakhir q2/2 , 5 mod 3 = 2
input 10 (10102) , state terakhir q1/1 , 10 mod 3 = 1
Mesin Mealy
M = (Q,Σ,δ,S,∆,λ)
Q : himpunan state
Σ : himpunan simbol input
δ : fungsi transisi
S : state awal S ∈Q
∆ : himpunan output
λ : fungsi output untuk setiap transisi
Contoh mesin Mealy untuk mendeteksi ekspresi reguler
(0+1)*(00+11)
Jawab
M = (Q,Σ,δ,S,∆,λ)
Q : q0,q1,q2
Σ : [0,1]
S : q0
∆ : [0,1,2]
λ(q0,0) =T
λ(q0,1) =T
λ(q1,0) =Y
λ(q1,1) =T
λ(q2,0) =T
λ(q2,1) =Y
26
0/Y
q1
0/T
q0
1/T
0/T
1/T
q2
1/Y
Ekuivalensi mesin Moore dengan mesin Mealy

Mesin Moore ke mesin Mealy
Jml state = jml state sebelum * jml output
1
1
q0T
0
q1T
0
0
0
q0Y
q2T
1
1
q1Y
0

0
q2Y
1
Mesin Mealy ke mesin Moore
Menambah label output pada transisi
Menghapus label output pada state
27
0/0
q0
1/2
1/1
1/0
q1
0/2
q2
0/1
Contoh kasus

Tentukan FSA dari rangkaian sirkuit berikut ini. Asumsi bahwa terdapat waktu
yang cukup untuk perambatan sinyal menuju kondisi yang stabil.
y1
F
input x
y2

Kelereng dijatuhkan dari A atau B. Percabangan x1,x2 dan x3 menentukan
saluran mana yang akan dilewati kelereng (kiri / kanan). Ketika percabangan
dilewati, kelereng berikutnya akan melewati dengan saluran berbeda. Buatlah
FSA nya
28
A B
X1 X2
X3
C
D
Latihan :
buku Firrar bab 7
PR.
Buatlah mesin Mealy dan Moore untuk proses membaca input (0+1)* :

Jika input berakhir dengan 101, outputnya A

Jika input berakhir dengan 110, outputnya A

Jika yang lainnya , 8outputnya C
29
PERTEMUAN VIII
Tata Bahasa Bebas Konteks
Motivasi awal :
deskripsi bahasa alami
<kalimat>
→ <subjek> <predikat>
<subjek>
→ <kata benda>
<predikat>
→ <kata kerja>
<kata benda>
→ kucing
<kata kerja>
→ berlari
<kata kerja>
→ menyapu
Contoh kalimat yang dapat dihasilkan
kucing berlari
kucing menyapu
(sintaks yes, semantik no)
Dalam tatabahasa bebas konteks

Ruas kiri dari aturan produksi terdiri dari SATU simbol non terminal

Ruas kanan dapat berupa string yang dibentuk dari simbol terminal dan non
terminal
Contoh
S →aSb | ε
Kalimat-kalimat yang dibangkitkan dari aturan produksi itu adalah ε,ab,aabb,aaabbb,... ,
anbn
Contoh
A →0A0
A →1A1
A→a
Kalimat-kalimat yang dibangkitkan dari aturan produksi itu adalah a,01a10, 1001a1001 ,
110a011 βaβR
Contoh
S → aSb | SS |ε
Bahasa yang dihasilkan oleh tatabahasa dengan aturan produksi di atas adalah :
L = {w ∈ (a + b)* |na(w) =nb(w) }
Leftmost dan Rightmost Derivation
Suatu penguraian /penurunan dikatakan leftmost derivation bila setiap tahapan penurunan
variabel / non terminal terkiri yang diuraikan. Apabila setiap tahapan penurunan variabel
/ non terminal paling kanan yang diuraikan disebut rightmost derivation
Contoh 1
G=({A,B,S}, {a,b},S,P} dengan aturan produksi P :
S → AB
A→ aaA | λ
30
B→Bb | λ
Menspesifikasikan bahasa
L(G) = {a2nbm | n≥0 , m≥0}
Leftmost derivation untuk menghasilkan string aab
S ⇒ AB ⇒ aaAB ⇒ aaB ⇒ aaBb ⇒ aab
Righmost derivation untuk menghasilkan string aab
S ⇒ AB ⇒ ABb ⇒ aaABb ⇒aaAb ⇒aab
Contoh 2
G=({A,B,S}, {a,b},S,P} dengan aturan produksi P :
S → aAB
A→ bBb
B→ A | λ
Leftmost derivation untuk menghasilkan string abbbb
S ⇒ aAB ⇒ abBbB ⇒ abAbB ⇒ abbBbbB
⇒ abbbbB ⇒ abbbb
Righmost derivation untuk menghasilkan string aab
S ⇒ aAB ⇒ aA ⇒ abBb ⇒ abAb ⇒ abbBbb ⇒ abbbb
Pohon urai
Untuk menampilkan penguraian, dapat dilakukan dengan membentuk pohon urai
(sayangnya, urutan penguraian tidak terlihat) .
Contoh pohon urai pada contoh sebelumnya :
S
a
A
b
B
λ
B
b
A
b
B
b
λ
Parsing dan Keanggotaan
Untuk menentukan apakah string w berada di L(G), dengan cara secara sistematis
membangun semua kemungkinan penurunan, dan mencocokkan hasilnya apakah ada
yang sama dengan string w. (disebut exhaustive search parsing)
contoh menentukan apakah string ab berada pada bahasa yang dibentuk oleh grammar
dengan aturan produksi
31
S → SS | aSb | bSa | λ
Untuk penguraian pertama
1. S ⇒ SS
2. S ⇒ aSb
3. S ⇒ bSa
4. S ⇒ λ
Penguraian nomor 3 dan 4 tidak perlu dilanjutkan. Penguraian 1 membentuk
Penguraian 2 membentuk
1a. S ⇒ SS ⇒ SSS
2a. S ⇒ aSb ⇒ aSSb
1b. S ⇒ SS ⇒ aSbS
2b. S ⇒ aSb ⇒ aaSbb
1c. S ⇒ SS ⇒ bSaS
2c. S ⇒ aSb ⇒ abSab
1d. S ⇒ SS ⇒ S
2d. S ⇒ aSb ⇒ ab
Ambiguitas pada Tatabahasa dan Bahasa
Tatabahasa bebas konteks G disebut ambigu jika terdapat beberapa w ∈ L(G) yang
mempunyai paling sedikit dua buah pohon penurunan
Contoh pada tatabahasa dengan aturan produksi
S → SS | aSb | λ
string aabb mempunyai 2 pohon penurunan :
S
S
S
a S b
a S b
λ
λ
S
a S b
a S b
λ
Pumping Lemma untuk bahasa bebas konteks

Jika suatu rangkaian simbol /string yang cukup panjang yang merupakan sebuah
bahasa bebas konteks, maka kita dapat menemukan dua substring yang jaraknya
berdekatan yang jika dipompa, string baru yang diperoleh merupakan bahasa
bebas konteks juga.

Secara formal, lemma diatas dinyatakan dengan
32
z ∈ L ∧ z ≥ n ⇒



 z = uvwxy ∧ vwx ≤ n ∧ vx ≥ 1 ⇒ 
( ∀L)( ∃n)( ∀z ) 

(∃u, v , w, x , y ) ( ) i i
 ∀i (uv wx y ∈ L)






syarat “ kedua lokasi berdekatan” dinyatakan dengan kondisi |vwx| ≤ n
Jika salah satu v atau x diambil sebagai string kosong, maka lemma diatas
berubah menjadi lemma untuk bahasa reguler
Contoh tatabahasa dengan aturan produksi
S →uAy
A → vAx
A→w
maka aturan derivasinya
S ⇒ uAy ⇒ uwy
S ⇒ uAy ⇒ uvAxy ⇒uvwxy
S ⇒ uAy ⇒ uvAxy ⇒ uvvAxxy ⇒uvvwxxy
sehingga untuk setiap i ≥0 , uviwxiy ∈ L
Sifat sifat tertutup bahasa bebas konteks

Gabungan dua CFL merupakan CFL juga
Jika diketahui dua buah CFG G1= (N1,T1,S1,P1) dan G2=(N2,T2,S2,P2) yang
menghasilkan bahasa L1 dan L2 , maka CFG L1 ∪ L2 dapat dibentuk dengan cara
:
1. menggabungkan kedua himpunan dan menambahkan satu simbol variabel
baru S
2. menggabungkan kedua himpunan simbol terminal
3. menggabungkan kedua himpunan aturan produksi dan menambahkan satu
aturan produksi baru
S → S1|S2 yang digunakan untuk memilih salah satu simbol awal S1 atau S2
dari simbol awal baru S
G3 = (N1∪N2∪{S},T1∪T2 ,S,P1∪P2 ∪{S→S1|S2}}

Penyambungan dua CFL merupakan CFL juga
Jika diketahui dua buah CFG G1= (N1,T1,S1,P1) dan G2=(N2,T2,S2,P2) yang
menghasilkan bahasa L1 dan L2 , maka bahasa L1L2 dapat dibentuk oleh :
G4 = (N1∪N2∪{S},T1∪T2 ,S,P1∪P2 ∪{S→S1S2}}

Klosure Kleene dari CFL adalah CFL juga.
Klosure Kleene dari tatabahasa G=(N,T,S1,P) adalah
G5 = (N ∪ {S} , T , S , P ∪ {S → S1S | ε } )
Latihan
G(L1) = ( {S , A , B}, {a,b} , S , P ) dengan P :
S → AB | ε
A → aB
33
B → Sb
G(L2) = ( {S , A , B}, {a,b} , S , P ) dengan P :
S → aaB
A → bBb | ε
B → aA
Bagaimanakah :
a. CFG G(L1 ∪ L2)
b. CFG G(L1L2)
c. CFG G(L1*)

Bahasa bebas konteks tertutup terhadap substitusi
Contoh
La = {0 n1n | n ≥1 } dan Lb = { wwR | w ∈ (0+2)* }
dihasilkan oleh tatabahasa Ga dengan aturan produksi
Sa → 0Sa1 | 01
serta tatabahasa G2 dengan aturan produksi
Sb → 0Sb0 | 2Sb2 | ε
Didefinisikan tatabahasa G dengan aturan produksi
S → aSbS | bSaS | ε
jika f adalah substitusi f(a)= La dan f(b) = Lb maka
f(L) adalah bahasa yang dihasilkan oleh tatabahasa dengan aturan produksi
S → SaSSbS | SbSSaS | ε
Sa → 0Sa1 | 01
Sb → 0Sb0 | 2Sb2 | ε
Tatabahasa Bebas Konteks dan Bahasa Pemrograman

Tatabahasa bebas konteks digunakan untuk mendefinisikan sintaks bahasa
pemrograman

Menggunakan notasi BNF (Backus-Naur Form)

variabel / non terminal : <...>

terminal : tanpa tanda

← diganti dengan ::=

Contoh statemen if then else
< if_statement> ::= if <expression>
<then_clause>
<else_clause>
34
PERTEMUAN IX
PENYEDERHANAAN
TATA BAHASA BEBAS KONTEKS
Tujuan
Melakukan pembatasan sehingga tidak menghasilkan pohon penurunan yang memiliki
kerumitan yang tidak perlu atau aturan produksi yang tidak berarti.
Contoh 1:
S AB | a
A a

Aturan produksi S AB tidak berarti karena B tidak memiliki penurunan
Contoh 2 :
S
A
B
C
D


A
B
C
D
a|A
Memiliki kelemahan terlalu panjang jalannya padahal berujung pada S
produksi D A juga menyebabkan kerumitan.
a,
Cara Penyederhanaan:
1. Penghilangan produksi useless ( tidak berguna )
2. Penghilangan produksi unit
3. Penghilangan produksi ε
Penghilangan Produksi Useless
Di sini produksi useless didefinisikan sebagai :


Produksi yang memuat symbol variabel yang tidak memiliki penurunan yang akan
menghasilkan terminal-terminal seluruhnya.
Produksi yang tidak akan pernah dicapai dengan penurunan apapun dari simbol
awal, sehingga produksi itu redundan ( berlebih )
Contoh :
S aSa | Abd | Bde
A Ada
B BBB | a
Maka
1) Simbol variabel A tidak memiliki penurunan yang menuju terminal, sehingga bisa
dihilangkan
2) Konsekuensi no (1), aturan produksi S Abd tidak memiliki penurunan
35
Penyederhanaan menjadi:
S aSa | Bde
B BBB | a
Contoh :
S Aa | B
A ab | D
B b|E
C bb
E aEa
Maka :
1) Aturan produksi A D, simbol variabel D tidak memiliki penurunan.
2) Aturan produksi C
bb, Penurunan dari simbol S, dengan jalan manapun tidak
akan pernah mencapai C
3) Simbol variabel E tidak memiliki aturan produksi yang menuju terminal
4) Konsekuensi no (3) Aturan produksi B
E, simbol variabel E tidak memiliki
penurunan.
maka produksi yang useless:
A D
C bb
E aEa
B E
Penyederhanaannya menjadi:
S Aa | B
A ab
B b
Contoh :
S
A
B
C
D
aAb | cEB
dBE | eeC
ff
ae
h
Analisa :
1) Aturan produksi S cEB, A dBE dapat dihilangkan ( E tidak memiliki
penurunan)
2) Aturan produksi D h, redundan
Sisa aturan produksi
S aAb
A eeC
B ff
C ae
Analisis lagi
36
B ff juga redundan,
Hasil penyederhanaan menjadi:
S aAb
A eeC
C ae
Contoh lain lagi :
S aB
A bcD | dAC
B e | Ab
C bCb | adF | ab
F cFB
Analisis
1) Aturan produksi A bcD, variabel D tidak memiliki penurunan
2) Konsekuensi no (1), simbol variabel A tidak memiliki penurunan yang menuju
terminal (tinggal A dAC)
3) Konsekuensi no (2), B Ab tidak memiliki penurunan
4) Simbol variabel F tidak memiliki penurunan yang menuju terminal
5) Konsekuensi no (4), C adF tidak memiliki penurunan
Setelah disederhanakan menjadi:
S aB
B e
C bCb | ab
Contoh lain lagi :
S aBD
B cD | Ab
D ef
A Ed
F dc
Analisa
1) Aturan produksi A Ed, E tidak memiliki penurunan
2) Aturan produksi F dc, redundan
Sisa aturan produksi:
S aBD
B cD | Ab
D ef
Analisa lagi
B Ab, A tidak memiliki penurunan.
Hasil penyederhanaan:
S aBD
B cD
D ef
Contoh lagi:
S Abc | ab
37
A AAA | ε
Aturan produksi setelah disederhanakan:
S
A
Abc | ab
AAA | ε
Ingat A ε juga harus diperhitungkan
PRINSIP
Setiap kali melakukan penyederhanaan diperiksa lagi aturan produksi yang tersisa,
apakah semua produksi yang useless sudah hilang.
Penghilangan Produksi Unit

Produksi dimana ruas kiri dan kanan aturan produksi hanya berupa satu simbol
variabel, misalkan: A B, C D.

Keberadaannya membuat tata bahasa memiliki kerumitan yang tak perlu.

Penyederhanaan dilakukan dengan melakukan penggantian aturan produksi unit.
Contoh:
S Sb
S C
C D
C ef
D dd
Dilakukan penggantian berturutan mulai dari aturan produksi yang paling dekat menuju
ke penurunan terminal-terminal (‘=>’ dibaca ‘menjadi’):

C D => C dd

S C => S dd | ef
Sehingga aturan produksi setelah penyederhanaan:
S Sb
S dd | ef
C dd
C ef
C dd
Contoh lain:
S A
S Aa
A B
B C
B b
C D
C ab
D b
Penggantian yang dilakukan :

C D => C b

B C => B b | ab, karena B b sudah ada, maka cukup dituliskan B ab

A B => A ab | b

S A => ab | b
38
Sehingga aturan produksi setelah penyederhanaan:
S ab | b
S Aa
A ab | b
B ab
B b
C b
C ab
D b
Contoh lagi:
S Cba | D
A bbC
B Sc | ddd
C eAn | f | C
D E | SABC
E gh
Penggantian yang dilakukan:

D E menjadi D gh

C C , kita hapus

S D menjadi S gh | SABC
Sehingga aturan produksi setelah penyederhanaan:
S Cba | gh | SABC
A bbC
B Sc | ddd
C eA | f
D gh | SABC
E gh
Penghilangan Produksi ε
Produksi ε adalah produksi dalam bentuk
α ε
atau bisa dianggap sebagai produksi kosong ( empty ). Penghilangan produksi ε
dilakukan dengan melakukan penggantian produksi yang memuat variabel yang bisa
menuju produksi ε, atau biasa disebut nullable.
Prinsip penggantiannya bisa dilihat kasus berikut:
S bcAd
A ε
A nullable serta A
ε satu-satunya produksi dari A, maka variabel A bisa
ditiadakan, hasil penyederhanaan tata bahasa bebas konteks menjadi:
S
bcd
Tetapi bila kasusnya:
39
S bcAd
A bd | ε
ε bukan satu-satunya produksi dari A, maka hasil
A nullable, tapi A
penyederhanaan:
S bcAd | bcd
A bd
Contoh lagi, terdapat tata bahasa bebas konteks:
S Ab | Cd
A d
C ε
ε merupakan
Variabel yang nullable adalah variabel C. Karena penurunan C
penurunan satu-satunya dari C, maka kita ganti S
Cd menjadi S
d. Kemudian
produksi C ε kita hapus.
Setelah penyederhanaan menjadi:
S Ab | d
A d
Contoh lain lagi:
S dA | Bd
A bc
A ε
B c
ε bukan penurunan satu-satunya
Variabel yang nullable adalah variabel A. A
dari A ( terdapat A
bc ), maka kita ganti S
dA menjadi S
dA | d.A
ε kita
hapus.
Setelah penyederhanaan :
S dA | d | Bd
A bc
B c
Contoh tata bahasa bebas konteks:
S AaCD
A CD | AB
B b|ε
C d|ε
D ε
Variabel yang nullable adalah variabel B, C, D. Kemudian dari A
CD, maka
variabel A juga nullable ( A
ε ). Karena D hanya memilki penurunan D
ε, maka
kita sederhanakan dulu:



S
A
D
AaCD => S AaC
CD => A C
ε kita hapus
Selanjutnya kita lihat variabel B dan C memiliki penurunan ε, meskipun bukan
satu-satunya penurunan, maka dilakukan penggantian:

A AB => A AB | A | B

S AaC => S AaC | aC | Aa | a
40

B ε dan C ε kita hapus
Setelah penyederhanaan:
S AaC | aC | Aa | a
A C | AB | A | B
B b
C ε
Variabel yang nullable adalah A, B, C. Dari S
lakukan penggantian:






A
B
B
A
S
C
AB, maka S juga nullable. Kita
aCa => A aa
bA => B bA | b
BB => B BB | B
abB => A abB | ab
AB => S AB | A | B | ε
ε, B ε, A ε dihapus
*Perhatikan untuk penggantian S
AB kita tetap mempertahankan S
ε, karena S
merupakan simbol awal. Ini merupakan satu-satunya perkecualian produksi ε yang tidak
dihapus, yaitu produksi ε yang dihasilkan oleh simbol awal.
Hasil akhir dari penyederhanaan:
S AB | A | B | ε
A abB | ab | aa
B bA | b | BB | B
Contoh tata bahasa bebas konteks:
S aAb
A aAb | ε
Hasil penyederhanaan:
S aAb | ab
A aAb | ab
Contoh tata bahasa bebas konteks:
S ABaC
A BC
B b|ε
C D|ε
D d
Hasil penyederhanaan:
S ABaC | BaC | AaC | ABa | aC | Aa | Ba | a
A B | C | BC
B b
C D
D d
41
Prakteknya ketiga penyederhanaan tersebut dilakukan bersama pada suatu tata
bahasa bebas konteks, yang nantinya menyiapkan tata bahasa bebas konteks tersebut
untuk diubah kedalam suatu bentuk normal Chomsky.
Urutan penghapusan aturan produksi :
1) Hilangkan produksi ε
2) Hilangkan produksi unit
3) Hilangkan produksi useless
Contoh :
S
A
B
C
AA | C | bd
Bb | ε
AB | d
de
Hilangkan produksi ε, sehingga menjadi:
S A | AA | C | bd
A Bb
B B | AB | d
C de
Selanjutnya penghilangan produksi unit menjadi:
S Bb | AA | de | bd
A Bb
B AB | d
C de
Penghilangan produksi unit bisa menghasilkan produksi useless.
Terakhir dilakukan penghilangan produksi useless:
S Bb | AA | de | bd
A Bb
B AB | d
Hasil akhir aturan produksi tidak lagi memiliki produksi ε, produksi unit, maupun
produksi useless.
42
PERTEMUAN X
BENTUK NORMAL CHOMSKY
Pengertian Bentuk Normal Chomsky
Bentuk normal Chomsky / Chomsky Normal Form (CNF) merupakan salah satu
bentuk normal yang sangat berguna untuk tata bahasa bebas konteks ( CFG ). Bentuk
normal Chomsky dapat dibuat dari sebuah tata bahasa bebas konteks yang telah
mengalami penyederhanaan yaitu penghilangan produksi useless, unit, dan ε. Dengan
kata lain, suatu tata bahasa bebas konteks dapat dibuat menjadi bentuk normal Chomsky
dengan syarat tata bahasa bebas kontesk tersebut:



Tidak memiliki produksi useless
Tidak memiliki produksi unit
Tidak memiliki produksi ε
Aturan produksi dalam bentuk normal Chomsky ruas kanannya tepat berupa
sebuah terminal atau dua variabel. Misalkan:
A BC
A b
B a
C BA | d
Pembentukan Bentuk Normal Chomsky
Langkah-langkah pembentukan bentuk normal Chomsky secara umum sebagai
berikut:

Biarkan aturan produksi yang sudah dalam bentuk normal Chomsky

Lakukan penggantian aturan produksi yang ruas kanannya memuat simbol
terminal dan panjang ruas kanan > 1

Lakukan penggantian aturan produksi yang ruas kanannya memuat > 2 simbol
variabel

Penggantian-penggantian tersebut bisa dilakukan berkali-kali sampai akhirnya
semua aturan produksi dalam bentuk normal Chomsky

Selama dilakukan penggantian, kemungkinan kita akan memperoleh aturan-aturan
produksi baru, dan juga memunculkan simbol-simbol variabel baru
Bisa dilihat tahapan-tahapan tersebut pada gambar 10.1
43
Biarkan yg
sudah CNF
CFG yang
sudah
disederhanakan
Penggantian simbol
terminal pada a.p,
dg ruas kanan > 1
Buat variabel
dan a.p, baru
bila perlu
CNF
Penggantian a.p,
dengan simbol
variabel > 2
Tahapan-tahapan pembentukan bentuk normal Chomsky
Contoh, tata bahasa bebas konteks ( kita anggap tata bahasa bebas konteks pada
bab ini sudah mengalami penyederhanaan ):
S
A
B
bA | aB
bAA | aS | a
aBB | bS | b
Aturan produksi yang sudah dalam bentuk normal Chomsky:
A
B
a
b
Dilakukan penggantian aturan produksi yang belum bentuk normal Chomsky
(‘=>’ bisa dibaca berubah menjadi):
S bA => S P1A
S aB => S P1B
A bAA => S P1AA => A P1P3
A aS => A P2S
B aBB => B P2BB => B P2P4
B bS => B P1S
Terbentuk aturan produksi dan simbol variabel baru:
P1 b
P2 a
P3 AA
P4 BB
Hasil akhir aturan produksi dalam brntuk normal Chomsky :
44
A
B
S
S
A
A
B
B
P1
P2
P3
P4
a
b
P1A
P2B
P1P3
P2S
P2P4
P1S
b
a
AA
BB
Contoh, tata bahasa bebas konteks:
S aB | CA
A a | bc
B BC | Ab
C aB | b
Aturan produksi yang sudah dalam bentuk normal Chomsky :
S CA
A a
B BC
C b
Penggantian aturan produksi yang belum dalam bentuk normal Chomsky:
S
A
B
C
aB => S
bc => S
Ab => B
aB => C
P1B
P2P3
A P2
P1B
Terbentuk aturan produksi dan simbol variabel baru:
P1
P2
P3
a
b
c
Hasil akhir aturan produksi dalam bentuk normal Chomsky :
S CA
A a
B BC
45
C
S
S
B
C
P1
P2
P3
b
P1B
P2P3
A P2
P1B
a
b
c
Contoh, tata bahasa bebas konteks :
S
aAB | ch | CD
A dbE | eEC
B ff | DD
C ADB | aS
D i
E jD
Aturan produksi yang sudah dalam bentuk normal Chomsky :
S CD
B DD
D
i
Penggantian aturan produksi:
S
S
A
A
B
C
C
E
aAB => S P1P2
ch => S P3P4
dbE => A P5P6
eEC => A P8P9
ff => B P10P10
ADB => C AP11
aS => C P1S
jD => E P12D
Terbentuk aturan produksi baru:
P1
P2
P3
P4
P5
P6
P7
P8
P9
a
AB
c
h
d
P7E
b
e
EC
46
P10
P11
P12
f
DB
j
Hasil akhir dalam bentuk normal Chomsky:
S CD
B DD
D i
S P1P2
S P3P4
A P5P6
A P8P9
B P10P10
C AP11
C P1S
E P12D
P1 a
P2 AB
P3 c
P4 h
P5 d
P6 P7E
P7 b
P8 e
P9 EC
P10 f
P11 DB
P12 j
Algoritma CYK untuk Tata Bahasa Bebas Konteks
Algoritma CYK merupakan algoritma parsing dan keanggotaan ( membership)
untuk tata bahasa bebas konteks. Algortima ini diciptakan oleh J. Cocke, DH. Younger,
dan T. Kasami. Syarat untuk penggunaan algortima ini adalah tata bahasa harus berada
dalam bentuk normal Chomsky . Obyektif dari algortima ini adalah untuk menunjukkan
apakah suatu string dapat diperoleh dari suatu tata bahasa.
Algoritma CYK sebagai berikut:
begin
1) for i:= 1 to n do
2) Vi1 := {A| A
a aturan produksi dimana simbol ke- i
adalah a };
3) for j:= 2 to n do
47
4)
for i:= 1 to (n-j+1)
begin
5)
Vij:=Ø;
6)
for k:=1 to (j
7)
Vij:= Vij υ
produksi, dimana B di Vik
end
end
do
– 1) do
( A | A
BC adalah suatu
dan C di Vi+k,j-k }
Penjelasan:








n = panjang untai yang akan diperiksa, missal : untuk untai ‘ada’, n = | ada | =3
i akan menyatakan kolom ke-
j akan menyatakan baris ke-
tahapan no (1) dan (2) untuk mengisi table baris pertama kolom 1 – n
no (3), interasi dari baris ke- 2 sampai n
no (4), interasi untuk mengisi kolom 1 sampai ( n – baris + 1) pada suatu baris.
no (5) inisialisasi Vij dengan Ø
no (6) dan no (7), interasi untuk memeriksa mana saja yang menjadi anggota Vij
Kita lihat contoh kasus, dimana terdapat tata bahasa bebas konteks ( simbol awal
S ):
S
A
B
C
AB | BC
BA | a
CC | b
AB | a
Periksalah apakah untai ‘baaba’ termasuk kedalam bahasa tersebut
Pertama – tama kita akan membuat tabel untuk Vij ( Vkolom,baris ) sebagai berikut :
b
a
a b a
3 4 5
i
1
2
1
2
3
4
5
Tabel diatas kita gunakan unruk mempermudah kita dalam menyelesaikan
persoalan, i akan menyatakan kolom, j akan menyatakan baris.
Kita ketahui n = 5. Dari Algoritma langkah (1) dan (2) kita bisa mengisi baris
pertama pada tabel, sebagai berikut:
48





Untuk V11, kita periksa variabel yang bisa menurunkan ‘b’, dari B
V11= {B}
Untuk V21, kita periksa variabel yang bisa menurunkan ‘a’, dari A
kita isi V21{A,C}
Untuk V31, kita periksa varibel yang bisa menurunkan ‘a’, dari A
kita isi V31={A,C}
Untuk V41, kita periksa variabel yang bisa menurunkan ‘b’, dari B
V41={B}
Untuk V51, kita periksa variabel yang bisa menurunkan’a’, dari A
kita isi V51={A,C}
b kita isi
a dan C
a dan C
a
a
b kita isi
a dan C
A
Dari hasil tersebut kita bisa tabel :
b
a
a b a
3 4 5
A,C B A,C
i
1
2
3
4
5




1
B
2
A,C
Selanjutnya kita akan mengisi baris ke-2 sampai n sebagai berikut
Pada baris ke -2 ( k =1 )
Untuk V12, periksa Vik- Vi+k, j-k, berarti V11-V21, yaitu B-A,C, variabel yang
bisa menurunkan BA atau BC adalah S dan A, maka V12 kita isi {S, A}
Untuk V22, periksa Vik – Vi+k, j-k, berarti V21-V31, yaitu A,C-A,C, variabel yang
bisa menurunkan AA, AC, CA, atau CC adalah B maka V22 kita isi {B}
Untuk V32, periksa Vik-Vi+k, j-k, berarti V31-V41 yaitu A, C-B, variabel yang
bisa menurunkan AB atau CB adalah S dan C, maka V12 kita isi {S, C}
Untuk V42, periksa Vik-Vi+k, j-k berarti V41-V51, yaitu A,C-B, variabel yang bisa
menurunkan AB atau CB adalah S dan C, maka V12 kita isi {S,A}
Dari hasil tersebut kita bisa mengisi tabel:
b a
1 2
B A,C
S,A B
a b a
3 4 5
A,C B A,C
S,C S,A
i
1
2
3
4
5
49
Pada baris ke –3 (k = 1 sampai 2):
Untuk V13, periksa Vik-Vi+k, j-k, berarti V11-V22 & V12-V31, yaitu B-B & S,A-A,C,
variabel yang bisa menurunkan BB, SA,SC,AA, atau AC adalah tidak ada, maka
V13 kita isi ∅
Untuk V23, periksa Vik-Vi+k, j-k, berarti V21-V32 & V22-V41, yaitu A,C-S,C & B-B,
variabel yang bisa menurunkan AS, AC, CS, CC, atau BB adalah B , maka V23
kita isi {B}
Untuk V33, periksa Vik-Vi+k, j-k, berarti V31-V42 & V32-V51, yaitu A,C-S,A & S,C-
A,C variabel yang bisa menurunkan AS, AA, CS, CA, SA, SC, CA, atau CC
adalah B, maka V33 kita isi {B}
Dari hasil tersebut kita bsa mengisi tabel:
b
a
a b a
3 4 5
A,C B A,C
S,C S,A
B
i
1
2
3
4
5
1
B
S,A

2
A,C
B
B
Pada baris ke –4 ( k = 1 sampai 3):
Untuk V14, periksa Vik-Vi+k, j-k, berarti V11-V23 & V12-V32 & V13-V41, yaitu B-B &
S,A-S,C & ∅-B, variabel yang bisa menurunkan BB, SS, SC, AS AC adalah tidak
ada, maka V14 kita isi ∅
Untuk V24, periksa Vik-Vi+k, j-k, berarti V21-V33 & V22-V42 & V23-V51, yaitu A,C-B
& B-S,A & B-S,A & B-A,C, variabel yang bisa menurunkan AC, AB, BS, BA,
BC adalah S, C, A, maka V24 kita isi {S,A,C}
Dari hasil tersbut kita bisa mengisi tabel:
b
a
a b a
3 4 5
A,C B A,C
S,C S,A
B
i
1
2
3
4
5
1
B
S,A


2
A,C
B
B
S,A,C
Pada baris ke –5 ( k = 1 sampai 4 )
Untuk V15, periksa Vik-Vi+k, j-k, berarti V11-V24 & V12-V33 & V13-V42 & V14-V51
yaitu B-S,A,C & S,A-B & ∅-S,A & ∅-A,C, variabel yang bisa menurunkan BA,
BC, SA, SC, SB, atau AB adalah A,S,C maka V15 kita isi {S,A,C}
50
Dari hasil tersbut kita bisa mengisi tabel:
b A
1 2
B A,C
S,A B
∅ B
  ∅ S,A,C
    S,A,C
a b a
3 4 5
A,C B A,C
S,C S,A
B
i
1
2
3
4
5
Perhatikan , syarat suatu untai dapat diturunkan dari simbol awal, V1n memuat
simbol awal. Terlihat pada tabel, simbol awal S termuat di V15, maka untai ‘baaba’ dapat
diturunkan oleh tata bahasa tersebut.
Kita bisa mencoba-coba untuk membuat pohon penurunan dari untai ‘baaba’,
Kita lihat untuk contoh lain, terdapat tata bahasa bebas konteks:
S
A
B
AB | b
BA | a
AS | b
Periksalah apakah untai ‘aaab’ termasuk ke dalam bahasa tersebut
Pertama-tama kita akan membuat tabel untuk Vij ( Vkolom, baris) sebagai berikut:
a
a
a b
3 4
i
1
2
1
2
3
4
Kita ketahui n = 4. Dari algoritma langkah (1) dan(2) kita bisa mengisi baris
pertama pada tabel, sebagai berikut:
Untuk V11, kita periksa variabel yang bisa menurunkan ‘a’, dari A a kita isi V11
= {A}
Untuk V21, kita periksa variabel yang bisa menurunkan ‘a’, dari A a kita isi V21
= {A}
Untuk V31, kita periksa variabel yang bisa menurunkan ‘a’, dari A a kita isi V31
= {A}
Untuk V41, kita periksa variabel yang bisa menurunkan ‘b’, dari B b dan S b
kita isi V41 = {S,B}
51
Dari haisl tersebut kita bisa mengisi tabel:
a a
1 a 2
A A
b
3 4
A S,B
i
j
1
2
3
4
Selanjutnya kita akan mengisi baris ke –2 sampai n sebagai berikut:
Pada baris ke –2 (k = 1) :
Untuk V12, periksa Vik-Vi+k, j-k, berarti V11-V21, yaitu A-A, variabel yang bisa
menurunkan AA adalah tidak ada, maka V12 kita isi ∅
Untuk V22, periksa Vik-Vi+k, j-k, berarti V21-V31 ,yaitu A-A, variabel yang bisa
menurunkan AA adalah tidak ada, maka V22 kita isi ∅
Untuk V32, periksa Vik-Vi+k, j-k, berarti V31-V41 ,yaitu A,S-B, variabel yang bisa
menurunkan AS atau AB adalah S dan B, maka V32 kita isi {S,B}
Dari hasil tersebut kita bisa mengisi tabel:
a a
1 2
A A
∅ ∅
a b
3 4
A S,B
S,B
i
j
1
2
3
4
Pada baris ke –3 (k = 1 sampai 2)
Untuk V13, periksa Vik-Vi+k, j-k, berarti V11-V22 & V12-V31, yaitu A-∅ & ∅-A,
variabel yang bisa menurunkannya adalah tidak ada, maka V13 kita isi ∅
Untuk V23, periksa Vik-Vi+k, j-k, berarti V21-V32 & V22-V41, yaitu A-SB & ∅-SB,
variabel yang bisa menurunkan AS atau AB adalah S dan B, maka V23 kita isi
{S,B}
Dari hasil tersebut kita bisa mengisi tabel:
a
a
a b
3 4
A S,B
S,B
i
j
1
2
3
4
1
A


2
A

S,B
52
Pada baris ke –4 (k = 1 sampai 3):
Untuk V14, periksa Vik-Vi+k, j-k, berarti V11-V23 & V12-V32 & V13-V41, yaitu A-SB
& ∅-SB, variabel yang bisa menurunkan AS atau AB adalah S dan B, maka V14
kita isi {S,B}
Dari hasil tersebut kita bisa mengisi tabel:
a
a
a b
3 4
A S,B
S,B
i
j
1
A


S,B
1
2
3
4
2
A

S,B
Terlihat pada tabel, simbol awal S termuat di V14, maka untai ‘aaab’ dapat
diturunkan oleh tata bahasa tersebut.
S
A
B
B
B
A
C
A
B
a
C
B
a
b
Pohon penurunan untuk untai ‘baaba’
53
PERTEMUAN XI
PENGHILANGAN REKURSIF KIRI
Aturan Produksi Rekursif
Aturan Produksi yang rekursif memilki ruas kanan (hasil produksi) yang memuat
simbol variabel pada ruas kiri. Sebuah aturan produksi dalam bentuk:
A
βA
merupakan aturan produksi yang rekursif kanan
β=(V∪T)* atau kumpulan simbol variabel dan terminal
Contoh aturan produksi yang rekursif kanan:
S dS
B adB
A Aβ
Produksi dalam bentuk:
Merupakan aturan produksi yang rekursif kiri, contohnya:
S
B
Sd
Bad
Produksi yang rekursif kanan menyebabkan pohon penurunan tumbuh ke kanan,
sebaliknya Produksi yang rekursif kiri menyebabkan pohon penurunan tumbuh ke kiri.
Bisa dilihat pohon penurunanpada gambar 11.1 dari tata bahasa bebas konteks dengan
aturan produksi:
S aAc
A Ab | ε
54
S
a
A
A
b
A
A
c
b
b
Gambar 11.1 Pohon penurunan sebuah CFG yang rekursif kiri
Dalam banyak penerapan tata bahasa, rekursif kiri tak diinginkan. Untuk
menghindari penurunan yang bisa mengakibatkan loop kita perlu menghilangkan sifat
rekursif kiri dari aturan produksi. Penghilangan rekursif kiri disini memungkinkan suatu
tata bahasa bebas konteks nantinya diubah ke dalam bentuk normal Greibach.
Tahapan Penghilangan Rekursif Kiri
Langkah-langkah penghilangan rekursif kiri:
Pisahkan aturan produksi yang rekursif kiri dan yang tidak, misal:
Aturan produksi yang rekursif kiri:
A
Aα1 | Aα2 | Aα3 | ....... Aαn
Aturan produksi yang tidak rekursif kiri (termasuk produksi ε):
A
β1 | β2 | β3 | ........ βm
Dari situ kita bisa tentukan α1, α2, .... αn, dan β1, β2, .... βm dari setiap aturan
produksi yang memiliki simbol ruas kiri yang sama
Lakukan penggantian aturan produksi yang rekursif kiri, menjadi sebagai berikut:
1) A β1Z | β2Z | .... βmZ
2) Z
α1 | α2 | α3 | .... αn
3) Z α1Z | α2Z | α3Z | .... αnZ
55
Penggantian diatas dilakukan untuk setiap aturan produksi dengan simbol ruas kiri
yang sama. Bisa muncul simbol variabel baru Z1, Z2 dan seterusnya, sesuai
banyaknya variabel yang menghasilkan produksi yang rekursif kiri.
Hasil akhir berupa aturan produksi pengganti ditambah dengan aturan produksi
semula yang tidak rekursif kiri.
Tahapan-tahapan tersebut bisa dilihat pada Gambar berikut
Aturan
produksi
CFG
mengan
d
Lakukan
penggantian
lk
Aturan
d ki
CFG
bebas
d i
Gambar 11.2 Tahapan penghilangan rekursif kiri
Contoh, tata bahasa bebas konteks:
S
Sab | aSc |dd | ff | Sbd
Pertama-tama kita lakukan pemisahan aturan produksi
Aturan produksi yang rekursif kiri:
S
Sab | Sbd
Dari situ kita tentukan:
Untruk simbol ruas kiri S: α1=ab, α2=bd
Aturan produksi yang tidak rekursif kiri:
S
aSc | dd | ff
Dari situ kita dapatkan:
Untuk simbol ruas kiri S: β1=aSc, β2=dd, β3=ff
Kita lakukan penggantian aturan produksi yang rekursif kiri:
Untuk yang memiliki simbol ruas kiri S:
S Sab | Sbd, digantikan oleh:
i.
S aScZ1 | dd Z1 | ffZ1
ii.
Z1 ab | bd
iii.
Z1 abZ1 | bd Z1
56
Hasil akhir setelah penghilangan rekursif kiri adalah:
S aSc | dd | ff
S aScZ1 | dd Z1 | ffZ1
Z1 ab | bd
Z1 abZ1 | bd Z1
*Pada kasus diatas S adalah satu-satunya simbol variabel yang menghasilkan produksi
rekursif kiri.
Contoh lain, terdapat tata bahasa bebas konteks:
S Sab | Sb | cA
A Aa | a | bd
Pertama-tama kita lakukan pemisahan aturan produksi
Aturan produksi yang rekursif kiri:
S Sab | Sb
A Aa
Dari situ kita tentukan:
Untuk simbol ruas kiri S: α1= ab, α2 =b
Untuk simbol ruas kiri A: α1 = a
Aturan produksi yang tidak rekursif kiri:
S cA
A a | bd
Dari situ kita dapatkan
Untuk simbol ruas kiri S: β1 = cA
Untuk simbol ruas kiri A: β1 = a, β2 = bd
Kita lakukan penggantian aturan produksi yang rekursif kiri:
Untuk yang memiliki simbol ruas kiri S:
S Sab | Sb, digantikan oleh:
i.
ii.
iii.
S
Z1
Z1
cAZ1
ab | b
abZ1 | bZ1
Untuk yang memiliki simbol ruas kiri A :
A
i.
ii.
iii.
Aa, digantikan oleh:
A
Z2
Z2
a Z2 | bdZ2
a
a Z2
57
Hasil akhir setelah penghilangan rekursif kiri adalah:
S cA
A a | bd
S cAZ1
Z1 ab | b
Z1 abZ1 | bZ1
A a Z2 | bdZ2
Z2 a
Z2 a Z2
*Perhatikan bahwa penghilangan rekursif kiri memunculkan simbol variabel baru, dan
aturan produksi baru yang rekursif kanan.
Contoh lain, terdapat tata bahasa bebas konteks:
S Sa |aAc | c | ε
A Ab | ba
Pertama-tama kita lakukan pemisahan aturan produksi
Aturan produksi yang rekursif kiri:
S Sa
A Ab
Dari situ kita tentukan:
Untuk simbol ruas kiri S: α1 = a
Untuk simbol ruas kiri A: α1 = b
Aturan produksi yang tidak rekursif kiri:
S aAc | c | ε
A ba
Dari situ kita dapatkan
untuk simbol ruas kiri S:β1 = aAc, β2= c, β3 = ε
untuk simbol ruas kiri A: β1 = ba
*Perhatikan produksi ε termasuk produksi yang tidak rekursif kiri
Kita lakukan penggantian aturan produksi yang rekursif kiri:
Untuk yang memilki simbol ruas kiri S:
S Sa, digantikan oleh:
S aAcZ1 | cZ1 | Z1
i.
ii.
Z1 a
iii.
Z1 a Z1
Untuk yang memiliki simbol ruas kiri A:
A Ab, digantikan oleh:
i.
A ba Z2
ii.
Z2 b
58
iii.
Z2
bZ2
Hasil akhir setelah penghilangan rekursif kiri adalah:
S
S
aAc | c | ε
aAcZ1 | cZ1 | Z1
A ba
A ba Z2
Z1 a
Z1 a Z1
Z2 b
Z2 b Z2
59
PERTEMUAN 12
BENTUK NORMAL GREIBACH
Pengerian Bentuk Normal Greibach
Bentuk normal Greibach merupakan bentuk normal yang memiliki banyak
konsekuensi teoritis dan prkatis. Dalam bentuk normal Greibach kita membatasi posisi
munculnya terminal-terminal dan variabel-variabel. Suatu tata bahasa bebas konteks
(CFG) dikatakan dalam bentuk normal Greibach / Greibach Normal Form, selanjutnya
kita sebut sebagai GNF, jika setiap aturan produksinya ada dalam bentuk:
A

a:simbol terminal (tunggal), a ε T
α: rangkaian simbol-simbol variabel (V*)
Atau dengan kata lain, suatu tata bahasa bebas konteks dalam bentuk normal
Greibach bila hasil produksinya (ruas kanan) diawali dengan satu simbol terminal,
slanjutnya bisa diikuti oleh rangkaian simbol variabel. Contoh tata bahasa bebas konteks
dalam bentuk bentuk normal Greibach:
S a | aAB
A aB
B cS
Untuk dapat diubah ke dalam bentuk normaol Greibach, tata bahasa semula haru
memenuhi syarat:
Sudah dalam bentuk normal Chomsky
Tidak bersifat rekursif kiri
Tidak menghasilkan ε
Terdapat dua cara pembentukan bentuk normal Greibach , yaitu melalui substitusi
dan perkalian matriks. Pada bagian berikutnya kita membahasa kedua cara tersebut.
12.2. Pembentukan Bentuk Normal Greibach dengan Substitusi
Secara umum langkah-langkah untuk mendapatkan bentuk normal Greibach :
Tentukan urutan simbol-simbol variabel yang ada dalam tata bahasa. Misalkan
1.
terdapat m variabel dengan urutan A1, A2, ...., Am
2.
Berdasarkan urutan simbol yang ditetapkan pada langkah (1) seluruh aturan
produksi yang ruas kanannya diawali dengan simbol variabel dapat dituliskan
dalam bentuk
Ah Ai γ
dimana h <> i (rekrusif kiri sudah dihilangkan), γ bisa berupa simbol-simbol
variabel
a. Jika h < i, aturan produksu ini sudah benar ( tidakperlu diubah)
60
3.
4.
5.
6.
b. Jika h > i, aturan produksi belum benar. Lakukan substitusi berulang-ulang
terhadap Ai (ganti Ai pada produksi ini dengan ruas kanan produksi dari variabel
Ai ) sehingga suatu saat diperoleh produksi dalam bentuk
Ah Ap γ (dimana h ≤ p )
i) Jika h = p , lakukan penghilangan rekursif kiri
ii) Jika h < p, aturan produksi sudah benar
Jika terjadi penghilangan rekursif kiri pada tahap (2b), sejumlah simbol variabel
baru yang muncul dari operasi ini dapat disisipkan pada urutan variabelsemula
dimana saja asalkan ditempatkan tidak sebelum Ah (di kiri)
Setelah langkah (2) & (3) dikerjakan maka aturan-aturan produksi yang ruas
kanannya dimulai simbol variabel sudah berada dalam urutan yang benar
Ax Ay γ ( di mana x < y )
Produksi-produksi yang lain ada dalam bentuk:
Ax a γ ( a = simbol terminal )
Bx γ
( B2 = simbol variabel baru yang akan muncul sebagai akibat dari operasi
penghilangan rekursif kiri )
Bentuk normal Greibach diperoleh dengan cara melakukan substitusi mundur
mulai dari variabel Am, lalu Am-1, Am-2, ..... Dengan cara ini aturan produksi dalam
bentuk Ax
Ay γ dapat diubah sehinga ruas kanannya dimulai dengan simbol
terminal.
Produksi dalam bentuk Bx
γ juga dapat diubah dengan cara substitusi seperti
pada langkah (5)
Contoh (tata bahasa bebas konteks sudah dalam bentuk normal Chomsky dan
memenuhi syarat untuk diubah ke bentuk normal Greibach), simbol awal adalah S:
S
A
B
C
D
CA
a|d
b
DD
AB
Kita tentukan urutan simbol variabel, misalnya S, A, B, C, D (S<A<B<C<D).
*Perhatikan urutan tersebut boleh anda tentukan sendiri, buatlah urutan sedemikian
sehingga memudahkan untuk proses selanjutnya
Kita periksa aturan produksi yang simbol pertama pada ruas kanan adalah simbol
variabel, apakah sudah memenuhi ketentuan urutan variabel:
S CA ( sudah memenuhi aturan karena S<C)
C DD (sudah memenuhi karena C<D)
D AB (tidak memenuhi, karena D>A)
61
Yang belum memenuhi urutan yang telah kita tentukan adalah: D
AB, karena
ruas kiri > simbol pertama pada ruas kanan. Maka kita lakukan sibstitusi pada
simbol variabel A, aturan produksi menjadi:
D
aB | dB
Setelah semua aturan produksi sudah memenuhi ketentuan urutan variabel, kita
lakukan substitusi mundur pada aturan produksi yang belum dalam bentuk normal
Greibach (‘=>’ dibaca ‘menjadi’):
C
S
DD => C
CA => S
aBD | dBD
aBDA | dBDA
*Perhatikan substitusi mundur dimulai dari aturan produksi yang memiliki ruas kiri
dengan urutan variabel paling akhir ( kasus di atas:S<A<B<C<D, maka C lebih dulu
disubstitusikan daripada S )
Hasil akhir aturan produksi yang sudah dalam bentuk normal Greibach :
S
A
B
C
D
aBDA | dBDA
a|d
b
aBD | dBD
aB | dB
*Perhatikan : setiap substitusi kita lakukan pada simbol variabel pertamapada ruas kanan
( pada aturan produksi yang belum bentuk normal Greibach tentunya ).
Prinsipnya:
Biarkan aturan produksi yang sudah dalam bentuk normal Greibach
Tentukan pengurutan simbol variabel, berdasarkan kondisi aturan produksi yang
ada buatlah urutan sedemikian sehingga memudahkan untuk proses selanjutnya.
Mulailah terlebih dahulu dari seimbol awal.
Lakukan perubahan pada aturan produksi yang belum memenuhi ketentuan urutan
tersebut dan bila perlu selama proses itu bisa dilakukan substitusi dan
penghilangan rekursif kiri
Lakukan substitusi mundur sedemikian rupa sehingga semua aturan produksi akan
diawali dengan tepat sebuah simbol terminal. Proses substitusi mundur dimulai
dari aturan produksi dengan urutan paling akhir.
Lakukan substitusi mundur juga pada aturan produksi baru yang muncul sebagai
hasil penghilangan rekursif kiri.
Contoh lain (simbol awal A):
A BC
B CA | b
C AB | a
62
Kita tentukan urutan simbol: A,B,C ( A<B<C )
A
B
C
BC ( sudah memenuhi karena A<B)
CA (sudah memenuhi karena B<C)
AB (padahal C > A sehingga harus diubah)
Pengubahan C
C AB => C
AB:
BCB => C
CACB | bCB
Untuk C CACB lakukan penghilangan rekursif kiri menjadi
C bCBZ1 | aZ1
Z1 ACB
Z1 ACBZ1
Kita lihat seluruh hasil produksi dari variabel C, sudah dalam bentuk normal
Greibach:
C bCBZ1 | aZ1 | bCB | a
Setelah semua aturan produksi sudah memenuhi ketentuan urutan variabel, kita
laukan substitusi mundur:
B CA => B bCBZ1A | aZ1A | bCBA | aA
A BC => A bCBZ1AC | aZ1AC | bCBAC | aAC | bC
Selanjutnya lakukan pula substitusi pada aturan produksi dengan variabel baru
yang terbentuk (pada contoh ini Z1):
Z1 ACB => Z1 bCBZ1ACCB | aZ1ACCB | bCBACCB | aACCB | bCCB
Z1
ACBZ1 => Z1
bCBZ1ACCBZ1 | aZ1ACCBZ1 | bCBACCBZ1 | aACCBZ1
| bCCBZ1
A
B
C
Z1
Z1
Hasil akhir aturan produksi dalam bentuk bentuk normal Greibach:
bCBZ1AC | aZ1AC | bCBAC | aAC | bC |
bCBZ1A | aZ1A | bCBA | aA | B
bCBZ1 | aZ1 | bCB | a
bCBZ1ACCB | aZ1ACCB | bCBACCB | aACCB | bCCB
bCBZ1ACCBZ1 | aZ1ACCBZ1 | bCBACCBZ1 | aACCBZ1 | bCCBZ1
63

Welcome In Blogging Is My Life

Contoh Sliding Login Dengan JQuery

Disamping ini adalah contoh Sliding Login menggunakan JQuery. Login Form Disamping hanya Contoh dan tidak dapat digunakan layaknya Login Form FB, Karena Blog ini terbuka untuk umum tanpa perlu mendaftar menjadi Member

Tutorial Blog

Untuk membuatnya Silahkan : Klik Disini

Member Login

Lost your password?

Not a member yet? Sign Up!