BAB I
PENDAHULUAN

1.1  LATAR BELAKANG MASALAH
Sudah tidak bisa dipungkiri lagi, seiring berkembangnya sains dan teknologi yang sangat pesat  di saat ini, maka perkembangan mesin pun mengikuti, dan menuntut kita untuk mengetahuinya. Dan salah satu cara untuk mengetahui dan memperdalam masalah mesin dan lain sebagainya kita bisa mempelajari mata kuliah Teori Bahasa dan Otomata. Maka dari itu kami membahas salah satu materi yang ada di dalam Teori Bahasa dan Otomata dengan harapan bisa menambah pengetahuan pembaca tentang otomata.

1.2  RUMUSAN MASALAH
Dalam pembahasan ini kami menguraikan beberapa hal tentang macam-macam penyederhanaan tata bahasa bebas konteks (cfg).
1.    Menghilangkan produksi yang useless (tidak berguna)
2.    Menghilangkan produksi unit
3.    Menghilangkan produksi ε

1.3  TUJUAN PEMBAHASAN
Tujuan dari pembahasan ini adalah untuk memenuhi tugas mata kuliah Teori Bahasa dan Otomata.

1.4  MANFAAT PEMBAHASAN
Manfaat yang diharapkan dari pembahasan ini adalah:
  1. Pembaca bisa lebih memahami seputar Teori Bahasa dan Otomata.
  2. Khususnya fokus pada materi penyederhanaan tata bahasa bebas konteks (cfg).
BAB II
PEMBAHASAN

2.1.  PENYEDERHANAAN TATA BAHASA BEBAS KONTEKS (CFG)
Penyederhanaan tata bahasa bebas konteks ini memiliki tujuan agar tidak menghasilkan pohon penurunan yang memiliki kerumitan yang tidak diperlukan atau menghilangkan aturan produksiyang tidak berarti.
Langkah-langkah penyederhanaan dari tatabahasa bebas konteks ini adalah dengan cara :
1.      Menghilangkan produksi yang useless (tidak berguna)
2.      Menghilangkan produksi unit
3.      Menghilangkan produksi ε
Apa yang dumaksud dengan produksi useless, produksi unit dan produksi ε ? dan bagaimana cara menghilangkannya ? mari kita lihat pembahasannya berikut ini.

2.1.1.      Menghilangkan Produksi Useless
Produksi Useless didefinisikan sebagai berikut :
Poduksi yang memuat simbol variable yang tidak memiliki penurunan yang akan menghasilkan terminal-terminal seluruhnya, Produksi yang tidak akan pernah dicapai dengan penurunan apapun dari simbol awal, sehingga produk itu redudan (berlebih).
Contoh :
Terdapat aturan produksi sebagai berikut :
S à aBD
B à cD | Ab
D à ef
A à Ed
F àdc
 Analisa :
1)      Pada aturan produksi A à Ed, E tidak memiliki penurunan. sehingga dapat dihilangkan
2)      Aturan produksi F à­­­­ dc, redudan. sehingga aturan produksi tersebut dapat dihilangkan
Sisa aturan produksi yang telah disederhanakan adalah sebagai berikut :
S à aBD
B à cD | Ab
D à ef

Analisa kembali :
aturan produksi B à Ab, A tidak memiliki penurunan. sehingga didapat penyederhanaan lagi menjadi
S à aBD
Bà cD
D à ef
Kesimpulannya adalah bahwa produk useless yang dihilangkan adalah :
Aà> Ed
F à dc
Bà Ab

2.1.2.      Menghilangkan Produksi Unit
Produksi Unit adalah produksi dimana ruas kiri dan kanan aturan produksi hanya berupa satu simbol variabel. Contoh : A à B, C à D
keberadaan produksi unit ini membuat tata bahasa memiliki kerumitan yang tak perlu. untuk menyederhanakan produksi unit, dilakukan penggantian aturan produksi unit tersebut.
Contoh :
diberikan aturan produksi sebagai berikut :
S à A
S à Aa
A à B
B àC
B à b
C à D
C à ab
D à b
Lakukan penggantian berurutan mulai dari aturan produksi yang paling dekat menuju ke penurunan terminal-terminal (" è" dibaca "menjadi")
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 è S à ab | b
sehingga aturan produksi yang telah disederhanakan dengan menghilangkan produksi unit adalah sebagai berikut :
S à ab | b
S à Aa
A à ab | b
B àab
B à b
C à b
C à ab
D à b

