Jumat, 05 Oktober 2012

Makalah Teori Bahasa dan Otomata


BAB I
PEMBAHASAN
1.1.  Tata Bahasa Bebas Konteks
CFG / Bahasa Bebas Konteks adalah sebuah tata bahasa dimana tidak terdapat pembatasan pada hasil produksinya, Contoh Pada aturan produksi :

a → b

batasannya hanyalah ruas kiri (a) adalah sebuah simbol variabel. Sedangkan contoh aturan produksi yang termasuk CFG adalah seperti di bawah :

B → CDeFg

D → BcDe

Tata bahasa bebas konteks ( CFG ) adalah tata bahasa yang mempunyai tujuan sama seperti halnya tata bahasa regular yaitu merupakan suatu cara untuk menunjukkan bagaimana menghasilkan suatu untai-untai dalam sebuah bahasa.Bila pada tata bahasa regular terdapat pembatasan pada ruas kanan atau hasil produksinya, maka pada tata bahasa bebas konteks/ context free grammar, selanjutnya kita sebut CFG, tidak terdapat pembatasan hasil produksinya. Pada aturan produksi:
a à b
batasannya hanyalah ruas kiri (a) adalah sebuah symbol variabel.
Contoh aturan produksi yang termasuk CFG:
B à CDeFg
D à BcDe
Seperti halnya pada tata bahasa regular, sebuah tata bahasa bebas konteks adalah suatu cara yang menunjukkan bagaimana menghasilkan untai-untai dalam sebuah bahasa. Seperti kita ketahui, pada saat menurunkan  suatu string, symbol-simbol variabel akan mewakili bagian-bagian yang belum yang belum terturunkan dari string tersebut. Bila pada tata bahasa regular, bagian yang belum terturunkan tersebut selalu terjadi pada suatu ujung, pada tata bahasa bebas konteks bisa terdapat lebih banyak bagian yang belum terturunkan itu dan bisa terjadi dimana saja. Ketika penurunan itu sudah lengkap, semua bagian yang belum terturunkan telah diganti oleh string-string (yang mungkin saja kosong) dari himpunan symbol terminal. Bahasa bebas konteks menjadi dasar dalam pembentukan suatu parser/proses analisis sintaksis. Bagian sintaks dalam suatu kompilator kebanyakan didefinisikan dalam tata bahasa bebas konteks.
1.2.  Parsing
CFG menjadi dasar dalam pembentukan suatu parser/proses analisis sintaksis. Bagian sintaks dalam suatu kompilator kebanyakan di definisikan dalam tata bahasa bebas konteks. Pohon penurunan ( derivation tree/parse tree) berguna untuk menggambarkan simbol-simbol variabel menjadi simbol-simbol terminal setiap simbol variabel akan di turunkan menjadi terminal sampai tidak ada yang belum tergantikan.

Contoh, terdapat CFG dengan aturan produksi sebagai berikut dengan simbol awal S :

S → AB

A → aA | a

B → bB | b

Maka jika kita ingin mencari gambar pohon penurunan dengan untai : ‘aabbb’ hasilnya adalah seperti di bawah :

Proses penurunan / parsing bisa dilakukan dengan cara sebagai berikut :


Penurunan terkiri (leftmost derivation): simbol variabel terkiri yang di perluas terlebih dahulu. Penurunan terkanan ( rightmost derivation ) : simbol variabel terkanan yang diperluas terlebih dahulu.
Misal : Tata bahasa sbb :

S → aAS | a

A → SbA | ba

