To print higher-resolution math symbols, click the
Hi-Res Fonts for Printing button on the jsMath control panel.
If the math symbols print as black boxes, turn off image alpha channels
using the Options pane of the jsMath control panel.

jsMath

Avtomati in teorija jezikov (32 %) (doc. Zoran Bosnić)

Pregled poskusa 1

Začeto dnesreda, 3. november 2010, 22:07
Dokončano dnesreda, 3. november 2010, 22:23
Porabljeni čas16 min 53 s
Točke12/20
Ocena6 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:
#DejanjeOdgovorČasČisto število točkOcena
1Ocenaskladovni avtomat22:07:59 dne 3/11/1000
2Zapri in oceniskladovni avtomat22:23:57 dne 3/11/1000
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:
#DejanjeOdgovorČasČisto število točkOcena
1Ocenaznak za presledek v tračni abecedi22:12:56 dne 3/11/1000
2Zapri in oceniznak za presledek v tračni abecedi22:23:57 dne 3/11/1000
Question 3
Točke: 1/1

Podana je kontekstno neodvisna gramatika G=VTPS (V=množica spremenljivk, T=množica končnih simbolov, P=množica produkcij, S=začetni simbol).

Jezik gramatike G je definiran kot:

Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
#DejanjeOdgovorČasČisto število točkOcena
1Ocenamnožica besed, ki so sestavljene iz samih končnih simbolov in ki jih je možno izpeljati iz začetnega simbola S22:14:24 dne 3/11/1011
2Zapri in ocenimnožica besed, ki so sestavljene iz samih končnih simbolov in ki jih je možno izpeljati iz začetnega simbola S22:23:57 dne 3/11/1011
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:
#DejanjeOdgovorČasČisto število točkOcena
1Ocenavse od naštetega22:14:56 dne 3/11/1011
2Zapri in ocenivse od naštetega22:23:57 dne 3/11/1011
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:
#DejanjeOdgovorČasČisto število točkOcena
1Ocenaregularen22:15:20 dne 3/11/1000
2Zapri in oceniregularen22:23:57 dne 3/11/1000
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:
#DejanjeOdgovorČasČisto število točkOcena
1Ocenalevo rekurzivna in nedvoumna22:15:37 dne 3/11/1000
2Zapri in ocenilevo rekurzivna in nedvoumna22:23:57 dne 3/11/1000
Question 7
Točke: 1/1

Lema o napihovanju za regularne jezike pravi: Naj bo L regularen jezik. Potem obstaja neka konstanta n z lastnostjo: če za xL velja xn , potem obstajajo uvw ( je abeceda jezika) z lastnostjo x=uvw; pri tem pa imamo uvn , v1 in za vse vrednosti i0 velja uviwL.

Podan je jezik L3=aibicii1 . Katera od naslednjih trditev drži?

Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
#DejanjeOdgovorČasČisto število točkOcena
1Ocenaz izpeljavo protislovja lahko z lemo o napihovanju dokažemo, da L3 ni regularen22:17:51 dne 3/11/1011
2Zapri in oceniz izpeljavo protislovja lahko z lemo o napihovanju dokažemo, da L3 ni regularen22:23:57 dne 3/11/1011
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:
#DejanjeOdgovorČasČisto število točkOcena
1Ocenazapis gramatike v krajši obliki22:18:36 dne 3/11/1011
2Zapri in ocenizapis gramatike v krajši obliki22:23:57 dne 3/11/1011
Question 9
Točke: 1/1
Podani so regularni jeziki L1L2 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:
#DejanjeOdgovorČasČisto število točkOcena
1Ocenaregularen22:18:52 dne 3/11/1011
2Zapri in oceniregularen22:23:57 dne 3/11/1011
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:
#DejanjeOdgovorČasČisto število točkOcena
1Ocenadiagonalni jezik Ld22:19:08 dne 3/11/1000
2Zapri in ocenidiagonalni jezik Ld22:23:57 dne 3/11/1000
Question 11
Točke: 1/1
Kontekstno neodvisna gramatika je dvoumna:
Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
#DejanjeOdgovorČasČisto število točkOcena
1Ocenakadar obstaja beseda v jeziku gramatike, za katero obstajata različni drevesi izpeljav22:19:38 dne 3/11/1011
2Zapri in ocenikadar obstaja beseda v jeziku gramatike, za katero obstajata različni drevesi izpeljav22:23:57 dne 3/11/1011
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:
#DejanjeOdgovorČasČisto število točkOcena
1OcenaTuringov stroj s končnim trakom22:19:59 dne 3/11/1011
2Zapri in oceniTuringov stroj s končnim trakom22:23:57 dne 3/11/1011
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:
#DejanjeOdgovorČasČisto število točkOcena
1Ocenazačetni simbol22:20:24 dne 3/11/1000
2Zapri in ocenizačetni simbol22:23:57 dne 3/11/1000
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:
#DejanjeOdgovorČasČisto število točkOcena
1Ocenaregularni, kontekstno-neodvisni, kontekstno-odvisni, rekurzivno števni22:21:17 dne 3/11/1011
2Zapri in oceniregularni, kontekstno-neodvisni, kontekstno-odvisni, rekurzivno števni22:23:57 dne 3/11/1011
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:
#DejanjeOdgovorČasČisto število točkOcena
1Ocenarekurziven jezik22:21:27 dne 3/11/1011
2Zapri in ocenirekurziven jezik22:23:57 dne 3/11/1011
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:
#DejanjeOdgovorČasČisto število točkOcena
1Ocenaprodukcijo oblike A --> a22:22:19 dne 3/11/1011
2Zapri in oceniprodukcijo oblike A --> a22:23:57 dne 3/11/1011
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:
#DejanjeOdgovorČasČisto število točkOcena
1OcenaNP-polnih problemov22:22:37 dne 3/11/1000
2Zapri in oceniNP-polnih problemov22:23:57 dne 3/11/1000
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:
#DejanjeOdgovorČasČisto število točkOcena
1OcenaTuringovi jeziki proti rekurzivnim jezikom22:22:56 dne 3/11/1011
2Zapri in oceniTuringovi jeziki proti rekurzivnim jezikom22:23:57 dne 3/11/1011
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:
#DejanjeOdgovorČasČisto število točkOcena
1Ocenakončni avtomat22:23:35 dne 3/11/1011
2Zapri in ocenikončni avtomat22:23:57 dne 3/11/1011
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:
#DejanjeOdgovorČasČisto število točkOcena
1Ocenaunija jezikov vseh Turingovih strojev22:23:49 dne 3/11/1000
2Zapri in oceniunija jezikov vseh Turingovih strojev22:23:57 dne 3/11/1000