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!