u as automata

7/23/2019 u as Automata

1/9

1. Mesin otomata membuat keputusan menerima string input bila mencapai state akhir.State akhir dinyatakan dengan .........

a) Lingkaran Tunggal c) Panah Tunggalb) Lingkaran Ganda d) Panah Ganda

2. Kumpulan dari himpunan ariabel! simbol"simbol terminal! simbol a#al! yang dibatasioleh aturan"aturan produksi adalah de$inisi dari ..........a) %tomata &ingga c) '(Gb) Tata Bahasa (Grammar) d) eguler Grammar

*. Matematika dasar yang mendasari teori otomata! komputasi dan bahasa $ormalterutama adalah

a) Teori &impunan c) Graphb) Semua benar d) Logika (ormal

+. ,iketahui - bahasa! y automata! maka operasi concate /-y) menghasilkan ........

a) Bahasaautomata c) 0ahasab) 0ahasautomata d) automata

. ,iketahui - bahasa! y automata! maka operasi concate -/tail/y))3 menghasilkan ......a) 0ahasautomata c) automatab) 0ahasaautomata d) bahasaa

4. Mesin abstrak yang dapat mengenali! menerima atau membangkitkan sebuah kalimatdalam bahasa tertentu disebut ..........

a) Kompilator c) Grammar b) ,eriasi d) Automata

5. Proses pembentukan sebuah kalimat disebut...a) Kompilator c) derivasib) 6utomata d) grammar

7. 0erikut merupakan simbol"simbol terminal! kecuali ......a) a! b! c c) expr, stmtb) 8! 9! - d) :(! T&;

=. ,eretan hingga simbol"simbol terminal disebut .....a) Token c) grammar b) Kalimat d) 0ahasa

1>. %perator yang ber$ungsi untuk memilih satu diantara dua buah string adalah ......a) &ead c) tailb) Alternation d) concatenation

11. 0erikut merupakan 'onte-t (ree Grammar! kecualia) ? @SASaB0a! 0A'a! 'AaCb) ? @SAa0'! 0Ab'! 'AcCc) ! "S#Ba$, a$#$d%cc,B#b&


2/9

d) ? @SA-D! DAEyBy! EAaC

12. Pushdo#n 6utomata merupakan mesin pengenal untuk kelas bahasa ........a) G c) FGb) 'SG d)$'G

1*. 6utomata &ingga merupakan mesin pengenal untuk kelas bahasa ........a) G c) '(Gb) 'SG d) FG

1+. 0erikut himpunan string yang dapat dibentuk dari ;kspresi egular />B1)>>! kecuali .....a) * c) >>>b) 1>> d) >>1>>

1. Kedudukan teori bahasa dan automata pada bidang komputasi berperan pada bagian...a) +odel dan gagasan mendasar c)So$t#areb) Teknik rekayasa d)&ard#are

14. Secara teoritis ilmu komputer dia#ali dari seHumlah disiplin ilmuI 0iologi! ;lektro!matematika. 6hli bahasa Huga berperan dengan menyelidiki...........

a)


3/9

aturan"aturan yang mana simbol"simbol tersebut bisa dikombinasikan kedalam entitasyang disebut.....

a) Kata c)Kalimatb) Grammar d) %tomata

2*. %tomata merupakan suatu sistem yang terdiri atas seHumlah berhingga ............ yang

menyatakan in$ormasi mengenai input yang lalu! dan dapat pula dianggap sebagaimemori mesin.a) uas /;dge) c) 6cceptance Stateb) Stata (State) d) Token

2+. Perhatikan pushdown automata/P,6) P @>! 1C! @a! bC! @ a! b! EC! >! E! (! @>C3dengan ( sebagai berikutI(/>! a! E) /1! aE)(/1! a! a ) /1! aa )(/1! b! a ) /1!)(/1!! E) />! E)Kon$igurasi yang benar setelah kon$igurasi a#al untuk stringkatakalimat ab Hikadiinputkan padapushdown automataP adalahI

a) />! ab! E) B" /1! b! E) c) />! ab! E) B" /1! b! a)b) (2, ab, 3) %4 (2*, b, a3) d) />! ab! E) B" /1! b! Ea)

2. Kon$igurasi yang benar setelah kon$igurasi /1! b! aE) pada P,6 P pada soal no.2+adalah ........

a) /1! N! aE) c) /1! N! N)b) (2*, 5, 3) d) /1! N! bE)

24. Frutan kon$igurasi yang benar untuk string aabb Hika diinputkan ke mesin pushdownautomataP pada soal no.2+ adalah .....

a) />! aabb! E) B" /1! abb! aE) B" /1! bb! aaE) B" /1! b! a3) B" /1! N! 3) B" />! N!E)

