1.
Mesin
otomata membuat keputusan menerima string input bila mencapai state akhir.
State akhir dinyatakan dengan .........
a)
Lingkaran
Tunggal c) Panah
Tunggal
b)
Lingkaran
Ganda d) Panah Ganda
2.
Kumpulan dari himpunan variabel, simbol-simbol terminal,
simbol awal, yang dibatasi oleh aturan-aturan produksi adalah definisi dari
..........
a)
Otomata
Hingga c)
CFG
b)
Tata Bahasa
(Grammar) d)
Reguler Grammar
3.
Matematika
dasar yang mendasari teori otomata, komputasi dan bahasa formal terutama adalah
a)
Teori
Himpunan c)
Graph
b)
Semua benar d)
Logika Formal
4.
Diketahui x = bahasa, y = automata, maka operasi concate
(xy) menghasilkan ........
a)
Bahasaautomata c) Bahasa
b)
Bahasautomata d)
automata
5.
Diketahui x = bahasa, y = automata, maka operasi concate
[x(tail(y))] menghasilkan ......
a)
Bahasautomata c)
automata
b)
Bahasaautomata d)
bahasaa
6.
Mesin abstrak yang dapat mengenali, menerima atau
membangkitkan sebuah kalimat dalam bahasa tertentu disebut ..........
a)
Kompilator c)
Grammar
b)
Derivasi d)
Automata
7.
Proses
pembentukan sebuah kalimat disebut...
a)
Kompilator c) derivasi
b)
Automata d)
grammar
8.
Berikut
merupakan simbol-simbol terminal, kecuali ......
a)
a,
b, c c)
expr, stmt
b)
+,
–, x d)
IF, THEN, ELSE
9.
Deretan hingga simbol-simbol terminal disebut .....
a)
Token c)
grammar
b)
Kalimat d)
Bahasa
10.
Operator
yang berfungsi untuk memilih satu diantara dua buah string adalah ......
a)
Head c)
tail
b)
Alternation d) concatenation
11.
Berikut merupakan Context Free Grammar, kecuali
a)
Q = {S→Sa|Ba, B→Ca, C→a}
b)
Q = {S→aBC, B→bC, C→c}
c) Q = {S→BaC, aC→Cd|cc,B→b}
d)
Q = {S→xY, Y→Zy|y, Z→a}
12.
Pushdown Automata merupakan mesin pengenal untuk kelas
bahasa ........
a)
RG c)
UG
b)
CSG d)CFG
13.
Automata Hingga merupakan mesin pengenal untuk kelas
bahasa ........
a)
RG c) CFG
b)
CSG d)
UG
14.
Berikut
himpunan string yang dapat dibentuk dari Ekspresi Regular (0|1)*00, kecuali
.....
a)
010 c)
000
b)
100 d)
00100
15.
Kedudukan
teori bahasa dan automata pada bidang komputasi berperan pada bagian...
a)
Model dan gagasan mendasar c)Software
b)
Teknik
rekayasa d)Hardware
16.
Secara
teoritis ilmu komputer diawali dari sejumlah disiplin ilmu: Biologi, Elektro,
matematika. Ahli bahasa juga berperan dengan menyelidiki...........
a)
Neural
network c)
Logika
b)
Switching
circuit d) Natural language
17.
Finite State Automata dan Ekspresi Reguler awalnya
dikembangkan berdasar pemikiran...
a)
Pattern
matching c) Neural network
& Switching circuit
b)
Logika d)
Natural Language
18.
Finite State Automata dan Ekspresi Reguler merupakan Tool
yang sangat berguna dalam perancangan............pada kompilator.
a)
Semantic
Analyzer c) Lexical
analyzer
b)
Syntax
Analyzer d)
semua salah
19.
Finite State Automata dan Ekspresi Reguler dipakai pula
dalam.....
a)
Text
Editor c)
File searching
b)
Pattern
Matching d) Semua Benar
20.
Spesifikasi
dari sebuah bahasa pemrograman meliputi hal-hal berikut, kecuali....
a) Gaya
b)
Himpunan program yang benar secara sintaktik
c)
'Makna'
dari program tersebut
d)
Himpunan
simbol-simbol
21.
Tata
bahasa bebas konteks dan Push-down Automata telah banyak memberikan bantuan
pada spesifikasi dari bahasa pemrograman dan perancangan....
a)
Scanner c)
semantic analyser
b)
Lexic d)
Parser
22.
Sebuah
bahasa formal adalah suatu abstraksi terdiri dari himpunan simbol-simbol dan aturan-aturan
yang mana simbol-simbol tersebut bisa dikombinasikan kedalam entitas yang
disebut.....
a)
Kata c) Kalimat
b)
Grammar d)
Otomata
23.
Otomata
merupakan suatu sistem yang terdiri atas sejumlah berhingga ............ yang
menyatakan informasi mengenai input yang lalu, dan dapat pula dianggap sebagai
memori mesin.
a)
Ruas
(Edge) c)
Acceptance State
b)
Stata (State) d)
Token
24.
Perhatikan pushdown automata
(PDA) P = [{q0, q1}, {a, b}, { a, b, Z}, q0, Z, F, {q0}] dengan F sebagai
berikut:
F(q0, a, Z) = (q1, aZ)
F(q1, a, a ) = (q1, aa )
F(q1, b, a ) = (q1, )
F(q1, , Z) = (q0, Z)
Konfigurasi yang benar
setelah konfigurasi awal untuk string/kata/kalimat ab jika diinputkan pada pushdown
automata P adalah:
a) (q0, ab, Z) |- (q1, b, Z) c)
(q0, ab, Z) |- (q1, b, a)
b) (q0, ab, Z) |- (q1, b, aZ) d) (q0, ab, Z) |- (q1, b, Za)
25.
Konfigurasi yang benar setelah konfigurasi (q1, b, aZ) pada PDA P
pada soal no.24 adalah ........
a)
(q1, ε, aZ) c)
(q1, ε, ε)
b)
(q1, ε, Z) d) (q1, ε, bZ)
26.
Urutan konfigurasi yang benar untuk string aabb jika diinputkan ke mesin pushdown
automata P pada soal no.24 adalah .....
a)
(q0, aabb, Z) |- (q1,
abb, aZ) |- (q1, bb, aaZ) |- (q1, b, aZ) |- (q1, ε, Z) |- (q0, ε, Z)
b)
(q0, aabb, Z) |- (q1, abb, aZ) |- (q1, bb, aZ) |- (q1, bb, Z) |- (q0, bb, Z)
c)
(q0, aabb, Z) |- (q1, abb, aZ) |- (q1, bb, aZ) |- (q1, b, ε)
d)
(q0, aabb, Z) |- (q1, abb, Z) |- (q1, bb, a) |- (q1, b, ε)
27.
Kelebihan mesin Turing dibandingkan Push Down Automata dan
Automata Hingga adalah pada manajemen .....
a)
Memori c) Final State
b) State-State d)
Tata Bahasa
28.
Mesin Turing M = [{q1,q2},{a,b},{a,b,b},δ, S={q1},F={q2}, b]
dengan fungsi transisi :
δ(q1,a) = (q1, a, R)
δ(q1,b) = (q1, a, R)
δ(q1,b) = (q2, b , L)
maka string 'abbaa' akan .....
a)
no response c)
halt
b)
ditolak d)
diterima
29.
Push Down Automata yang menerima string input jika kondisi stack
kosong disebut ....
a)
PDA final state c)
PDA deterministik
b)
PDA non-deterministik d)
PDA Null stack
30. Linier-Bounded Automata adalah Mesin pengenal untuk Grammar .......
a)
RG c)
UG
b)
CFG d) CSG
31.
Yang dimaksud dengan BootStrap, adalah
a) Bagaimana
orang mengerti bahasa mesin
b) Penggunaan bahasa tingkat
tinggi
c)
Untuk
membangun sesuatu yang besar dibangun dulu bagian intinya
d)
Untuk menghidupkan computer
32.
Noam Chomsky melakukan penggolongan tingkatan dalam
bahasa, dikenal dengan istilah
a) BNF c) Tata bahasa
b)
Grammar d)
Chomsky Hierarky
33.
Menurut
Chomsky terdapat 4 penggolongan dalam aturan produksi, yang termasuk pada
kategori Context Free Grammar: Ruas kiri haruslah tepat satu simbol variable,
adalah
a) Tipe 2 c)
Tipe 0
b)
Tipe
1 d)
Tipe 3
34. fungsi dari ................... adalah untuk menentukan makna dari
serangkaian instruksi yang terdapat dalam program sumber.
a)
Analisa
Semantik c)
Analisa Lexical
b) Analisa Syntax d)
Code optimizer
35. Pada analisa semantik akan dilakukan pemeriksaan sebagai berikut
kecuali.....
a)
Apakah
Token-token sudah sesuai kemunculannya
b)
Apakah variabel-variabel bertipe sama
c)
Apakah operand memiliki nilai
d)
Apakah variabel-variabel telah didefinisikan
36. Fungsi dari intermediate code (kode antara) adalah sebagai berikut,
kecuali..........
a)
Memperkecil usaha dalam membangun kompilator
b)
Proses optimasi lebih mudah
c)
Program internal jadi mudah dimengerti
d)
Mengurangi
kesalahan lexical
37.
Intermediate code dapat dinyatakan dalam bentuk N-tuple dan
Notasi.............
a)
Prefix c)
Postfix
b)
Infix d)
Prefix-Sufix
38. Notasi Postfix dari statement (a+b)*(c+d) adalah.........
a)
*+ab+cd c)
ab+cd+*
b)
ab+*cd+ d)
*a+bc+d
39. Notasi Quadrupel untuk statement A:=D*C+B/E adalah.....
a)
(*,D,C,T1);(/,B,E,T2);(+,T1,T1,A)
b)
(*,D,C,T1);(/,B,E,T2);(+,T1,T2,A)
c)
(*,D,C,T2);(/,B,E,T2);(+,T1,T2,A)
d)
(*,D,C,T1);(/,B,E,T1);(+,T1,T2,A)
40.
Translator yang Source code
nya adalah bahasa tingkat tinggi, object
code adalah bahasa mesin atau bahasa assembly. Source code dan data
diproses berbeda, disebut dengan....
a)
Assembler c)
Interpreter
b)
Compiler d) Decoder
41.
Yang dimaksud dengan Diagram Syntax, pada teknik
Kompilasi adalah
a) Digunakan
untuk mendapatkan token, mempermudah melakukan analisis lexical
b) Alat bantu (tools) dalam pembuatan parser/
analisis sintaksis
c) Digunakan
untuk mendapatkan token, mempermudah melakukan analisis syntax
d)
Simbol terminal
42.
Dua teknik Top Down Parsing adalah :
a)
Rekursi kiri dan ambiguous c) Brute-Force dan tanpa back-up
b)
Brute-Force dan ambiguous d)
Ambiguous
dan tanpa back-up
43.
Analisa relasi presedens adalah metoda parsing yang
termasuk teknik parsing :
a)
Tanpa back-up c)
Top-Down
b) Brute-force d) Bottom-up
44. Sebuah kalimat yang mempunyai lebih dari satu pohon parsing disebut :
a)
Ambiguous c) Predictive
b)
Left recursive d) Right recursive
45. Tahapan dalam kompilasi yang bertujuan untuk
menghasilkan kode program yang berukuran lebih kecil dan lebih cepat
eksekusinya.
a) Tahap
code optimizer c) Tahap Sintesa
b) Tahap code generator d)
Tahap Analisa
46. Optimasi yang dilakukan hanya pada suatu blok dari
source code disebut........
a) Optimasi serial c)
Optimasi Paralel
b) Optimasi Global d)
Optimasi lokal
47. Diketahui Ekspresi Reguler :ab*cc maka string yang
dibangkitkan adalah sebagai berikut kecuali...
a) acc c)
abcbcc
b) abcc d)
abbcc
48. Diketahui Ekspresi Reguler :(a+b)* maka string yang
dibangkitkan adalah sebagai berikut kecuali...
a) aabbababa c)
aaabbsbbbabab
b) bbabbabba d)
abbabbabbabba
49. Ekspresi Reguler yang membangkitkan string yang
memuat minimal dua nol berurutan ('00') adalah ..........
a) (01)*00(01)* c)
(0+1)00(0+1)
b) 00+00+00 d)
(0+1)*00(0+1)*
50. Ekspresi Reguler yang membangkitkan string yang
berakhiran dua nol berurutan ('00') adalah ..........
a)
(0+1)*00 c)
(0+1)00*
b)
(0+1)00 d)
(0*+1)00
51.
Automata Stata Hingga dengan output disebut......
a)
Transducer c) Transmitter
b)
Translator d)
Accepter
52.
Automata Stata Hingga yang hanya menerima atau menolak
input disebut.......
a)
Transducer c)
transmitter
b)
Translator d)
Accepter
53.
Pada Automata hingga non-deterministik terdapat transisi
hampa yang artinya.....
a) diperbolehkan merubah state tanpa membaca
input.
b)
Semua input masuk transisi hampa
c)
Transisi yang menuju final state
d)
semua salah
54.
himpunan stata-state yang dapat dicapai dari suatu state
tanpa membaca input disebut....
a)
state space c)
Initial state
b)
final state d)
epsilon-closure
55.
Untuk mendapatkan Automata hingga deterministik (AHD)
dari Automata hingga non-deterministik dengan transisi hampa (AHN
epsilon-closure), maka harus diubah dahulu menjadi..
a)
AHD dengan transisi hampa c)
AHN
b)
Regular Grammar d)
Ekspresi Reguler
56.
Diketahui Ekspresi reguler : a*+b* maka salah satu string
yang dibangkitkan adalah...
a)
aab c)
abab...ab
b)
aa...ab....bb d) aa
57.
Diketahui Ekspresi reguler : a*d maka string paling
pendek (minimal) yang dibangkitkan adalah..
a)
a c) d
b)
ad d)
hampa
58.
Ciri utama dari mesin Mealy adalah..........
a)
Jumlah input lebih banyak dari jumlah output
b)
Jumlah input lebih sedikit dari jumlah output
c) Jumlah input sama dengan jumlah output
d)
semua salah
59.
Ciri utama dari mesin Moore adalah.......
a)
Jumlah input sama dengan dari jumlah output
b)
Jumlah input lebih sedikit dari jumlah output
c)
Jumlah input dan jumlah output bebas
d) Jumlah input lebih banyak dari jumlah
output
60.
Untuk memperoleh ekivalensi mesin Mealy dari suatu mesin
Moore cukup dengan....
a)
Menambah label output ke setiap transisi
b) Menambah label output ke setiap transisi
dan menghapus label output pd state
c)
Menghapus label output pd state
d)
semua salah
61.
Bila sebuah automata hingga mempunyai kemampuan 'memori'
yang terbatas, pada automata push-down didefinisikan sebuah tempat penyimpanan
yang tidak terbatas berupa.......
a)
Stata-stata c)
pita magnetik
b)
Stack d)
cakram
62.
Aturan pengisian pada tempat penyimpanan automata
push-down adalah....
a)
FIFO (first in first out) c)
FILO (first in last out)
b)
LIFO
(last in first out) d) LILO (last in last out)
63.
Pengambilan elemen dari tempat penyimpanan PDA
disebut....
a)
operasi infix c) operasi
prefix
b)
operasi push d)
operasi pop
64.
Pemasukan elemen kedalam memori PDA disebut....
a)
operasi infix c)
operasi prefix
b)
operasi
push d)
operasi pop
65.
Ekivalensi Final State PDA dan Null Stack PDA
artinya......
a)
Final State PDA sama dengan Null Stack PDA
b) Final State PDA dapat diubah menjadi Null
Stack PDA dan sebaliknya
c)
Final State PDA induk dari Null Stack PDA
d)
semua salah
66.
Pada mesin Turing 'memori' akan berupa suatu pita yang
pada dasarnya berupa......
a)
Stack c) array
b)
Card d)
disk
67.
Mesin Turing bisa dianalogikan seperti komputer
sederhana, dimana secara berurutan sejumlah state, pita, dan fungsi transisi
dianggap sebagai:
a)
secondary storage, memori, program
b)
program, memori, secondary storage
c)
memori , program, secondary storage
d) memori, secondary storage, program
68.
Untuk menyatakan secara formal konfigurasi Mesin Turing
pada suatu saat disebut....
a)
formal language c)
grammar
b)
universal formal form d)
deskripsi
seketika
69.
Sebuah mesin Turing bisa saja berjalan terus tanpa pernah
berhenti. Kondisi itu biasa disebut sebagai loop tak berhingga, dimana loop ini
menunjukkan bahwa input yang dimasukkan......
a)
Ditolak c)
diterima
b)
Halt d)
semua salah
70.
Sebuah hipotesa yang menyatakan bahwa setiap komputasi
yang bisa dilakukan secara mekanis bisa dilakukan juga oleh mesin Turing
disebut dengan.....
a)
Dalil De'Morgan c)
Dalil Lagrange
b)
Dalil Cauchy d) Dalil Turing
71.
Rangkaian kalimat yang terdiri dari simbol-simbol yang
mempunyai makna disebut..
a)
Bahasa c)
word
b)
input d)
string
72.
Sebuah tata bahasa bebas konteks dimana ruas kanan dari
setiap aturan produksinya terdiri dari dua simbol variabel atau satu simbol
terminal disebut
a)
Backus Naur Form c)
grammar
b)
Chomsky
normal form d) token
73.
Notasi yang digunakan untuk menyatakan secara formal
konfigurasi mesin pada suatu saat, digunakan untuk Push-Down Automata atau
mesin Turing disebut
a)
Notasi Sigma c) Notasi
Seketika
b)
Notasi Grammar d)
Notasi terminal
74.
Model matematika dari sebuah sistem dengan input dan
output diskrit, yang terdiri dari sejumlah berhingga state dan fungsi-fungsi
transisi yang menyajikan perubahan state disebut
a)
automata c)
Push-Down Automata
b)
Linier-Bounded Automata d) Finite
Automata
75.
Graph berarah yang menggambarkan sebuah finite automata
disebut
a)
Diagram
Transisi c) Diagram konteks
b)
Diagram Syntax d)
Diagram leksikal
76.
Merupakan generator bahasa yang mendefinisikan suatu
bahasa secara rekursif disebut
a)
syntax c)
token
b)
Grammar d)
Semantics
77.
Bahasa yang diterima oleh Finite Automata disebut...
a)
bahasa alamiah c) Ekspresi
reguler
b)
Grammar d)
salah semua
78.
Aturan yang berhubungan dengan variabel yang menyatakan
bagaimana menggenerate string-string dalam bahasa disebut
a)
Aturan Baku c)
aturan tertulis
b)
definisi seketika d) Produksi
79.
Simbol yang masih memiliki penurunan/masih bisa
diturunkan disebut
a)
variabel c) terminal
b)
Token d)
produksi
80.
Bentuk jamak dari besaran leksik adalah
a)
leksiks c)
leksikal
b)
leksim d)
salah semua
Kunci Jawaban
- B 26. A 51. A 76. B
- B 27. A 52. D 77. C
- B 28. D 53. A 78. D
- A 29. D 54. D 79. A
- D 30. D 55. C 80. B
- D 31. C 56. D
- C 32. D 57. C
- C 33. A 58. C
- B 34. A 59. D
- B 35. A 60. B
- C 36. D 61. B
- D 37. C 62. B
- A 38. C 63. D
- A 39.
B 64. B
- A 40.
B 65. B
- D 41.
B 66. C
- C 42.
C 67. D
- C 43.
D 68. D
- D 44.
A 69. A
- A 45.
A 70. D
- D 46.
D 71. A
- C 47.
C 72. B
- B 48.
C 73. C
- B 49.
D 74. D
- B 50.
A 75. A
