J_{}ezyki, Automaty i Obliczenia

Zadania egzaminacyjne

Damian Niwiński

Egzamin zerowy 1994/1995

1. Pan X postanowił, że każdego dnia b_{}edzie pracował lub nie, przestrzegaj _{}ac przy tym zasady, by na żadne siedem kolejnych dni nie przypadało wi_{}ecej niż cztery dni pracy. Możliwy rozkład dni pracy pana X w ci _{}agu n kolejnych dni możemy przedstawić jako n-bitowe słowo, gdzie 1 odpowiada dniowi pracy, a 0 dniowi odpoczynku. Dowieść, że zbiór wszystkich tak otrzymanych słów jest j_{}ezykiem regularnym (nad alfabetem {0, 1}). Znaleźć minimalny automat deterministyczny.

2. Dowieść, że dla dowolnego j_{}ezyka regularnego L, j_{}ezyk

{w : w^{|w|} ∈ L}

jest również regularny.

3. Rozważamy alfabet {1, +, ∗, =}. Czy nast_{}epuj _{}ace j_{}ezyki s _{}a bezkontekstowe?

(a) {1^{x} + 1^{y} = 1^{z} : x + y = z}

(b) {1^{x} ∗ 1^{y} = 1^{z} : x · y = z}

4. Rozważamy formuły rachunku zdań z jedn _{}a zmienn _{}a zdaniow _{}a X. Dowieść, że nast_{}epuj _{}ace zbiory tworz _{}a j_{}ezyki bezkontekstowe:

(a) zbiór formuł spełnialnych (tj. takich, że istnieje wartościowanie zmiennej X przy którym formuła jest prawdziwa),

(b) zbiór tautologii (tj. formuł prawdziwych dla każdego wartościowania zmiennej X).

Uwaga. Formuły można rozważać w notacji in-fiksowej (tj. klasycznej) lub w notacji polskiej, pre-fiksowej b _{}adź post-fiksowej, do wyboru.

5. Powiemy, że maszyna Turinga jest write-once jeśli może pisać tylko w pustych komórkach taśmy, a symbol raz napisany nie może być zast _{}apiony żadnym innym symbolem (w szczególności nie może być “zmazany” tj. zast _{}apiony przez “blank”). Dla dowolnej maszyny Turinga z jedn _{}a taśm _{}a, skonstruować maszyn_{}e write-once z nie wi_{}ecej niż trzema taśmami, która akceptuje ten sam j_{}ezyk. (Wolno powi_{}ekszyć również alfabet roboczy.)

Egzamin – 1 termin, 1994/1995

1. Pan X zakupił pakiety trzech różnych akcji: A, B i C. Każdego dnia bada wzajemne położenie wartości swoich akcji, które może być reprezentowane jako uporz _{}adkowanie zbioru {A, B, C}, w kierunku od najmniej do najbardziej wartościowej. (Przyjmujemy założenie, że dwie różne akcje maj _{}a zawsze różne wartości.) Pan X postanowił, że jeśli w ci _{}agu dwóch kolejnych dni któraś z akcji dwukrotnie spadnie na niższ _{}a pozycj_{}e, to sprzeda t_{}e akcj_{}e. Np. jeśli kolejne notowania (w tym wypadku: uporz _{}adkowania) s _{}a (A, B, C), (B, C, A), (C, B, A) to pan X sprzeda pakiet akcji C. Rozważamy zbiór G wszystkich uporz _{}adkowań liniowych zbioru {A, B, C}. Dowieść, że zbiór tych ci _{}agów nad alfabetem G, które opisuj _{}a takie wyniki notowań giełdowych, przy których pan X nie pozb_{}edzie si_{}e żadnego pakietu akcji, jest j_{}ezykiem regularnym. Znaleźć liczb_{}e stanów automatu minimalnego akceptuj _{}acego ten j_{}ezyk.

2. Przypomnijmy, że zbiór wyrażeń regularnych nad alfabetem Σ oznaczamy R(Σ), oraz że, dla r ∈ R(Σ), L[r] ⊆ Σ^{∗} jest j_{}ezykiem opisywanym przez r. Które z poniższych j_{}ezyków s _{}a regularne lub bezkontekstowe:

(a) {r ∈ R(Σ) : L[r] ≠ ∅},

