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!