Avtomati in teorija jezikov (32 %) (doc. Zoran Bosnić)
Pregled poskusa 1
Začeto dne | sreda, 3. november 2010, 22:07 |
---|---|
Dokončano dne | sreda, 3. november 2010, 22:23 |
Porabljeni čas | 16 min 53 s |
Točke | 12/20 |
Ocena | 6 od možne ocene 10 (60%) |
Question 1
Točke: 0/1
Podana je gramatika, ki jo definira
četverka: množica spremenljivk, množica končnih simbolov, množica
produkcij in začetno stanje. Za množico produkcij velja, da definira
takšne zamenjave spremenljivk, ki so odvisne od simbolov, ki
spremenljivko obkrožajo. Kateri od naslednjih avtomatov sprejema jezik
takšne gramatike?
Izberite en odgovor.
Napačno
Točke za to oddajo: 0/1.
Zgodovina odgovorov:
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | skladovni avtomat | 22:07:59 dne 3/11/10 | 0 | 0 |
2 | Zapri in oceni | skladovni avtomat | 22:23:57 dne 3/11/10 | 0 | 0 |
Question 2
Točke: 0/1
Klasični Turingov stroj (z enojnim
trakom, ki je neskončen v desno) je definiran s sedmerko, ki med drugim
vključuje: (1) končno množico stanj, (2) množico vhodnih simbolov, (3)
množico tračnih simbolov, (4) začetno stanje. Kateri element izmed
preostalih treh NI ELEMENT te sedmerke?
Izberite en odgovor.
Napačno
Točke za to oddajo: 0/1.
Zgodovina odgovorov:
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | znak za presledek v tračni abecedi | 22:12:56 dne 3/11/10 | 0 | 0 |
2 | Zapri in oceni | znak za presledek v tračni abecedi | 22:23:57 dne 3/11/10 | 0 | 0 |
Question 3
Točke: 1/1
Podana je kontekstno neodvisna gramatika V
T
P
S
Jezik gramatike G je definiran kot:
Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | množica besed, ki so sestavljene iz samih končnih simbolov in ki jih je možno izpeljati iz začetnega simbola S | 22:14:24 dne 3/11/10 | 1 | 1 |
2 | Zapri in oceni | množica besed, ki so sestavljene iz samih končnih simbolov in ki jih je možno izpeljati iz začetnega simbola S | 22:23:57 dne 3/11/10 | 1 | 1 |
Question 4
Točke: 1/1
Jezik besed oblike 0*10* je:
Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | vse od naštetega | 22:14:56 dne 3/11/10 | 1 | 1 |
2 | Zapri in oceni | vse od naštetega | 22:23:57 dne 3/11/10 | 1 | 1 |
Question 5
Točke: 0/1
Vsak kontekstno odvisen jezik je tudi...
Izberite en odgovor.
Napačno
Točke za to oddajo: 0/1.
Zgodovina odgovorov:
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | regularen | 22:15:20 dne 3/11/10 | 0 | 0 |
2 | Zapri in oceni | regularen | 22:23:57 dne 3/11/10 | 0 | 0 |
Question 6
Točke: 0/1
Gramatika, podana z edino produkcijo
S -> Aa | a | aa
je
Izberite en odgovor.
Napačno
Točke za to oddajo: 0/1.
Zgodovina odgovorov:
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | levo rekurzivna in nedvoumna | 22:15:37 dne 3/11/10 | 0 | 0 |
2 | Zapri in oceni | levo rekurzivna in nedvoumna | 22:23:57 dne 3/11/10 | 0 | 0 |
Question 7
Točke: 1/1
Lema o napihovanju za regularne jezike pravi: Naj bo L
x
n
v
w
uv
n
1
0
L
Podan je jezik i
1
Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | z izpeljavo protislovja lahko z lemo o napihovanju dokažemo, da | 22:17:51 dne 3/11/10 | 1 | 1 |
2 | Zapri in oceni | z izpeljavo protislovja lahko z lemo o napihovanju dokažemo, da | 22:23:57 dne 3/11/10 | 1 | 1 |
Question 8
Točke: 1/1
Katera od naslednjih možnosti NE
PREDSTAVLJA prednosti uporabe ene od normalnih oblik (=NO) gramatik
(npr. po Chomskem ali po Greibachovi)?
Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | zapis gramatike v krajši obliki | 22:18:36 dne 3/11/10 | 1 | 1 |
2 | Zapri in oceni | zapis gramatike v krajši obliki | 22:23:57 dne 3/11/10 | 1 | 1 |
Question 9
Točke: 1/1
Podani so regularni jeziki L1 , L2 in L3 . Iz njih naredimo jezik L4=(L1
L2)
L3 . Dobljeni jezik L4 je:



Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | regularen | 22:18:52 dne 3/11/10 | 1 | 1 |
2 | Zapri in oceni | regularen | 22:23:57 dne 3/11/10 | 1 | 1 |
Question 10
Točke: 0/1
Kateri od naslednjih jezikov je Turingov?
Izberite en odgovor.
Napačno
Točke za to oddajo: 0/1.
Zgodovina odgovorov:
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | diagonalni jezik | 22:19:08 dne 3/11/10 | 0 | 0 |
2 | Zapri in oceni | diagonalni jezik | 22:23:57 dne 3/11/10 | 0 | 0 |
Question 11
Točke: 1/1
Kontekstno neodvisna gramatika je dvoumna:
Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | kadar obstaja beseda v jeziku gramatike, za katero obstajata različni drevesi izpeljav | 22:19:38 dne 3/11/10 | 1 | 1 |
2 | Zapri in oceni | kadar obstaja beseda v jeziku gramatike, za katero obstajata različni drevesi izpeljav | 22:23:57 dne 3/11/10 | 1 | 1 |
Question 12
Točke: 1/1
Katera od naslednjih različic NI ekvivalentna osnovni različici modela Turingovega stroja?
Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | Turingov stroj s končnim trakom | 22:19:59 dne 3/11/10 | 1 | 1 |
2 | Zapri in oceni | Turingov stroj s končnim trakom | 22:23:57 dne 3/11/10 | 1 | 1 |
Question 13
Točke: 0/1
Katera od naslednjih možnosti NE predstavlja elementa, ki je potreben za definicijo poljubne kontekstno neodvisne gramatike?
Izberite en odgovor.
Napačno
Točke za to oddajo: 0/1.
Zgodovina odgovorov:
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | začetni simbol | 22:20:24 dne 3/11/10 | 0 | 0 |
2 | Zapri in oceni | začetni simbol | 22:23:57 dne 3/11/10 | 0 | 0 |
Question 14
Točke: 1/1
Razvrsti naslednje jezike gramatik po hierarhiji Chomskega od najnižjega (najmanjša podmnožica vseh jezikov) do najvišjega:
Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | regularni, kontekstno-neodvisni, kontekstno-odvisni, rekurzivno števni | 22:21:17 dne 3/11/10 | 1 | 1 |
2 | Zapri in oceni | regularni, kontekstno-neodvisni, kontekstno-odvisni, rekurzivno števni | 22:23:57 dne 3/11/10 | 1 | 1 |
Question 15
Točke: 1/1
Komplement L rekurzivnega jezika L je
Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | rekurziven jezik | 22:21:27 dne 3/11/10 | 1 | 1 |
2 | Zapri in oceni | rekurziven jezik | 22:23:57 dne 3/11/10 | 1 | 1 |
Question 16
Točke: 1/1
V normalni obliki kontekstno neodvisnih gramatik po Chomskem imajo lahko gramatike
Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | produkcijo oblike A --> a | 22:22:19 dne 3/11/10 | 1 | 1 |
2 | Zapri in oceni | produkcijo oblike A --> a | 22:23:57 dne 3/11/10 | 1 | 1 |
Question 17
Točke: 0/1
Vsak problem, ki ga je v polinomskem času možno izračunati na nedeterminističnem Turingovem stroju, pripada družini
Izberite en odgovor.
Napačno
Točke za to oddajo: 0/1.
Zgodovina odgovorov:
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | NP-polnih problemov | 22:22:37 dne 3/11/10 | 0 | 0 |
2 | Zapri in oceni | NP-polnih problemov | 22:23:57 dne 3/11/10 | 0 | 0 |
Question 18
Točke: 1/1
Parcialno rekurzivne funkcije so proti totalno rekurzivnim funkcijam v enaki "sorodnosti" kot
Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | Turingovi jeziki proti rekurzivnim jezikom | 22:22:56 dne 3/11/10 | 1 | 1 |
2 | Zapri in oceni | Turingovi jeziki proti rekurzivnim jezikom | 22:23:57 dne 3/11/10 | 1 | 1 |
Question 19
Točke: 1/1
Podana sta dva nedeterministična
končna avtomata, od katerih prvi sprejema jezik 0+1*00, drugi pa jezik
1+0*11. Če želimo izdelati avtomat, ki bi sprejemal unijo obeh naštetih
jezikov, potrebujemo najmanj:
Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | končni avtomat | 22:23:35 dne 3/11/10 | 1 | 1 |
2 | Zapri in oceni | končni avtomat | 22:23:57 dne 3/11/10 | 1 | 1 |
Question 20
Točke: 0/1
V domeni Turingov stojev je univerzalni jezik
Izberite en odgovor.
Napačno
Točke za to oddajo: 0/1.
Zgodovina odgovorov:
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | unija jezikov vseh Turingovih strojev | 22:23:49 dne 3/11/10 | 0 | 0 |
2 | Zapri in oceni | unija jezikov vseh Turingovih strojev | 22:23:57 dne 3/11/10 | 0 | 0 |