(b) {r ∈ R(Σ) : L[r] jest nieskończony },

(c) dla a ∈ Σ, {r ∈ R(Σ) : L[r] ∩ Σ^{∗}aΣ^{∗} ≠ ∅}, (tzn. symbol a wyst_{}epuje w jakimmś słowie z L[r]),

(d) {ar : r ∈ R(Σ) oraz L[r] ∩ Σ^{∗}aΣ^{∗} ≠ ∅}

(e) {r$s : r, s ∈ R(Σ) oraz L[r] = L[s]},

(f) {ar : r ∈ R(Σ) oraz L[r] ∩ Σ^{∗}aΣ^{∗} ≠ ∅}

(g) {r$s^{R} : r, s ∈ R(Σ) oraz L[r] = L[s]}.

3. Określamy nast_{}epuj _{}acy j_{}ezyk nad alfabetem {0, 1}.

L = \{\underbrace{11 … 1}_{n} 0 \underbrace{1 … 1}_{m_{1}} 0 … \underbrace{1 … 1}_{m_{k}} : m_{1} + … + m_{k} = n\}

• Czy L jest regularny?

• Czy L jest bezkontekstowy?

4. bis Niech L ⊆ Σ b_{}edzie j_{}ezykiem regularnym. Określamy j_{}ezyk nad alfabetem

Σ ∪ {♯}.

L = {w♯w_{1}♯w_{2}♯ … ♯w_{m} : w, w_{1}, …, w_{m} ∈ L ∧ m = |w|}

• Czy L jest regularny?

• Czy L jest bezkontekstowy?

5. bis bis Niech L ⊆ Σ b_{}edzie j_{}ezykiem regularnym. Określamy j_{}ezyk nad alfabetem Σ ∪ {♯}.

L = {w♯w_{1}♯w_{2}♯ … ♯w_{m} : m ∈ N w, w_{1}, …, w_{m} ∈ L ∧ |w_{1}| + … + |w_{m}| = |w|} • Czy L jest regularny?

• Czy L jest bezkontekstowy?

J_{}ezyki, Automaty i Obliczenia. Egzamin – 2 termin, 1994/1995

1. Niech L b_{}edzie zbiorem słów w ∈ {a, b}^{∗}, które zawieraj _{}a przynajminiej jedno wyst _{}apienie symbolu b, przy czym bezpośrednio przed ostatnim wyst _{}apieniem symbolu b w słowie w musi wyst _{}apić symbol a. Dowieść, że L jest j_{}ezykiem regularnym. Podać liczb_{}e stanów minimalnego automatu deterministycznego rozpoznaj _{}acego j_{}ezyk L. Skonstruować wyrażenia regularne opisuj _{}ace każd _{}a z klas abstrakcji relacji ∼_{L} z twierdzenia Myhill’a–Nerode’a wyznaczonej przez L.

2. Jakie z nast_{}epuj _{}acych j_{}ezyków s _{}a regularne, a jakie bezkontekstowe ale nie regularne?

(a) Zbiór słów nad alfabetem {a, b}, w których a wyst_{}epuje tyle samo razy co b.

(b) Zbiór słów nad alfabetem {a, b}, takich, że w każdym bloku kolejnych 10 liter (o ile słowo jest długości co najmniej 10), a wyst_{}epuje tyle samo razy co b.

(c) Zbiór słów nad alfabetem {a, b}, w których liczba wyst _{}apień a jest kwadratem liczby wyst _{}apień b.

3. Dla słowa w ∈ {a, b}^{∗}, określamy σ(w) jako zbiór wszystkich permutacji słowa w, tzn. , gdy w = w_{1} … w_{m}, gdzie w_{1}, …, w_{m} ∈ {a, b}, to

σ(w) = {w_{f(1)}w_{f(2)} … w_{f(m)} : f jest permutacj _{}a zbioru {1, …, n} }

Dla L ⊆ {a, b}^{∗},

σ(L) = ⋃_{w∈L} σ(w)

• Czy dla dowolnego j_{}ezyka regularnego L, σ(L) jest j_{}ezykiem bezkontekstowym ? (Wskazówka : czy σ({a^{n}(bc)^{n} : n ∈ N}) jest j_{}ezykiem bezkontekstowym ?)

