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