WorksheetsQuiz 6 Teori Bahasa dan Otomata-2023-1Ok
Total questions: 25
Worksheet time: 25mins
Dalam Penerapan Ekspresi Reguler: Sebuah bahasa dinyatakan regular jika:.......
terdapat finite state automata (FSA) yang dapat menerimanya
tidak terdapat finite state automata (FSA) yang dapat menerimanya
sebagian terdapat finite state automata (FSA) yang dapat menerimanya
terdapat finite state automata (FSA) yang tidak dapat menerimanya
finite state automata (FSA) yang dapat menerimanya dapat digunakan secara umum
Dalam penerapan Ekspresi Reguler: Ekspresi regular memberikan suatu pola atau template untuk ..............
untai/string dari suatu bahasa.
ragam dari suatu bahasa.
kumpulan dari suatu bahasa.
pengembangan dari suatu bahasa.
penelusuran dari suatu bahasa.
Dalam Penerapan Ekspresi Reguler: Untai yang menyusun suatu bahasa regular akan cocok dengan:
pola bahasa itu
gaya bahasa itu
untai bahasa itu
jenis bahasa itu
tingkat kerumitan bahasa itu
Perhatikan Gambar di atas, gambar tersebut merupakan contoh Penerapan Ekspresi Reguler untuk:
FSA menerima bilangan integer tak bertanda
FSA menerima bilangan bulat
FSA menerima bilangan integer positif
FSA menerima bilangan integer negatif
FSA menerima bilangan desimal dan alfa numerik
Dalam suatu kompilator, Ekspresi regular bisa diaplikasikan untuk melakukan analisis leksikal, yaitu mengidentifikasikan unit-unit leksikal yg dikenal dalam program. Unit leksikal ini biasa disebut
token
untai
deret
himpunan
makna
Manakah berikut ini yang bukan merupakan penulisan Notasi Ekspresi Reguler?
(*) yaitu karakter asterisk, berarti bisa tidak muncul, bisa juga muncul berhingga kali (0-n).
(˖) pada posisi superscript / diatas berarti minimal muncul satu kali (1-n).
(+) atau (ᴗ) berarti union/atau.
(.) titik, berarti konkatenasi. Biasanya titik bisa dihilangkan. Misalnya: ab bermakna sama seperti a.b.
(%) Prosen, berarti berarti pembagian modulus. Misalnya 5%2 bermakna 5 dibagi dengan 2 hasilnya 2 dengan sisa hasil pembagian 1
Perhatikan gambar di atas, gambar tersebut merupakan"
Hubungan antara NFA, DFA dan Ekspresi Regular
Diagram Proses NFA, DFA dan Ekspresi Regular
Cara Kerja NFA, DFA dan Ekspresi Regular
Hubungan antara NFA, DFA dan Ekspresi Regular
Penggabungan antara NFA, DFA dan Ekspresi Regular
Sebuah otomata berhingga menspesifikasikan sebuah bahasa sebagai himpunan semua untai yang menggerakkannya dari state awal ke
salah satu dari state yang diterimanya (himpunan state akhir).
state awal
proses awal
proses tengah
proses akhir
Dalam batasan Aturan Produksi untuk Bahasa Regular (lanjutan):
•α atau β bisa berupa simbol terminal atau non-terminal/variabel.
•Simbol variabel/non-terminal adalah simbol yang masih bisa diturunkan. Biasanya dinyatakan dengan:
huruf besar, misal: A, B, C.
huruf kecil, misal: a, b, c.
gabungan huruf besar dan kecil
angka desimal
simbol abjad yunani seperti: α atau β
•Suatu tata bahasa (grammar) didefinisikan dengan 4 tupel (G={V, T, P, S}) dimana:
→V=
himpunan simbol variabel/non terminal.
himpunan simbol terminal.
kumpulan aturan produksi
simbol awal
konstanra
•Misalnya kita tentukan simbol awal adalah S, kita identikan simbol S dengan state awal q₀. dari q₀ mendapat input a menjadi q₁.
•E Kita identikkan dengan q₁
•Bisa kita tuliskan sebagai aturan produksi:
S→aE
S→AE
S→ae
S→q1q2
S→q2q1
Perhatikan gambar di atas:
•Bisa kita lihat hasil pada gambar tersebut akan berkorelasi S dengan q₀, B dengan q₁, dan C dengan q₂.
•Kita lihat S→b, maka kita buat state akhir adalah:
q₃.
q1.
q2.
q0
q2 dan q3
•Jika kita identikan q₂ sebagai A dan q₃ sebagai B.
–dari q₂ mendapat input a tetap ke q₂,
–dari q₃ mendapat input b tetap ke q₃, bisa kita tuliskan:
A → aA
B → bB
A → AA
B → BB
A → aa
B → bb
A → aA1
B → bB2
A → aA2
B → bB1
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
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
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
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
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
Penyederhanaan CFG: Untuk melakukan pembatasan sehingga tidak menghasilkan pohon penurunan yg memiliki kerumitan yang tidak perlu atau.........
aturan produksi yang tidak berarti
aturan produksi yang berarti
aturan produksi yang akurat
aturan produksi yang tidak rumit
aturan produksi yang tidak sederhana
Aturan Produksi berikut:
nS → A
A → B
B → C
C → D
D → a | A
Memiliki kelemahan yaitu terlalu panjang jalannya padahal berujung pada S → a, D → A juga menyebabkan.....
kerumitan.
kemudahan
kepanjangan
nilai kosong
nilai mutlak
Produksi Useless :
Produksi yang memuat simbol variabel yang tidak memiliki penurunan yang akan menghasilkan terminal-terminal seluruhnya, produksi ini tidak berguna karena bila diturunkan:
tidak akan pernah selesai (masih ada simbol variabel yang tersisa)
akan selesai ( walaupun masih ada simbol variabel yang tersisa)
tidak mudahi (karena masih ada simbol variabel yang tersisa)
mudah untuk diselesaikan (walaupun masih ada simbol variabel yang tersisa)
pasti akan pernah selesai (walaupun masih ada simbol variabel yang tersisa)
Prinsip penyederhanaan adalah: Prinsipnya setiap kali melakukan penyederhanan kita periksa lagi aturan produksi yang tersisa, apakah semua produksi yang useless sudah.........
dihilangkan.
diturunkan.
diproses.
dikembalikan.
dimutasi.
