Neka je zadana neka Turingova mašina M sa ulaznim alfabetom Σ={0,1}. Ndalje, pretpostavimo da univerzalna Turingova mašina UTM U koja je rađena na predavanjima  simulira rad TM M.  Neka su stanja TM M označena brojevima 1,2,...n, gdje je n broj stanja. Stanje trake UTM U u jednom konkretnom trenutku simulacije je prikazano na slici ispod.   

Izaberite ispravne tvrdnje:

Koliko stanja će imati NKA koji je konstruisan iz datog ε-NKA?

NAPOMENA: netačni odgovori nose negativne bodove

Neka je zadan sljedeći regularni izraz r₁

r₁= a(a+b)*b(a+b)* + aaa + a

Izaberite koje riječi navedeni ispod se nalaze u jeziku L(r₁):

Koliko stanja će imati NKA koji je konstruisan iz datog ε-NKA?

Neka je zadan sljedeći jezik: 

Na slici je zadan potisni automat koji prihvata riječi praznim stack-om sa jednim nedostajućim prijelazom. 

Odabrati ispravan prijelaz između stanja q0 i q0.

Neka je zadana sljedeća konteksno neovisna gramatika: 

sa sljedećim produkcijskim pravilima: 

Odabrati riječi koje se mogu generisati primjenom ovih produkcijskih pravila. 

NAPOMENA: netačni odgovori nose negativne bodove.