NEW
Font size
WorksheetsTBO_kelas Genap 2021/2022
Total questions: 51
Worksheet time: 26mins
Alphabet adalah simbol-simbol yang kosong dan tidak terbatas. Apakah pernyataan tersebut benar?
Benar
Salah
Berapakah panjang string dari abbaba ?
|w| = 6
|w| = 5
|w| = 4
|w| = 3
Suatu entitas abstrak yang tidak dapat didefinisikan secara formal disebut dengan?
mesin
Simbol
robot
graph
Berdasarkan gambar diatas, ada berapakah jumlah state dalam suatu graph tersebut?
1
3
5
8
Bahasa tingkat tinggi dikatakan sebagai bahasa yang sulit dikarenakan mesin hanya mengenali instruksi biner yaitu 0 & 1.
True
false
Berdasarkan gambar di bawah pilihlah pernyataan berikut yang benar
inputan a,d,a dan a,d,u diterima karena mencapai final state.
Inputan a,d,a dan a,d,u ditolak karena hanya ada 1 kondisi yang seharusnya diterima.
Inputan a,d,d diterima karena mencapai final state.
Jawaban A dan C benar
Gambar diatas menunjukan mesin yang cacat, karena terdapat 2 final state.
true
falsa
Deretan berhingga dari simbol-simbol disebut string. Untuk W = “atera” dan C = “ ” memiliki panjang string sebesar...
w = |4| & C=|0|
w = |4| & C=|0|
W = |5| & C=|0|
w = |5| & C=|0|
Input pada mesin automata dianggap sebagai bahasa yang harus dikenali oleh mesin.
True
False
Pada aturan produksi E→T | T+E dibaca…
E menuju T dan T ditambahkan E
E menghasilkan T atau E menghasilkan T+E
E merupakan T atau E berubah menjag T+E
E menuju T atau T+E sama dengan E
Pada hirarki chomsky yang termasuk contoh tipe Unresticted Grammar adalah…
S → AcaB
Bc→aaB
CB→DB
Semua benar
Dari gambar di atas, bila state q0 menerima inputan ‘a’ dan dapat berpindah ke state q0 atau q1, yang secara formal dinyatakan sebagai :
aδ (q0, a) = { q0 , q1 }
a. δ (q1, a) = { q0 , q1 }
δ (q0, q1) = { q0 , q1 }
a. δ (q0, q1) = { q0 , a}
Kumpulan dari himpunan variabel, simbol-simbol terminal, simbol awal, yang dibatasi oleh aturan-aturan produksi adalah definisi dari ...
Otomata Hingga
CFG
Tata Bahasa (grammar)
Reguler Grammar
Berdasarkan gambar di atas, yang manakah yang merupakan symbol input…
q0,q1,q2,q3
a,b,a,b
tanda panah
lingkaran ganda
Input manakah yang menyebabkan mesin tersebut menghasilkan output akhir genap?
10101
01100
11100
00010
Biasanya fungsi transisi disajikan dalam bentuk?
tabel
Diagram
Gambar
ANgka
Aturan produksi sama dengan tipe 0 namun dibatasi dengan aturan | α |≤|B| merupakan grammar tipe?
UG
CSG
CFG
RG
Pada FSA termasuk mekanisme kerja dapat diterapkan pada?
Leksikal
Mesin Bubut
Mesin Turing
Semua Benar
Berikut ini perbedaan antara Deterministic FA dan Non-Deterministic FA adalah …
DFA yaitu multi transisi dari 1 state ke state yang lain sedangkan NFA yaitu transisi dari 2 state ke state yang lain
NFA boleh terdapat transisi kosong sedangkan DFA tidak ada transisi kosong
DFA String di terima jika berakhir di final state sedangkan NFA String diterima jika setidaknya 1 dari semua kemungkinan transisi berakhir pada sebuah final state
Semua Salah
Perhatikan tabel di bawah ini 𝜹 a b q0 q0 q1 q1 q1 q2 q2 q1 q2
Manakah fungsi transisi berdasarkan tabel tersebut yang benar…
(q0,a)=q0
(q0,a)=q1
(q0,a)=q2
(q0,a)=q3
Jika pada gambar kita inputkan string ‘abb’, maka pernyataan yang benar adalah..
δ (q0,abb) = δ(q0,bb) = δ(q1,b)=q2
δ (q0,abb) = δ(q1,bb) = δ(q1,b)=q2
a. δ (q0,abb) = δ(q0,bb) = δ(q1,b)=q3
a. δ (q0,abb) = δ(q0,bb) = δ(q1,b)=q4
Perhatikan pernyataan di bawah ini 1) Setiap Finite Automata memiliki keadaan dan transisi yang tidak terbatas. 2) Transisi dari satu keadaan ke keadaan lainnya dapat bersifat deterministik atau non- deterministik. 3) Setiap Finite Automata tidak selalu memiliki keadaan awal. 4) Finite Automata dapat memiliki lebih dari satu keadaan akhir.
Manakah karakteristik dari finite state yang benar di bawah ini?
Jika pernyataan 1,2, dan 3 benar.
Jika pernyataan 1 dan 3 benar.
Jika pernyataan 2 dan 4 benar.
Jika pernyataan 4 saja yang benar.
Finite Automata tidak selalu dalam kondisi yang disebut state awal (initial state) pada saat Finite Automata mulai membaca tape
True
False
Perhatikan pernyataan dibawah ini:
1) AcAB → S
2) CD → F
3) Sab → ba
4) Ab → DeF
Dari ke empat pernyataan diatas, manakah yang memenuhi Grammar tipe-1 (CGS)?
Pernyataan 1,2, dan 3 benar
Pernyataan 1 dan 3 benar
Pernyataan 2 dan 4 benar
Pernyataan 4 saja yang benar.
Perhatikan pernyataan di bawah ini
1) T → aaB
2) a → aaa
3) A → aA
4) T → aaC
5) c → aCb
6) b → Baa
Dari ke enam pernyataan diatas, manakah yang memenuhi Tata bahasa tipe-3 (Regular Grammar)?
1, 2, dan 3
2,5 dan 6
1,3 dan 4
3,4, dan 5
1,3, dan 6
Perhatikan pernyataan di bawah ini 1) Setiap Finite Automata memiliki keadaan dan transisi yang tidak terbatas. 2) Transisi dari satu keadaan ke keadaan lainnya dapat bersifat deterministik atau non- deterministik. 3) Setiap Finite Automata tidak selalu memiliki keadaan awal. 4) Finite Automata dapat memiliki lebih dari satu keadaan akhir.
Manakah karakteristik dari finite state yang benar di bawah ini?
Jika pernyataan 1,2, dan 3 benar.
Jika pernyataan 1 dan 3 benar
Jika pernyataan 2 dan 4 benar.
Jika pernyataan 4 saja yang benar.
Apakah syarat dua buah DFA dikatakan equivalen?
Keduanya dapat menerima bahasa yang berbeda
Keduanya tidak dapat menerima bahasa
Keduanya dapat menerima bahasa yang sama
Keduanya dapat menerima bahasa
Dua buah DFA tidak dapat dikatakan equivalen
Pada Non Deterministic Finite State Automata, perubahan state dapat terjadi secara spontan tanpa input (transisi kosong).
True
False
Yang menjadi pembeda antara Deterministic Dan Non Deterministic FA adalah?
Ada atau tidaknya transisi epsilon
Fully defined
Ambigu atau tidaknya dalam menentukan next stage
A,B, dan C
Tata Bahasa Tipe-2 (Context Free Grammar) menghasilkan bahasa yang dikenali oleh Non-Deterministic Push Down Automata.
True
False
Jumlah simbol pada ruas sebelah kiri harus lebih kecil atau sama dengan jumlah simbol pada ruas kanan merupakan ciri khusus dari aturan produksi bahasa …..
reguler
Bebas Konteks
Context Sensitive
unresticte/Natural Language
Berikut yang bukan merupakan sifat NDFA
NDFA memiliki kemampuan untuk berada di lebih dari satu state pada saat yang bersamaan
NDFA tidak memiliki kemampuan untuk berada di lebih dari satu state pada saat yang bersamaan
NDFA selalu menerima bahasa yang diterima oleh DFA
NDFA lebih ringkas dibanding DFA
NDFA menerima secara tepat bahasa reguler
Manakah pernyataan yang benar…
Umumnya symbol terminal disymbolkan dengan huruf kecil (a,b,c, dsb)
T → a T menghasilkan a E menghasilkan A
Sentensial adalah obbjek yang tersusun atas string terminal atau simbol-simbol non terminal atau campuran keduanya.
Pengertian terminal berasal dari kata terminate (berlanjutan).
Teori mengenai Finite State Automata adalah suatu tool yang berguna untuk ...
Merancang sistem
Mengontrol sistem
Keamanan sistem
Mengimplementasikan system
Otomata adalah sebuah model dari suatu sistem, sedangkan teori bahasa adalah kaidah pembentukan sebuah bahasa pemrograman.
True
False
Sistem elevator dan pengaturan lampu lalu lintas bisa dimodelkan dengan Finite State Automaton (FSA)
True
False
Manakah pernyataan dibawah ini yang benar mengenai NFA …
Kemungkinan transisinya ke lebih dari satu state
Dari suatu state hanya ada tepat satu state berikutnya untuk setiap simbol masukan yang diterima.
Perubahan state dapat terjadi secara spontan tanpa input
Pilihan a dan c benar
Dibawah ini yang merupakaan pernyataan benar tentang simulasi NFA oleh DFA...
Cara simulasi NFA oleh DFA adalah dengan membuat state DFA berkorespondensi dengan set State
DFA yang dibentuk mencatat semua state yang mungkin pada NFA setelah membaca output tertentu
DFA yang dibentuk mencatat semua mesin yang mungkin pada NFA setelah membaca output tertentu
Cara simulasi NFA dan DFA adalah dengan membuat state DFA berkorespondasi dengan mesin Turing
Dari sebuah mesin Non-Deterministik Finite Automata dapat dibuat mesin DFA yang ekivalen. Ekivalen adalah...
Mampu menerima bahasa yang Sama
Mampu menerima bahasa yang Berbeda
Mampu menolak input
Mampu menolak Output
Finite State Automata/Otomata berhingga state (FSA), bukan suatu mesin fisik, tetapi suatu model matematika dari suatu sistem yang menerima input dan output
BErulang
Lurus
Diskrit
Kontiniu
Tentukan kombinasi string yang benar untuk mencapai final
(q0, a) = q0, (q0, a) = q0, (q0, b) = q2, (q2, b) =q4
(q0, a) = q0, (q0, a) = q0, (q0, b) = q2, (q2, b) =q2
(q0, a) = q0, (q0, a) = q0, (q0, c) = q0, (q0, b) =q0
(q0, a) = q0, (q0, a) = q0, (q0, b) = q2, (q2, c) =q2
Perhatikan keterangan dibawah ini
1) Initial state ditandai dengan busur tanpa asal state
2) Lingkaran menyatakan state
3) Label pada lingkaran adalah nama state
4) Busur menyatakan transisi/ arah perpindahan state
5) Label pada busur adalah symbol input
6) Lingkaran ganda menyatakan final
Pilihlah pernyataan yang benar
1 dan 2
1,2,3, dan 4
5 dan 6
Semua Benar
Tupel FSA yang menyatakan fungsi transisi adalah….
Q
S
∑
δ
Berikut merupakan simbol-simbol terminal, kecuali ......
a
b. x, –, ++
expr, stmt
IF, Then,Else
Kumpulan dari kumpulan himpunan variabel, simbol-simbol terminal, simbol awal yang dibatasi oleh aturan produksi, merupakan definisi dari …
String
Tata Bahasa
Kalimat
Automata
4 tingkatan tata Bahasa menurut Chomsky adalah (secara berurutan)
Unrestricted Grammar, Context Sensitve Grammar, Context Free Grammar, dan Reguler Grammar
Context Sensitve Grammar, Context Free Grammar, Unrestricted Grammar, dan Reguler Grammar.
Context Sensitve Grammar, Unrestricted Grammar, Reguler Grammar, dan Context Free Grammar
Reguler Grammar, Unrestricted Grammar, Context Sensitve Grammar dan Context Free Grammar
Berikut merupakan Context Free Grammar, kecuali …
Q = {S→Sa|Ba, B→Ca, C→a}
Q = {S→aBC, B→bC, C→c}
Q = {S→BaC, aC→Cd|cc,B→b}
Q = {S→xY, Y→Zy|y, Z→a}
Manakah berikut ini yang bukan merupakan arti dari bentuk-bentuk pada FSA ?
Busur menyatakan transisi yaitu perpindahan kedudukan/state
Lingkaran menyatakan state/kedudukan
Label pada lingkaran adalah nama lingkaran
Lingkaran didahului sebuah busur tanpa label menyatakan state awal
Secara formal FSA dinyatakan oleh 5 tupel. M = (Q, å, δ, S, F ), manakah arti simbol-simbol berikut yang salah?
Q = himpunan state / kedudukan
å = himpunan simbol input / masukkan / abjad
S = Stop/state akhr / kedudukan akhir (final state)
F = himpunan state akhir.
Berdasarkan gambar tersebut manakah pernyataan dibawah ini yang benar
1101 ditolak
0101 ditolak
0001 diterima
1110 diterima
Jika ingin membuat mesin DFA dari mesin NFA langka pertama yang kita lakukan adalah...
Membuat Tabel transisi
membuat tabel Logika Kebenaran
Membuat Mesin Turing
Membuat Himpunan State