Untuk memperoleh untai ‘aabbaa’ dari tata bahasa diatas dilakukan dengan cara :
Penurunan terkiri : S => aAS => aSbAS => aabAS => aabbaS => aabbaa
Penurunan terkanan       : S => aAS => aAa => aSbAa => aAbbaa => aabbaa
Sebuah pohon (tree) adalah suatu graph terhubung tidak sirkuler, yang memiliki satu simpul (node)/vertex disebut akar (root) dan dari situ memiliki lintasan ke setiap simpul. Gambar 1 memberikan contoh sebuah tree yang menguraikan kalimat dalam bahasa Inggris:  The quick brown fox jumped over the lazy dog
Pohon penurunan (derivation tree/parse tree) berguna untuk menggambarkan bagaimana memperoleh suatu string (untai) dengan cara menurunkan simbol- simbol variabel menjadi simbol-simbol terminal. Setiap simbol variabel akan diturunkan menjadi terminal, sampai tidak ada yang belum tergantikan.
Misal terdapat tata bahasa bebas konteks dengan aturan produksi (symbol awal S, selanjutnya didalam bab ini digunakan sebagai symbol awal untuk tata bahasa bebas konteks adalah S):
S à AB
A à aA | a
B à bB | b
Akan kita gambarkan pohon penurunan untuk memperoleh untai: ‘aabbb’. Pada pohon tersebut symbol awal akan menjadi akar (root). Setiap kali penurunan dipilih aturan produksi yang menuju ke solusi. Simbol-simbol variabel akan menjadi simpul-simpul yang mempunyai anak. Simpul-simpul yang tidak mempunyai anak akan menjadi symbol terminal. Kalau kita baca symbol terminal yang ada pada gambar 2 dari kiri ke kanan akan diperoleh unatai ‘aabbb’.
Proses penurunan atau parsing bisa dilakukan dengan cara:
·         Penurunan terkiri (leftmost derivation): symbol variabel terkiri yang diperluas terlebih dahulu.
·         Penurunan terkanan (rightmost derivation): symbol variabel terkiri yang diperluas terlebih dahulu
      Misal terdapat tata bahasa bebas konteks:
S à aAS | a
A à SbA | ba
Untuk memperoleh untai ‘aabbaa’ dari tata bahasa bebas konteks diatas (‘Þ’ bisa dibaca ‘menurunkan’)
·         Dengan penurunan terkiri: S Þ aAS Þ aSbAS Þ aabAS Þ aabbaS Þ aabbaa
·         Dengan penurunan terkanan: S Þ aAS Þ aAa Þ aSbAa Þ aSbbaa Þ aabbaa
Meskipun proses penurunannya berbeda akan tetap memiliki pohon penurunan yang sama.
            Biasanya persoalan yang diberikan berkaitan dengan pohon penurunan, adalah untuk mencari penurunan yang hasilnya menuju kepada suatu untai yang ditentukan. Dalam hal ini, perlu untuk melakukan percobaan pemilihan aturan produksi yang bisa menuju ke solusi. Misalkan  sebuah tata bahasa bebas konteks memiliki aturan produksi:
S à aB | bA
A à a | aS | bAA
B à b | bS | aBB
Pohon penurunan untuk memperoleh :’ aaabbabbba”
1.3.  Ambiguitas
Ambiguitas terjadi bila terdapat lebih dari satu pohon penurunan yang berbeda untuk memperoleh suatu untai.
Misalkan terdapat tata bahasa sebagai berikut :
S → A | B
A → a
B → a
Untuk memperoleh untai ‘a’ bisa terdapat dua cara penurunan sebagai berikut :
· S => A => a
· S => B => a
Ambiguitas/kedwiartian terjadi bila terdapat lebih dari satu pohon penurunan yang berbeda untuk memperoleh suatu untai.
Misalkan terdapat tata bahasa bebas konteks:
S à A | B
A à a
B à a
Untuk memperoleh untai ‘a’ bisa terdapat dua cara penurunan:
·         S Þ A Þ a
·         S Þ B Þ a
Contoh lain, terdapat tata bahasa bebas konteks:
S à SbS | ScS | a
Kita bisa menurunkan untai ‘abaca’ dalam dua cara
·         S Þ SbS Þ SbScS Þ SbSca Þ Sbaca Þ abaca
·         S Þ ScS Þ SbScS Þ abScS Þ abacS Þ abaca
Pohon penurunannya bisa dilihat pada gambar 5 dan 6
            Kita lihat untuk untai yang sama (‘abaca) dapat dibuat pohon penurunan yang berbeda, maka dapat dikatakan tata bahasa bebas konteks tersebut ambigu. Jadi untuk menunjukkan bahwa suatu tata bahasa bebas konteks ambigu, bisa dilakukan dengan menemukan untai yang memungkinkan pembentukan lebih dari satu pohon penurunan. Ambiguitas dapat menimbulkan masalah pada bahasa-bahasa tertentu, baik pada bahasa alami maupun pada bahasa pemrograman. Bila suatu struktur bahasa memiliki lebih dari suatu dekomposisi (penurunan), dan susunannya akan menentukan arti, maka artinya menjadi ambigu.



 1.4. Penyederhanaan Tata bahasa bebas konteks
