🐠 Penyederhanaan Tata Bahasa Bebas Konteks

Dalam mengkonstruksikan Aturan Produksi tata bahasa reguler dari sebuah FSA adalah memperhatikan State-State yang bisa menuju ke State Akhir, Misalkan diketahui FSA : b q 0 a q 1 b a q 2. Kita Ganti nama semua state yaitu : q 0 = S, q 1 = A, q 2 tidak diganti karestate akhir dan dari q 2 tidak ada busur keluar, sehingga menjadi b S a A a b Abstract. Teori Bahasa Automata Penyederhanaan Bahasa Bebas Konteks. Item Type: Teaching Resource Subjects: Materi Kuliah Online > Materi Kuliah Tahun 2013 CFG / Tata Bahasa Bebas Konteks Pada tata bahasa bebas konteks tidak terdapat pembatasan hasil produksinya. Batasan ruas kiri adalah sebuah simbol variabel. Contoh : CFG : B → CDe. Fg D → Bc. De Pd bhs regular, bagian yg belum terturunkan tsb selalu terjadi pd suatu ujung. Bentuk normal Chomsky / Chomsky Normal Form (CNF) merupakan salah satu bentuk normal yang sangat berguna untuk Context Free Grammar (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 Tata bahasa bebas konteks setelah penyederhanaan : S Ab | d A d Contoh 6 : S dA | Bd A bc A c B c Teori Bahasa dan Automata (2010) 51 Variabel yang nullable adalah A, A c bukan satu-satunya produksi dari A. Maka kita ganti S dA manjadi S dA | d kemudian A c dihapus. Penurunan terkanan ( rightmost derivation) : simbol variabel terkanan yang diperluas terlebih dahulu. Contoh 2. 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: 3. Penyederhanaan Tata Bahasa Bebas Konteks - Dilakukan agar tidak menghasilkan pohon penurunan yang rumit dan tidak perlu atau tidak berarti. a. Penghilangan Produksi Useless (Tidak Berguna) Contoh 1 : S → aSa | Abd | Bde A → Ada B → BBB | a Maka, variabel A tidak memiliki penurunan yang menuju terminal, sehingga dihilangkan Bahasa Bebas Konteks a. Penyederhanaan tata bahasa bebas konteks b. Bentuk Normal Chomsky 10,11 PushDown Automata (PDA) a. Pengertian PDA b. PDA deterministik/non deterministik. 12 Mesin Turing a. Pengertian Mesin Turing b. Penerimaan pada MT 13-15 Topik Khusus Topik-topik khusus/ masalah2 yang lebih kompleks dari teori bahasa dan otomata. 42 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 AA Qu2A.

penyederhanaan tata bahasa bebas konteks