• Czy dla dowolnego j_{}ezyka regularnego L, σ(L) jest j_{}ezykiem regularnym?

J_{}ezyki, Automaty i Obliczenia. Rok 3

Egzamin 1994. Test

1. Ile stanów ma minimalny automat deterministyczny nad alfabetem wejściowym {a, b}, akceptuj _{}acy zbiór słów w takich, że |w| ≥ 1994 ?

(a) 1995

(b) 1996

(c) 2^{1994}

(d) nieskończenie wiele stanow

2. Rozważamy nast_{}epuj _{}acy problem algorytmiczny. Dane: słowo w i wyrażenie regularne r. Pytanie: czy w ∈ L[r].

(a) Można zawsze skonstruować deterministyczny automat akceptuj _{}acy L[r] o O(|r|) stanach i rozstrzygn _{}ać powyższy problem w O(|w| · |r|) krokach.

(b) Istnieje algorytm rozwi _{}azuj _{}acy problem w |w||r|^{3} krokach.

(c) Dla pewnych wyrażeń regularnych nie istnieje algorytm rozwi _{}azuj _{}acy ten problem.

(d) Istnieje algorytm rozwi _{}azuj _{}acy problem w |w|^{2} krokach (długość r nie ma zna-

czenia).

3. Niech L, M ⊆ Σ^{∗}. Jeśli L = M^{∗}, to (a) L = M

(b) może być L ≠ M, ale na pewno jeden ze zbiorów jest zawarty w drugim

(c) na pewno L ≠ M

(d) L^{∗} = (L ∪ M)^{∗}

4. Jeśli L ⊆ Σ^{∗} jest bezkontekstowy a R, SΣ^{∗} s _{}a regularne, to (a) (L^{−1}R)S jest bezkontekstowy, ale może nie być regularny

(b) ((SL^{−1})^{−1}L)R^{−1} jest bezkontekstowy

(c) R^{∗} − S^{∗} jest bezkontekstowy, ale może nie być regularny

(d) L^{∗} − S^{∗} jest bezkontekstowy, ale może nie być regularny

5. Niech L ⊆ Σ^{∗} b_{}edzie j_{}ezykiem regularnym. Wówczas (a) istnieje stała M > 0, taka że (∀w ∈ L)|w| > M ⇒ ww ∈ L