b) />! aabb! E) B" /1! abb! aE) B" /1! bb! aE) B" /1! bb! E) B" />! bb! E)c) />! aabb! E) B" /1! abb! aE) B" /1! bb! aE) B" /1! b! N)d) />! aabb! E) B" /1! abb! E) B" /1! bb! a) B" /1! b! N)

25. Kelebihan mesin Turing dibandingkan Push ,o#n 6utomata dan 6utomata &inggaadalah pada manaHemen .....

a) +emori c) (inal Stateb) State"State d) Tata 0ahasa

27. Mesin Turing M @1!2C!@a!bC!@a!b!bC!O! S@1C!(@2C! b3 dengan $ungsi transisi IO/1!a) /1! a! )O/1!b) /1! a! )O/1!b) /2! b ! L)maka string abbaa akan .....

a) no response c) haltb) ditolak d) diterima

2=. Push ,o#n 6utomata yang menerima string input Hika kondisi stack kosong disebut ....


4/9

a) P,6 $inal state c) P,6 deterministikb) P,6 non"deterministik d) 16A ull stack

*>. Linier"0ounded 6utomata adalah Mesin pengenal untuk Grammar .......a) G c) FGb) '(G d) $SG

*1. Dang dimaksud dengan 0ootStrap! adalaha) 0agaimana orang mengerti bahasa mesinb) Penggunaan bahasa tingkat tinggic) 7ntuk membangun sesuatu /ang besar dibangun dulu bagian intin/ad) Fntuk menghidupkan computer

*2.


5/9

*=. . Translator yang Source code nya adalah bahasa tingkat tinggi! object code adalahbahasa mesin atau bahasa assembly. Source code dan data diproses berbeda! disebutdengan....

a) 6ssembler c) :nterpreter b) $ompiler d) ,ecoder

+1. Dang dimaksud dengan ,iagram Synta-! pada teknik Kompilasi adalaha) ,igunakan untuk mendapatkan token! mempermudah melakukan analisis

le-icalb) Alat bantu (tools) dalam pembuatan parser> analisis sintaksisc) ,igunakan untuk mendapatkan token! mempermudah melakukan analisis

synta-d) Simbol terminal

+2. ,ua teknik Top ,o#n Parsing adalah Ia) ekursi kiri dan ambiguous c) Brute4'orce dan tanpa back4upb) 0rute"(orce dan ambiguous d) 6mbiguous dan tanpa back"up

+*. 6nalisa relasi presedens adalah metoda parsing yang termasuk teknik parsing Ia) Tanpa back"up c) Top",o#nb) 0rute"$orce d)Bottom4up

++. Sebuah kalimat yang mempunyai lebih dari satu pohon parsing disebut Ia) Ambiguous c) Predictieb) Le$t recursie d) ight recursie

+. Tahapan dalam kompilasi yang bertuHuan untuk menghasilkan kode program yangberukuran lebih kecil dan lebih cepat eksekusinya.

a) Tahap code optimi0er c) Tahap Sintesab) Tahap code generator d) Tahap 6nalisa

+4. %ptimasi yang dilakukan hanya pada suatu blok dari source code disebut........a) %ptimasi serial c) %ptimasi Paralelb) %ptimasi Global d) @ptimasi lokal

+5. ,iketahui ;kspresi eguler Iabcc maka string yang dibangkitkan adalah sebagaiberikut kecuali...

a) acc c)abcbccb) abcc d) abbcc

+7. ,iketahui ;kspresi eguler I/a8b) maka string yang dibangkitkan adalah sebagaiberikut kecuali...

a) aabbababa c) aaabbsbbbabab


6/9

b) bbabbabba d) abbabbabbabba

+=. ;kspresi eguler yang membangkitkan string yang memuat minimal dua nol berurutan/>>) adalah ..........

a) />1)>>/>1) c) />81)>>/>81)b) >>8>>8>> d) (;*). ;kspresi eguler yang membangkitkan string yang berakhiran dua nol berurutan />>)adalah ..........

a) (;*)81)>>b) />81)>> d) />81)>>

1. 6utomata Stata &ingga dengan output disebut......a) Transducer c) Transmitterb) Translator d) 6ccepter

2. 6utomata Stata &ingga yang hanya menerima atau menolak input disebut.......a) Transducer c) transmitter b) Translator d) Accepter

*. Pada 6utomata hingga non"deterministik terdapat transisi hampa yang artinya.....a) diperbolehkan merubah state tanpa membaca inputb) Semua input masuk transisi hampac) Transisi yang menuHu $inal stated) semua salah

+. himpunan stata"state yang dapat dicapai dari suatu state tanpa membaca inputdisebut....

a) state space c) :nitial stateb) $inal state d) epsilon4closure