1.4.1. Tujuan Penyederhanaan       
Penyederhanaan tata bahasa bebas konteks bertujuan untuk melakukan pembatasan sehingga tidak menghasilkan pohon penurunan yang memiliki kerumitan yang tak pelu atau aturan produksi yang tak berarti. Misalkan terdapat tata bahasa bebas konteks (dengan symbol awal S, dalam bab ini kita gunakan sebagai symbol awal untuk tata bahasa bebas konteks adalah S) :
SàAB | a
Aàa
            Kelemahan tata bahasa bebas konteks di atas, aturan produksi SàAB tidak berarti karena B tidak memiliki penurunan.
untuk tata bahasa bebas konteks berikut :
SàA
AàB
BàC
CàD
Dàa | A
memiliki kelemahan terlalu panjang jalannya padahal berujung pada Sàa, produksi DàA juga menyebabkan kerumitan.
            Suatu tata bahasa bebas konteks dapat disederhanakan dengan melakukan :
1.      penghgilangan produksi useless
2.      penghilangan produksi unit
3.      penghilangna produksi e
            Selanjutnya akan kita bahas satu persatu cara penyederhanaan tersebut.

1.4.2. Penghilangan Produksi Useless
Disini produksi useless didefinisikan sebagai :
·         Produksi yang memuat symbol variabel yang tidak memiliki penurunan yang akan menghasilkan terminal-terminal seluruhnya (kita sebut saja sebagai ‘menuju terminal’), produksi ini tidak berguna karena bila diturunkan tidak akan pernah selesai (masih ada symbol variabel yang tersisa)
·         produksi yang tidak akan pernah dicapai dengan penurunan apapun dari symbol awal, sehingga produksi itu redundan ( berlebih )
Contoh
      terdapat tata bahasa bebas konteks :
SàaSa| Abd | Bde
AàAda
BàBBB | a
Bisa kita lihat :
1.      Simbol variabel A tidak memiliki penurunan yang menuju terminal sehingga bisa dihilangkan.
2.      Konsekuensi no (1), aturan produksi Sà Abd tidak memiliki penurunan
Maka tata bahsa bebas kontek setelah  disederhanakan menjadi :
SàaSa | Bde
BàBBB | a

