Bentuk Normal Greibach (Greibach Normal Form)
Pertemuan 10Mahasiswa mampu menerapkan konsep & definisiBentuk Normal Greibach ( Greibach Normal Form)
2 Materi Pengertian Bentuk Normal Greibach
Pembentukan Bentuk Normal Greibach dengan substitusi
3 Pengertian Bentuk Normal Greibach
Merupakan bentuk normal pada CFG yang membatasi posisi munculnya terminal-terminal dan variabel variabel. dalam bentuk normal Greibach, bila hasil produksinya (pada ruas kanan) diawali dengan simbol terminal selanjutnya bisa diikuti dengan simbol variabel Contoh : S→a |aAB A→a B
4 Pembentukan Bentuk Normal Greibach dengan substitusi
Syarat : Produksi sudah dalam bentuk Normal Chomsky, tidak rekursif kiri dan tidak menghasilkan produksi empty
5 Pembentukan Bentuk Normal Greibach dengan substitusi
6 Pembentukan Bentuk Normal Greibach dengan substitusi
7 Pembentukan Bentuk Normal Greibach dengan substitusi
8 ContohSimbol awal S : S →CA A → a | d B → b C → DD D → AB
9 PenyelesaianYang belum normal Greibach : S →CA C → DD D → AB 1. Tentukan urutan simbol variabel : S, A, B, C, D (S < A < B < C < D) (urutan bisa berubah sesuai keinginan) 2. Periksa ketentuan urutan variabel : S → CA (sudah memenuhi, karena S < C) C → DD (sudah memenuhi, karena C <D) D → AB (tidak memenuhi, karena D > A) 3. Lakukan substitusi pada D → AB dengan melakukan substitusi pada variabel A sehingga aturan menjadi : D → AB ⟹ aB | dB
10 Penyelesaian4. Lakukan substitusi mundur pada aturan yang belum dalam bentuk normal Greibach C → DD ⟹ aBD | dBD S → CA ⟹ aBDA | dBDA 5. Aturan produksi yang sudah dalam bentuk normal Greibach S → aBDA | dBDA A → a | d B → b C → aBD | dBD D → aB | dB
(sumber) https://slideplayer.info/