. Fntuk mendapatkan 6utomata hingga deterministik /6&,) dari 6utomata hingga non"deterministik dengan transisi hampa /6&< epsilon"closure)! maka harus diubah dahulumenHadi..

a) 6&, dengan transisi hampa c) A8b) egular Grammar d) ;kspresi eguler

4. ,iketahui ;kspresi reguler I a8b maka salah satu string yang dibangkitkan adalah...a) aab c) abab...abb) aa...ab....bb d) aa

5. ,iketahui ;kspresi reguler I ad maka string paling pendek /minimal) yang dibangkitkanadalah..

a) a c) db) ad d) hampa

7. 'iri utama dari mesin Mealy adalah..........a) Qumlah input lebih banyak dari Humlah outputb) Qumlah input lebih sedikit dari Humlah output


7/9

c) umlah input sama dengan Cumlah outputd) semua salah

=. 'iri utama dari mesin Moore adalah.......a) Qumlah input sama dengan dari Humlah outputb) Qumlah input lebih sedikit dari Humlah output

c) Qumlah input dan Humlah output bebasd) umlah input lebih ban/ak dari Cumlah output

4>. Fntuk memperoleh ekialensi mesin Mealy dari suatu mesin Moore cukup dengan....a) Menambah label output ke setiap transisib) +enambah label output ke setiap transisi dan menghapus label output

pd statec) Menghapus label output pd stated) semua salah

41. 0ila sebuah automata hingga mempunyai kemampuan memori yang terbatas! padaautomata push"do#n dide$inisikan sebuah tempat penyimpanan yang tidak terbatasberupa.......

a) Stata"stata c) pita magnetikb) Stack d) cakram

42. 6turan pengisian pada tempat penyimpanan automata push"do#n adalah....a) (:(% /$irst in $irst out) c) (:L% /$irst in last out)b) LD'@ (last in :irst out) d) L:L% /last in last out)

4*. Pengambilan elemen dari tempat penyimpanan P,6 disebut....a) operasi in$i- c) operasi pre:ixb) operasi push d) operasi pop

4+. Pemasukan elemen kedalam memori P,6 disebut....a) operasi in$i- c) operasi pre$i-b) operasi push d) operasi pop

4. ;kialensi (inal State P,6 dan


8/9

d) memori, secondar/ storage, program

47. Fntuk menyatakan secara $ormal kon$igurasi Mesin Turing pada suatu saat disebut....a) $ormal language c) grammar b) uniersal $ormal $orm d) deskripsi seketika

4=. Sebuah mesin Turing bisa saHa berHalan terus tanpa pernah berhenti. Kondisi itu biasadisebut sebagai loop tak berhingga! dimana loop ini menunHukkan bah#a input yangdimasukkan......

a) 6itolak c) diterimab) &alt d) semua salah

5>. Sebuah hipotesa yang menyatakan bah#a setiap komputasi yang bisa dilakukan secaramekanis bisa dilakukan Huga oleh mesin Turing disebut dengan.....

a) ,alil ,eMorgan c) ,alil Lagrangeb) ,alil 'auchy d) 6alil Turing

51. angkaian kalimat yang terdiri dari simbol"simbol yang mempunyai makna disebut..a) Bahasa c) #ordb) input d) string

52. Sebuah tata bahasa bebas konteks dimana ruas kanan dari setiap aturan produksinyaterdiri dari dua simbol ariabel atau satu simbol terminal disebut

a) 0ackus


9/9

57. 6turan yang berhubungan dengan ariabel yang menyatakan bagaimana menggeneratestring"string dalam bahasa disebut

a) 6turan 0aku c) aturan tertulisb) de$inisi seketika d) 1roduksi

5=. Simbol yang masih memiliki penurunanmasih bisa diturunkan disebut

a) variabel c) terminalb) Token d) produksi

7>. 0entuk Hamak dari besaran leksik adalaha) leksiks c) leksikalb) leksim d) salah semua

Kunci Qa#aban

1. 0 24. 6 1. 6 54. 02. 0 25. 6 2. , 55. '*. 0 27. , *. 6 57. ,+. 6 2=. , +. , 5=. 6. , *>. , . ' 7>. 04. , *1. ' 4. ,5. ' *2. , 5. '7. ' **. 6 7. '=. 0 *+. 6 =. ,1>.0 *. 6 4>. 011. ' *4. , 41. 012., *5. ' 42. 01*.6 *7. ' 4*. ,1+.6 *=. 0 4+. 01.6 +>. 0 4. 014., +1. 0 44. '15.' +2. ' 45. ,17.' +*. , 47. ,1=., ++. 6 4=. 62>.6 +. 6 5>. ,21., +4. , 51. 622.' +5. ' 52. 02*.0 +7. ' 5*. '2+.0 +=. , 5+. ,2.0 >. 6 5. 6

u as automata

Documents