2.1.3.      Menghilangkan Produksi ε
Produksi ε adalah produksi dalam bentuk α -> ε atau bisa dianggap sebagai produksi kosong (empty). penghilangan produksi  ε dilakukan dengan melakukan penggantian produksi yang memuat variable yang bisa menuju produksi ε, atau disebut Nullable.
Contoh :
terdapat tata bahasa bebas konteks sebagai berikut :
S à aB | Cd
A à d
C à ε
Variable yang nullable adalah variable C, karena penurunan C -> ε merupakan penurunan satu2nya dari C. maka qita ganti S -> Cd menjadi S -> d. kemudian produksi C -> ε kita hapus.
Hasil penyederhanaannya adalah :
S à aB | d
A à d
Dalam 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 (CNF).
Urutan dari penyederhanaan aturan produksi bebas konteks adalah sebagai berikut :
Hilangkan produksi ε
Hilangkan produksi unit
Hilangkan produksi useless

2.2.               CONTEXT-FREE GRAMMAR (CFG) DAN PARSING
Bentuk umum produksi CFG adalah : a ® b, a Î V, b Î (V½V)* Analisis sintaks : Penelusuran sebuah kalimat (sentensial) sampai pada simbol awal grammar. Analisis sintaks dapat dilakukan melalui derivasi atau parsing. Penelusuran melalui parsing menghasilkan pohon sintaks.
Contoh:
Diketahui grammar G = {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)
I Þ IH
Þ IAH
Þ IAAH
Þ HAAH
Þ xAAH
Þ x2AH
Þ x23H
Þ x23b
cara 2 (parsing)
I
I H
|
I A b
|
I A 3
| |
H 2
|
X
Contoh : Diketahui grammar G = {S ® SOS½A , O ® *½+, A ® 0½1½2½…½9} Kalimat : 2*3+7 mempunyai dua pohon sintaks berikut :
S S
| |
S O S S O S
| | | | | |
A * S O S S O S + A
| | | | | | | |
2 A + A A * 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.

Metoda Parsing                                                                                             
Ada 2 metoda parsing : top-down dan bottom-up. n Parsing top-down :
Parsing dimulai dari simbol awal S sampai kalimat x n Parsing bottom-up :
Parsing dimulai dari kalimat x sampai simbol awal S Parsing Top-down n Ada 2 kelas metoda parsing top-down : 1. kelas metoda dengan backup, Contoh: metoda Brute-Force
2. kelas metoda tanpa backup
Contoh: metoda recursive descent. n

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.
n Metoda Recursive-Descent n 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.
n 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.
Parsing Bottom-Up
n Salah satunya adalah grammar preseden sederhana (GPS).
n Pengertian Dasar
n Jika a dan x keduanya diderivasi dari simbol awal grammar tertentu, maka a disebut sentensial jika a Î (V½ V)*, dan x disebut kalimat jika x Î (V)*
n Misalkan a = Q1b Q2 adalah sentensial dan A Î VN :
- b adalah frase dari sentensial a jika : S Þ ¼ Þ Q1 a Q2 dan a Þ ¼ Þ b
- b adalah simple frase dari sentensial a jika : S Þ ¼ Þ Q1 a Q2 dan a Þ b
- Simple frase terkiri dinamakan handel
- frase, simple frase, dan handel adalah string dengan panjang ≥ 0
Contoh:
(1) I ⇒ I H Hb adalah sentensial dan b adalah simple frase
⇒ H H (dibandingkan dengan Q1 β Q 2 maka Q1 = H, β = b, dan Q2 = ε)
⇒ H b Perhatikan : simple frase (b) adalah yang terakhir diturunkan
(2) I ⇒ I H Hb adalah sentensial dan H adalah simple frase
⇒ I b (dibandingkan dengan Q 1 β Q 2 maka Q1 = ε, β = H, dan Q 2 = b)
⇒ H b Perhatikan : simple frase (H) adalah yang terakhir diturunkan
Sentensial Hb mempunyai dua simple frase (b dan H), sedangkan handelnya adalah H.