Scribd
Unggah
7 tayangan2 halaman

CFG dan Automata: Analisis dan Transformasi

Dokumen tersebut membahas beberapa topik terkait teori bahasa formal dan automata, yaitu: 1. Pohon penurunan untuk string CFG 2. Pengurangan aturan produksi bersamaan dengan menghilangkan produksi empty, unit, dan useless 3. Konversi bahasa bebas konteks ke bentuk normal Chomsky 4. Penerimaan string oleh push down automata

Diunggah oleh

Az Zikra Ismunandar
Hak Cipta
© All Rights Reserved
Kami menangani hak cipta konten dengan serius. Jika Anda merasa konten ini milik Anda, ajukan klaim di sini.
Format Tersedia
Unduh sebagai DOCX, PDF, TXT atau baca online di Scribd
7 tayangan2 halaman

CFG dan Automata: Analisis dan Transformasi

Dokumen tersebut membahas beberapa topik terkait teori bahasa formal dan automata, yaitu: 1. Pohon penurunan untuk string CFG 2. Pengurangan aturan produksi bersamaan dengan menghilangkan produksi empty, unit, dan useless 3. Konversi bahasa bebas konteks ke bentuk normal Chomsky 4. Penerimaan string oleh push down automata

Diunggah oleh

Az Zikra Ismunandar
Hak Cipta
© All Rights Reserved
Kami menangani hak cipta konten dengan serius. Jika Anda merasa konten ini milik Anda, ajukan klaim di sini.
Format Tersedia
Unduh sebagai DOCX, PDF, TXT atau baca online di Scribd

Nama: Zulfa Basmallah Agustyn

NIM: 20104053
Kelas: SE04B

1. Diketahui CFG dengan aturan produksi berikut


S→ABC
A→BC|a
B→AC|b
C→AB|c
Buat pohon penurunan untuk string “accaabbcb”

2. Ubahlah a.p (aturan produksi) berikut secara bersamaan dengan melakukan


penghilangan produksi dimulai dari empty, unit, useless :
a.p =
S→ a|bC|D
A→cd|AB
B→Ac|ε|ef
C→bD|ε|fg
D→abE
F→gh

3. Diketahui Bahasa bebas konteks (sudah tidak mengandung produksi useless,


unit dan ε)
S→ab|cd|aB|Cd|Ab|cD
A→BC|a
B→AC|b
C→AB|c
Ubahlah kedalam bentuk normal Chomsky !

4. Push down automata

1
Nama: Zulfa Basmallah Agustyn
NIM: 20104053
Kelas: SE04B

Apakah string “baab” diterima ?

Anda mungkin juga menyukai