(b) (∃M > 0) (∀w ∈ Σ^{∗})(w ∈ L ∧ |w| ≥ M) ⇒ (∃x, y, z)(w = xyz ∧ xy^{∗}z ⊆ L

(c) (∃M > 0) (∀w ∈ Σ^{∗})(w ∈ L ∧ |w| ≥ M) ⇒ (∀x)(∃y, z) (w = xyz ⇒ xy^{∗}z ⊆ L (d) (∃M > 0) (∀w ∈ Σ^{∗})w^{M} ∈ L

6. Jeśli skonczony automat niedeterministyczny akceptujacy jezyk L ⊆ Σ^{∗} ma k stanów, to minimalny automat deterministyczny akceptuj _{}acy j_{}ezyk LL

(a) ma co najmniej 2^{k} stanów

(b) ma nie wi_{}ecej niż 4^{k} stanów

(c) może nie istnieć

(d) ma dokładnie |Σ|^{k} stanów

7. Istnieje algorytm, który maj _{}ac na wejściu automat ze stosem nad alfabetem Σ, (a) oblicza liczb_{}e stanów automatu

(b) sprawdza, czy L(A) = Σ^{∗}

(c) sprawdza, czy L(A) jest nieskończony

(d) znajduje gramatyk_{}e bezkontekstow _{}a tak _{}a, że L(G) = Σ^{∗} − L(A)

8. Niech M b_{}edzie maszyn _{}a Turinga, A – automatem skończonym, a B – automatem ze stosem. Wówczas

(a) zbiór (L(M) − L(A))L(B) jest cz_{}eściowo obliczalny

(b) zbiór L(A) − L(M) jest bezkontekstowy

(c) zbiór L(B) − L(A) jest bezkontekstowy

(d) zbiór (L(A) (L(M))^{−1}) (L(B))^{−1} jest regularny

9. Które z nast_{}epuj _{}acych wyrażeń regularnych opisuj _{}a j_{}ezyk akceptowany przez wskazany automat:

(a) (00(010)^{∗}00(0 + 1))^{∗} + (1(010)^{∗}00(0 + 1))^{∗}

(b) (((((0 + 1)^{∗} + 1)^{∗} + 1)^{∗} + 1)^{∗} + 1)^{∗}

(c) (00(010)^{∗}00(0 + 1) + 1(010)^{∗}00(0 + 1))^{∗}

(d) (0000(0 + 1) + 100(0 + 1) + 0001000(0 + 1) + 10100(0 + 1))^{∗}

10. Niech L ⊆ Σ^{∗}. Określamy relacj_{}e ∼^{R} nast_{}epuj _{}aco:

w ∼^{R} v ⇔ ((∀u ∈ Sigma^{∗})uw ∈ L ⇔ uv ∈ L)

(a) ∼^{R} nie jest relacj _{}a równoważności

(b) jeśli relacja ∼^{R} ma skończenie wiele klas abstrakcji, to L jest skończony

(c) jeśli L jest bezkontekstowy, to relacja ∼^{R} ma skończenie wiele klas abstrakcji (d) relacja ∼^{R} ma skończenie wiele klas abstrakcji ⇔ L jest regularny

JAO. Egzamin zerowy. 1995/1996

1. Trzy drużyny piłkarskie A, B i C rozgrywaj _{}a mi_{}edzy sob _{}a seri_{}e spotkań towarzyskich, przy czym umówiły si_{}e, że każdy kolejny mecz jest rozgrywany pomi_{}edzy drużyn _{}a, która wygrała poprzedni mecz i drużyn_{}e, która nie brała udziału w tym meczu (tzn. jeśli drużyna X wygrała z drużyn _{}a Y, to nast_{}epne spotkanie rozegra drużyna X z drużyn _{}a Z). Zakładamy, że nie ma remisów. Rozważamy zbiór słów nad alfabetem {A, B, C}, stanowi _{}acych możliwe ci _{}agi zwyci_{}ezców kolejnych spotkań. Dowieść, że ten j_{}ezyk jest regularny. Zbudować minimalny automat deterministyczny, który go rozpoznaje.

2. (*) Dowieść, że jeśli L jest j_{}ezykiem regularnym nad dowolnym alfabetem Σ, to

j_{}ezyk

{1^{n} : liczba |L ∩ Σ^{n}| jest parzysta }

jest również j_{}ezykiem regularnym.

3. Zbadać, które z nast_{}epuj _{}acych j_{}ezyków s _{}a regularne lub bezkontekstowe. Odpowiedź (pozytywn _{}a lub negatywn _{}a) należy uzasadnić.

(a)

{0^{x}10^{y}10^{z}10^{w} : x + z = y + w}

(b) zbiór słów nad alfabetem {a, b}, w których sekwencja ab wyst_{}epuje tyle samo razy, co sekwencja ba (bardziej formalnie, liczba pozycji i w słowie w = w_{1}w_{2} … w_{n}, takich że w_{i} = a i w_{i+1} = b, oraz liczba pozycji j, takich, że w_{j} = b i w_{j+1} = a, s _{}a równe);

(c) zbiór słów nad alfabetem {a, b, c}, postaci ww^{R}, gdzie ponadto w jest palindromem.

4. Niech M b_{}edzie maszyn _{}a Turinga nad alfabetem {0, 1}, tak _{}a, że L(M) = {0, 1}^{∗}. Określamy funkcj_{}e T : {0, 1}^{∗} ⟶ {0, 1}^{∗} w ten sposób, że T (w) jest liczb _{}a kroków, jakie maszyna M wykonuje dla słowa wejściowego w, zapisan _{}a w postaci binarnej. Skonstruować maszyn_{}e M_{1} obliczaj _{}ac _{}a funkcj_{}e T. Oszacować złożoność czasow _{}a skonstruowanej maszyny M_{1}.

JAO. Pierwszy termin – zadania. 1995/1996

1. Punkt A porusza si_{}e po siatce sześcianu o wierzchołkach (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1) (w R^{3}). Z każdego wierzchołka, punkt A może wykonać trzy ruchy, odpowiadaj _{}ace przemieszczeniom w kierunku osi 0x, osi 0y i osi 0z, ruchy te nazwiemy właśnie x, y i z, oodpowiednio.

Innymi słowy, ruch x powoduje zmian_{}e położenia z (i, j, k) na (i + 1 mod 2, j, k), ruch y : (i, j, k) ⇝ (i, j + 1 mod 2, k), ruch z : (i, j, k) ⇝ (i, j, k + 1 mod 2).

Zakładamy, że w chwili pocz _{}atkowej punkt A znajduje si_{}e w położeniu (0, 0, 0).

Każde słowo nad alfabetem {x, y, z} wyznacza pewn _{}a tras_{}e punktu A po siatce sześcianu. Rozważamy zbiór słów odpowiadaj _{}acych takim trasom, że w ci _{}agu każdych czterech kolejnych chwil punkt A przynajmniej raz dotknie podstawy sześcianu, tzn. co najmniej jedno z czterech kolejnych położeń jest postaci (i, j, 0).

Dowieść, że jest to j_{}ezyk regularny i zbudować minimalny automat deterministyczny rozpoznaj _{}acy ten j_{}ezyk.

2. Dowieść, że jeżeli L ⊆ Σ^{∗} jest j_{}ezykiem regularnym, to

{w ∈ Σ^{∗} : istnieje nieskończenie wiele n ∈ N, takich że w^{n} ∈ L}

też jest j_{}ezykiem regularnym.

3. Niech E b_{}edzie zbiorem wyrażeń generowanych przez gramatyk_{}e

X → 1 | (X + X) | (X ⋆ X)

Czy nast_{}epuj _{}acy j_{}ezyk jest bezkontekstowy ?

(a) zbiór słów postaci E_{1} = E_{2}, gdzie E_{1}, E_{2} ∈ E i równość E_{1} = E_{2} zachodzi w pierścieniu Z_{2} (wszystkie działania modulo 2);

(b) zbiór słów postaci E_{1} = E_{2}, gdzie E_{1}, E_{2} ∈ E i równość E_{1} = E_{2} zachodzi w zbiorze liczb naturalnych N.

4. Niech M b_{}edzie maszyn _{}a Turinga i niech Q b_{}edzie zbiorem stanów maszyny M. Rozważamy zbiór wszystkich możliwych obliczeń maszyny M, dla wszystkich możliwych słów wejściowych. Z każdym skończonym fragmentem pocz _{}atkowym takiego obliczenia, powiedzmy C_{0} ⊢_{M} C_{1} ⊢_{M} … ⊢_{M} C_{n}, wi _{}ażemy ci _{}ag stanów, jakie wyst_{}epuj _{}a w kolejnych konfiguracjach C_{0}, C_{1}, …, C_{n}. Otrzymujemy w ten sposób pewien j_{}ezyk nad alfabetem Q.

Czy ten j_{}ezyk jest bezkontekstowy ?

JAO. Pierwszy termin – test. 1995/1996

1. Opisać za pomoc _{}a wyrażenia regularnego zbiory słów nad alfabetem {0, 1} o nast_{}epuj _{}acych własnościach :

(a) symbol 0 wyst_{}epuje co najwyżej dwa razy;

(b) symbol 0 nie wyst_{}epuje nigdy przed symbolem 1;

(c) każde dwa s _{}asiaduj _{}ace ze sob _{}a symbole s _{}a różne;

(d) symbol 1 wyst_{}epuje nieparzyst _{}a liczb_{}e razy.

2. Podać przykład j_{}ezyka, który jest bezkontekstowy, ale nie jest regularny.

3. Podać przykład j_{}ezyka, który jest obliczalny, ale nie jest bezkontekstowy.

4. Podać przykład j_{}ezyka, który jest cz_{}eściowo obliczalny, ale nie jest obliczalny.

5. Podać przykład j_{}ezyka, który nie jest cz_{}eściowo obliczalny (tzn. nie jest rozpoznawany przez żadn _{}a maszyn_{}e Turinga).

6. Podać przykład problemu NP –zupełnego.

7. Które z poniższych stwierdzeń s _{}a prawdziwe? (Przy każdym zdaniu, prosz_{}e napisać TAK lub NIE.)

(a) Deterministyczna maszyna Turinga zatrzymuje si_{}e dla każdego słowa wejściowego.

(b) Niedeterministyczna maszyna Turinga może mieć wi_{}ecej niż jedno obliczenie dla tego samego słowa wejściowego.

(c) Niedeterministyczna maszyna Turinga, to taka maszyna Turinga, która ma obliczenia nieskończone.

(d) Niedeterministyczny automat skończony, to taki automat, który nie jest deter-

ministyczny.

8. Dla których z nast_{}epuj _{}acych problemów istnieje algorytm rozwi _{}azuj _{}acy problem ? (Prosz_{}e odpowiedzieć TAK lub NIE.)

(a) Dane : dwie gramatyki bezkontekstowe G_{1} i G_{2}.

Pytanie : czy L(G_{1}) = L(G_{2})?

(b) Dane : gramatyka bezkontekstowa G i wyrażenie regularne R.

Pytanie : czy L(G) ∩ L[R] ≠ ∅?

(c) Dane : wyrażenie regularne R.

Znaleźć minimalny automat deterministyczny rozpoznaj _{}acy j_{}ezyk L[R].

(d) Dane : niedeterministyczny automat skończony A.

Znaleźć wyrażenie regularne opisuj _{}ace lustrzane odbicie j_{}ezyka L(A).

9. Które z nast_{}epuj _{}acych j_{}ezyków s _{}a regularne ? (Prosz_{}e odpowiedzieć TAK lub NIE.) (a) Zbiór słów, jakie mog _{}a być identyfikatorami w j_{}ezyku Pascal;

(b) Zbiór wyrażeń bez symboli identyfikatorów, reprezentuj _{}acych liczby rzeczywiste w j_{}ezyku Pascal;

(c) Zbiór poprawnie zbudowanych procedur w j_{}ezyku Pascal.

(d) Zbiór słów stanowi _{}acych poprawnie zbudowane kody jednotaśmowych maszyn

Turinga z alfabetem 0, 1, B (określone jak na wykładzie).

10. Które z nast_{}epuj _{}acych j_{}ezyków s _{}a bezkontekstowe? (Prosz_{}e odpowiedzieć TAK lub NIE.)

(a) Zbiór wyrażeń regularnych nad alfabetem {0, 1}.

(b) Zbiór deklaracji zmiennych w j_{}ezyku Pascal nie używaj _{}acych identyfikatorów typów ani identyfikatorów stałych innych niż standardowe.

(c) Zbiór wyrażeń arytmetycznych w j_{}ezyku Pascal nie używaj _{}acych identyfikatorów funkcji innych niż standardowe.

(d) Zbiór wszystkich programów w j_{}ezyku Pascal.

11. Jeśli A jest automatem niedeterministycznym o n stanach rozpoznaj _{}acym j_{}ezyk L, to minimalny automat deterministyczny rozpoznaj _{}acy L ma (prosz_{}e wpisać TAK lub NIE w zależności od tego, czy hipoteza jest zawsze prawdziwa)

(a) n^{2} stanów;

(b) dokładnie 2^{n} stanów;

(c) nie wi_{}ecej niż 2^{n} stanów;

(d) może nie istnieć.

12. Dla nast_{}epuj _{}acej gramatyki, znaleźć równoważn _{}a gramatyk_{}e w postaci Chomsky’ego :

X → XY Y | a

Y → Z | ϵ

Z → a.

13. Które z poniższych stwierdzeń s _{}a prawdziwe? (Przy każdym zdaniu, prosz_{}e napisać TAK lub NIE.)

(a) Jeśli j_{}ezyk jest rozpoznawany przez niedeterministyczn _{}a maszyn_{}e Turinga o złożoności pami_{}eciowej ograniczonej przez wielomian, to, z twierdzenie Savitcha, jest rozpoznawany przez deterministyczn _{}a maszyn_{}e o złożoności pami_{}eciowej O(n^{2}).

(b) Każde dwa problemy NP –zupełne redukuj _{}a si_{}e do siebie wzajemnie w sensie Karpa (tzn. w czasie wielomianowym).

(c) Każdy j_{}ezyk obliczalny jest albo w klasie P, albo w klasie NP.

(d) Jeśli problem plecakowy należy do klasy P, to NP = P.

Uwaga. P — klasa j_{}ezyków rozpoznawanych przez deterministyczne maszyny Turinga w czasie wielomianowym; NP — klasa j_{}ezyków rozpoznawanych przez niedeterministyczne maszyny Turinga w czasie wielomianowym.