NEW
Font size
WorksheetsQuiz 8 Teori Bahasa dan Otomata 2020-2
Total questions: 10
Worksheet time: 10mins
Dalam Hirarki Chomsky Bahasa Reguler/Type 3 mesin Otomata : Finite State Otomata (FSA) memiliki batasan aturan produksi:
ß memiliki maksimal sebuah simbol variabel yang bisa ada terletak di posisi paling kanan
α memiliki maksimal sebuah simbol variabel yang bisa ada terletak di posisi paling kanan
ß memiliki maksimal sebuah simbol variabel yang bisa ada terletak di posisi paling kiri
α memiliki maksimal sebuah simbol variabel yang bisa ada terletak di posisi paling kiri
Tidak ada batasan
Dalam Hirarki Chomsky Bahasa Untresticted/Phase Structural/Natural Language/Type 0 mesin Otomata : mesin turing memiliki batasan aturan produksi:
ß memiliki maksimal sebuah simbol variabel yang bisa ada terletak di posisi paling kanan
α memiliki maksimal sebuah simbol variabel yang bisa ada terletak di posisi paling kanan
ß memiliki maksimal sebuah simbol variabel yang bisa ada terletak di posisi paling kiri
α memiliki maksimal sebuah simbol variabel yang bisa ada terletak di posisi paling kiri
Tidak ada batasan
Dalam Tata Bahasa Bebas Konteks (Context Free Grammar/CFG)
Bahasa bebas konteks menjadi dasar dalam pembentukan suatu parser/proses analisis sintaksis.
Bagian sintaks dalam suatu kompilator kebanyakan didefinisikan dalam .....
tata bahasa bebas konteks
tata bahasa tergantung konteks
tata bahasa tanpa konteks
tata bahasa terikat konteks
tata bahasa mengikuti konteks
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 maka:
batasannya hanyalah ruas kiri (a) adalah sebuah simbol variabel
batasannya hanyalah ruas kiri (b) adalah sebuah simbol variabel
batasannya hanyalah ruas kiri (a) adalah beberapa simbol variabel
batasannya hanyalah ruas kanan(b) adalah sebuah simbol variabel
tidak ada batasan
Suatu graph terhubung tidak sirkuler, yang memiliki satu simpul (node) /vertex yang disebut akar (root) dan dari root memiliki lintasan ke setiap simpul disebut:
pohon (tree)
graph
matrik
vertex
akar
•Pohon penurunan (derivation tree/parse tree) berguna untuk menggambarkan bagaimana memperoleh suatu string (untai) dengan cara menurunkan simbol-simbol terminal. Setiap simbol variabel akan diturunkan menjadi ....
terminal, sampai tidak ada yang belum tergantikan.
daun, sampai tidak ada yang belum tergantikan.
pohonl, sampai tidak ada yang belum tergantikan.
graph, sampai tidak ada yang belum tergantikan.
vertex, sampai tidak ada yang belum tergantikan.
Misalnya terdapat tata bahasa bebas konteks dengan aturan produksi (simbol awal S, selanjutnya digunakan sebagai simbol awal untuk tata bahasa bebas konteks adalah S).
S –> AB
A –> aA | a
B –> bB | b
Manakah pernyataan berikut yang salah?
Akan kita gambarkan pohon penurunan untuk memperoleh untai : ‘aabbb’.
Pada pohon tersebut simbol awal akan menjadi akar (root).
Setiap kali penurunan dipilih aturan produksi yang menuju ke solusi.
Simbol-simbol variabel akan menjadi simpul-simpul yang mempunyai induk
Simpul-simpul yang tidak mempunyai anak akan menjadi simbol terminal.
Perhatikan gambar di atas, gambar di atas merupakan Pohon Penurunan untuk untai .....
‘aabbb’
‘aaabb’
'BABA'
‘ababa’
'AABB'
Ambiguitas/ke-dwi artian terjadi bila terdapat lebih dari satu pohon penurunan yang ......
berbeda untuk memperoleh suatu untai.
sama untuk memperoleh suatu untai.
bertingkat untuk memperoleh suatu untai.
setingkat untuk memperoleh suatu untai.
berproses untuk memperoleh suatu untai.
Ambiguitas dapat menimbulkan masalah pada bahasa-bahasa tertentu, baik 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
jelas
tunggal
pasti
tepat