Contoh, terdapat tata bahasa bebas konteks :
SàAa | B
Aàab | D
Bàb | E
Càbb
EàaEa
Bisa kita lihat :
1.      Aturan produksi AàD, symbol variabel D tidak memiliki penurunan
2.      Aturan produksi Càbb, bila kita coba melakukan penurunan dari symbol awal S, dengan jalan mana pun tidak akan pernah mencapai C
3.      Simbol variabel E tidak memiliki aturan produksi yang menuju terminal (EàaEa satu-satunya aturan produksi dari E
4.      Konsekuensi no (3) Aturan produksi BàE, symbol variabel E tidak memiliki penurunan

maka dari tata bahasa bebas konteks di atas, produksi yang useless :
AàD
Càbb
EàaEa
BàE
maka tata bahasa bebas konteks setelah disederhanakan menjadi :
SàAa | B
Aàab
Bàb
Contoh tata bahasa bebas konteks :
SàaAb | cEB
AàdBE  | eeC
Bàff
Càae
Dàh
Kita lihat :
1.      Aturan produksi SàcEB, AàdBE ( E tidak memiliki penurunan)
2.      Aturan produksi Dàh, redundan
Sisa aturan produksi
SàaAb
AàeeC
Bàff
Càae
Kita lihat sekarang Bàff  juga redundan sehingga hasil penyederhanaan menjadi :
SàaAb
AàeeC
Càae
Contoh tata bahasa bebas konteks :
SàaB
AàbcD | dAC
Bàe | Ab
CàbCd | adF | ab
FàcFB
1.      Aturan produksi AàbcD, variabel D tidak memiliki penurunan
2.      Konsekuensi no (1), symbol 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àbCd | ab
Contoh tata bahasa bebas konteks :
SàaBD
BàcD | Ab
Dàef
AàEd
Fàdc
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
Kita lihat sekarang BàAb, A tidak memiliki penurunan
Aturan produksi setelah disederhanakan :
SàaBD
BàcD
Dàef
Contoh tata bahasa bebas konteks :
SàAbc | ab
AàAAA | e
Aturan produksi setelah disederhanakan :
SàAbc | ab
AàAAA | e
Ingat A à e juga harus diperhitungkan
* Prinsipnya setiap kali melakukan penyederhanaan kita periksa lagi aturan produksi yang tersisa, apakah semua produksi yang useless sudah dihilangkan.

1.4.3. Penghilangan Produksi Unit
            Produksi unit adalah produksi dimana ruas kiri dan ruas kanan aturan produksi hanya berupa satu symbol variabel, misalkan Aà B, C à D. Keberadaan produksi unit membuat tata bahasa memiliki kerumitan yang tak perlu atau menambah panjang penurunan. Penyederhanaan ini dilakukan dengan melakukan pengantian aturan produksi unit.
Contoh tata bahasa bebas konteks :
SàSb
SàC
CàD
Càef
Dàdd
Kita lakukan penggantian berurutan 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
Dàdd
Contoh tata bahasa bebas konteks :
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 kita cukup tuliskan Bàab
· AàB => Aàab  | b
· SàA => Sàab  | b
Sehingga aturan produksi setelah penyederhanaan :
Sàab  | b
SàAa
Aàab  | b
Bàab
Bàb
Càb
Càab
Dàb
Contoh tata bahasa bebas konteks :
SàCba | D
AàbbC
BàSc | ddd
CàeA | f | C
DàE | SABC
Eàgh
Penggantian yang dilakukan :
· DàE => DàGH
· CàC, kita hapus
· SàD => 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

1.4.4. Penghilangan Produksi e
            Produksi e adalah produksi dalam bentuk
aàe
atau bisa dianggap sebagai produksi kosong. Penghilangan produksi e dilakukan dengan melakukan penggantian produksi yang memuat variabel yang bisa menuju produksi e , atau biasa disebut nullable. Prinsip penggantiannya bisa dilihat kasus berikut :
SàbcAd
Aàe
            Pada kasus di atas A nullable, serta A à e satu-satnya produksi dari A, maka variabel A bisa ditiadakan , hasil penyederhanaan tata bahasa bebas konteks menjadi :
Sàbcd
Tetapi bila kasusnya :
SàbcAd
Aàbd | e
Pada kasus di atas A nullable, tapi Aà e bukan satu-satunya produksi dari A, maka hasil penyederhanaan :
SàbcAd | bcd
Aàbd
Contoh tata bahasa bebas konteks :
SàAb | Cd
Aàd
Càe
Variabel yang nullable adalah A, B, C. Dari Sà AB , maka S juga nullable. Kita lakukan penggantian :
·         AàaCa => Aàaa
·         BàbA => Bà bA | b
·         BàBB => Bà BB | B
·         Aà abB => Aà abB | ab
·         Sà AB => SàAB | A | B | e
·         Cà e, Bàe, Aàe dihapus

* Perhatikan : untuk penggantian Sà AB kita tetap mempertahankan produksi S à e , karena S merupakan symbol awal. Ini merupakan satu-satunya perkecualian produksi e yang tidak dihapus, yaitu produksi e yang dihasilkan oleh symbol awal.

Hasil akhir penyederhanaan :
Sà AB | A | B | e
AàabB | ab | aa
Bà bA | b | BB | B
Contoh tata bahasa bebas konteks :
SàaAb
AàaAb | e
Hasil penyederhanaan :
Sà aAb | ab
Aà aAb | ab

Contoh tata bahasa bebas konteks :
Sà ABaC
Aà BC
Bà b | e
CàD | e
Dà d
Hasil penyederhanaan :
Sà ABaC | BaC | AaC | ABa | aC | Aa | Ba | a
Aà B | C | BCB
Bà b
Cà D
Dàd

            Pada prakteknya ketiga penyederhanaan tersebut ( penghilangan useless, unit, e ) dilakukan bersama pada suatu tata bahasa bebas konteks, yang nantinya menyiapkan tata bahasa bebas konteks tersebut untuk diubah ke dalam suatu bentuk normal Chomsky yang akan dibahas pada bab selanjutnya. Hal yang memerlukan perhatian adalah penghilangan suatu tipe produksi bisa menghasilkan produksi tipe yang lain , hal ini didasari kenyataan bahwa penghilangan produksi e bisa menghasilkan produksi unit. Tapi perhatikan juga bahwa penghilangan produksi unit tidak menghasilkan produksi e, dan penghilangan produksi useless tidak menghasilkan produksi unit maupun produksi e. Maka kita bisa menghapuskan semua produksi yang tidak diinginkan tersebut dengan melakukan urutan sebagai berikut :
1.      Hilangkan produksi e
2.      Hilangkan produksi unit
3.      Hilangkan produksi useless
            Bisa dilihat alur penyederhanaan tata bahasa bebas konteks pada gambar berikut.
Gambar 1 Penyederhanaan tata bahasa bebas konteks
      Hasil yang kita peroleh adalah tata bahasa yang sudah bebas dari ketiga jenis produksi tersebut. Kita harus mencoba untuk melakukan ketiga penyederhanaan tersebut pada aturan produksi berikut :
Sà AA | C | bd
Aà Bb | e
Bà AB | d
Cà de
Pertama-tama kita lakukan penghilangan produksi e, sehingga aturan produksi menjadi :
Sà A | AA | C | bd
Aà Bb
Bà B | AB | d
C à de
Nampak bahwa penghlangan produksi e berpotensi untuk menghasilkan produksi unit yang baru yang sebelumnnya tidak ada.
Selanjutnya kita lakukan penghilangan produksi unti menjadi :

Sà Bb | AA | de | bd
A à Bb
Bà AB | d
C à de
Anda lihat, penghilangan produksi unit bisa menghasilkan produksi useless. Terakhir kita lakukan penghilangan produksi useless :
Sà Bb | AA | de | bd
A à Bb
Bà AB | d

Bisa anda periksa, hasil akhir aturan produksi tidak lagi memiliki produksi e, produksi unit maupun produksi useless.
Langkah Penyederhanaannya :
  • Hilangkan simbol yang terdapat empty ( Є ) dalam himpunan produksi
  • Simbol variabel tidak di hapus jika terdapat cabang terminal / variabel yang saling berhubungan
  • Buat himpunan dengan simbol yang dihilangkan dan yang tidak
Contoh :
S → bcAd
A → e
Maka variabel A bisa di hilangkan, sehingga menjadi :
S → bcd

Ø Kasus lain :
S → bcAd
A → bd | Є
Ø Maka hasilnya akan menjadi :
S → bcAd | bcd
A → bd
Karena A → Є bukan satu-satunya produksi dari A
Ø Kasus lainya :
S → Ab | Cd
A → d
C → Є
Ø Hasil penyederhanaan sebagai berikut :
S → Ab | d
A → d
Ø Contoh lain :
S → dA | Bd
A → bc
A → Є
B → c
Ø Hasil penyederhanaan sebagai berikut :

S → dA | Bd
A → bc
B → c
Ø Contoh lainya :
S → AaCD
A → CD | AB
B → b | Є
C → d | Є
D → Є
Ø Hasil penyederhanaan sebagai berikut :
S → AaC | aC |Aa | a
A → C | AB | A | B               B → b                        C → d

3 komentar:

  1. Ada soal yang lebih rumit nih...

    Jika diketahui CFG, sbb :

    S --> kA | BAj | m
    A --> Bb | a | ε
    B --> bS | cA | d

    Coba lakukan langkah2 penyederhanaan CFG !

    Bagaimanakah penyelesaiannya ??? :)

    Mohon penjelasannya ya ! :)

    BalasHapus
  2. Ad -> dB itu bebas konteks atau bukan?

    BalasHapus

resep donat empuk ala dunkin donut resep kue cubit coklat enak dan sederhana resep donat kentang empuk lembut dan enak resep es krim goreng coklat kriuk mudah dan sederhana resep es krim coklat lembut resep bolu karamel panggang sarang semut

Copyright © Deja Area | Powered by Blogger

Design by Anders Noren | Blogger Theme by NewBloggerThemes.com | BTheme.net      Up ↑