Prawdą jest że:

a) języki rekurencyjnie przeliczalne są akceptowane na niedeterministycznych AZS
b) języki kontekstowe są akceptowane na niedeterministycznych AZS
c) można skonstruować taki AZS, który zaakceptuje daną gramatykę regularną
d) żadne z powyższych

Proszę wskazać niejednoznaczności w gramatykach bezkontekstowych: 5

a) dany wyraz można wyprowadzić na więcej niż jeden sposobów (z różnymi drzewami

składniowymi)

b) dany wyraz można wyprowadzić z więcej niż jednej gramatyki bezkontekstowej
c) w ciągu symboli może znajdować się kilka takich samych symboli nieterminalnych ; wówczas nie

wiadomo , który symbol podstawić daną regułą

d) żadne z powyższych

Przykładami problemów NP. są:

a) sprawdzenie prawdziwości reguły w arytmetyce Presburga
b) sortowanie bąbelkowe
c) spełnialność układów logicznych
d) wyszukiwanie ścieżki Hamiltona

Prawdą jest że:

a) każdy problem NP. można przekształcić w NP.-zupełny algorytmem o dowolnej złożoności
b) każdy problem NP. można przekształcić w NP.-zupełny w czasie co najwyżej wielomianowym
c) każdy problem NP. można przekształcić w NP.-zupełny w czasie co najmniej wykładniczym
d) każdy problem NP. znajduje się w klasie NP.

Wyrażenie a^i b^i c^i (gdzie i może być dowolna liczba naturalną) generuje gramatykę:

a) bezkontekstową
b) regularną
c) kontekstową !
d) ogólnego przeznaczenia

W maszynie RAM operandum=i oznacza , że argument jest

a) stałą i
b) zawartością rejestru i
c) i-tą komórką pamięci RAM
d) zawartością rejestru wskazywaną przez komórkę (adresowanie pośrednie)

W problemach NP.-zupełnych prawdziwe są następujące ograniczenia:

a) O-wykładnicze
b) O-wielomianowe
c)

θ-wykładnicze

d)

θ-wykładnicze

Dany jest automat Mealy’ego . Prawdą jest że:

a) równoważny mu automat Moore’a będzie miał |Q|*|Delta|
b) równoważny mu automat Moore’a będzie miał |Q|*|

∑|

c) automatu nie da się przekształcić do automatu Moore’a
d) żadne z powyższych

Wykresów składniowych używa się do opisów języków:

a) regularnych
b) bezkontekstowych
c) kontekstowych
d) rekurencyjnie przeliczalnych

Prawdą jest że dla problemu stopu f dla danych o rozmiarze n:

a) f=O(n^k)
b) f=O(2^n)
c) f=

Ω(n^k)

d) żadne z powyższych

Zgodnie z obecnym stanem wiedzy:

a) co-NP.=NP.
b) problemy NP. są weryfikowane w czasie wielomianowym na maszynach deterministynych !
c) P!=NP.
d) Żadne z powyższych

Prawdą jest że:

a) gramatyki prawostronnie liniowe są podzbiorem gramatyk bezkontekstowych
b) języki bezkontekstowe są podzbiorem języków kontekstowych !
c) zbiór deterministycznych języków bezkontekstowych jest podzbiorem niedeterministycznych języków

bezkontekstowych !

d) zbiór języków rekurencyjnie przeliczalnych jest nadzbiorem języków rekurencyjnych!