Języki, automaty i obliczenia/Ćwiczenia 6: Automat niedeterministyczny. Lemat o pompowaniu

Ćwiczenia 6

Ćwiczenie 1

Skonstruuj automat niedeterministyczny akceptujący język $L = A^{*} a A^{*} b A^{*}$ , a następnie określ równoważny automat deterministyczny przy pomocy algorytmu Determinizacja.

Rozwiązanie

Automat niedeterministyczny pokazany jest na rysunku 1.

Automat po determinizacji wyglądać powinien tak samo jak automat z rysunku 5 (patrz ćwiczenia 5.). Zauważ, że automat deterministyczny i niedeterministyczny dla języka $L$ mają po tyle samo stanów.

Ćwiczenie 2

Zastosuj algorytm Determinizacja podany na wykładzie do

determinizacji automatu z rysunku 2.

Rozwiązanie

W tabeli 1 opisane są kolejne kroki pętli (linia 5.) algorytmu Determinizacja. W kolejnych kolumnach tabeli podane są: krok algorytmu, stany dodane do zbioru $S^{'}$ , określenie funkcji przejść $f^{'}$ oraz stany dodane do zbioru stanów końcowych $T^{'}$ .

\begin{array}{ccccc} K r o k & d o d a n e d o S^{'} & o k r e s l e n i e f^{'} & d o d a n e d o T^{'} \\ 0 & {q_{0}} & \emptyset \\ 1 & {q_{0}, q_{3}} & f^{'} ({q_{0}}, a) = {q_{0}, q_{3}} & \emptyset \\ {q_{0}, q_{1}} & f^{'} ({q_{0}}, b) = {q_{0}, q_{1}} \\ 2 & {q_{0}, q_{3}, q_{4}} & f^{'} ({q_{0}, q_{3}}, a) = {q_{0}, q_{3}, q_{4}} & {q_{0}, q_{3}, q_{4}} \\ f^{'} ({q_{0}, q_{3}}, b) = {q_{0}, q_{1}} \\ f^{'} ({q_{0}, q_{1}}, a) = {q_{0}, q_{3}} \\ {q_{0}, q_{1}, q_{2}} & f^{'} ({q_{0}, q_{1}}, b) = {q_{0}, q_{1}, q_{2}} & {q_{0}, q_{1}, q_{2}} \\ 3 & f^{'} ({q_{0}, q_{3}, q_{4}}, a) = {q_{0}, q_{3}, q_{4}} \\ {q_{0}, q_{1}, q_{4}} & f^{'} ({q_{0}, q_{3}, q_{4}}, b) = {q_{0}, q_{1}, q_{4}} & {q_{0}, q_{1}, q_{4}} \\ {q_{0}, q_{2}, q_{3}} & f^{'} ({q_{0}, q_{1}, q_{2}}, a) = {q_{0}, q_{2}, q_{3}} & {q_{0}, q_{2}, q_{3}} \\ f^{'} ({q_{0}, q_{1}, q_{2}}, b) = {q_{0}, q_{1}, q_{2}} \\ 4 & f^{'} ({q_{0}, q_{1}, q_{4}}, a) = {q_{0}, q_{3}, q_{4}} \\ {q_{0}, q_{1}, q_{2}, q_{4}}, & f^{'} ({q_{0}, q_{1}, q_{4}}, b) = {q_{0}, q_{1}, q_{2}, q_{4}} & {q_{0}, q_{1}, q_{2}, q_{4}} \\ {q_{0}, q_{2}, q_{3}, q_{4}} & f^{'} ({q_{0}, q_{2}, q_{3}}, a) = {q_{0}, q_{2}, q_{3}, q_{4}} & {q_{0}, q_{2}, q_{3}, q_{4}} \\ f^{'} ({q_{0}, q_{2}, q_{3}}, b) = {q_{0}, q_{1}, q_{2}} \\ 5 & f^{'} ({q_{0}, q_{1}, q_{2}, q_{4}}, a) = {q_{0}, q_{2}, q_{3}, q_{4}} \\ f^{'} ({q_{0}, q_{1}, q_{2}, q_{4}}, b) = {q_{0}, q_{1}, q_{2}, q_{4}} \\ f^{'} ({q_{0}, q_{2}, q_{3}, q_{4}}, a) = {q_{0}, q_{2}, q_{3}, q_{4}} \\ f^{'} ({q_{0}, q_{2}, q_{3}, q_{4}}, b) = {q_{0}, q_{1}, q_{2}, q_{4}} \end{array}

Automat deterministyczny dla powyższego przykładu przedstawiony jest na rysunku 3. Dla uproszczenia stany tego automatu nie są etykietowane zbiorami, lecz indeksami stanów ze zbioru $Q$ . Na przykład, zamiast ${q_{0}, q_{1}, q_{2}}$ stan etykietowany jest wyrażeniem $012$ .

Automat z rysunku 3 posiada 9 stanów wobec 5 stanów niedeterministycznego automatu wyjściowego.

Ćwiczenie 3

Dla dowolnego $n > 1$ skonstruuj $n$ -stanowy automat niedeterministyczny $𝒜$ nad 3-elementowym alfabetem w ten sposób, by automat deterministyczny posiadał dokładnie $2^{n} - 1$ stanów.

Rozwiązanie

Niech $𝒜 = (S = {s_{0}, \dots, s_{n - 1}}, A = {a, b, c}, f, s_{0}, T)$ będzie automatem niedeterministycznym ( $T$ jest dowolnym podzbiorem $S$ ). Zdefiniujmy funkcję $f : S \times A \to 𝒫 (S)$ następująco:

\begin{aligned} \forall 0 \leq i \leq n - 1 f (s_{i}, a) & = {s_{i - 1 m o d n}}, \\ f (s_{0}, b) & = {s_{0}, s_{1}}, \\ \forall 1 \leq i \leq n - 1 f (s_{i}, b) & = {s_{i + 1 m o d n}}, \\ f (s_{0}, c) & = {s_{1}}, \\ \forall 1 \leq i \leq n - 1 f (s_{i}, c) & = {s_{i}} . \end{aligned}

Pokażemy, że dla każdego $\emptyset = W \subseteq S$ istnieje takie słowo $w \in A^{*}$ , że $f (s_{0}, w) = W$ . Niech $W = {s_{i_{1}}, s_{i_{2}}, . . ., s_{i_{k}}}$ i załóżmy, że ciąg $i_{1}, \dots, i_{k}$ jest rosnący. Niech $d_{j} = i_{j + 1} - i_{j} - 1$ będzie ilością stanów przez które trzeba przejść od stanu $s_{i_{j}}$ do stanu $s_{i_{j + 1}}$ idąc po krawędziach oznaczonych literą $a$ .

Zauważmy, że $f (s_{0}, b^{n - 1}) = S$ . Niech początek szukanego słowa $w$ ma postać $b^{n - 1}$ . Będziemy redukować ilość stanów zbioru $f (s_{0}, b^{n - 1})$ poprzez doklejanie liter $c$ , oraz "przesuwać" układ aktualnie występujących stanów używając liter $a$ .

Niech $S^{'} = f (s_{0}, w v)$ , gdzie $v = (c a)^{d_{1}} a (c a)^{d_{2}} a . . . (c a)^{d_{k - 1}} a$ . Łatwo sprawdzić, że $| S^{'} | = k$ i jeśli ma postać $S^{'} = {s_{j_{1}}, s_{j_{2}}, . . ., s_{j_{k}}}$ , to $j_{1} = 0$ i ponadto zachodzi $\forall 2 \leq t \leq k j_{t} - j_{t - 1} = i_{t} - i_{t - 1}$ . (Intuicyjnie: zastosowanie słowa $(c a)^{d}$ powoduje, że w cyklicznym ustawieniu stanów robi się "przerwa" długości $d$ . Użycie następnie litery $a$ gwarantuje, że kolejna "przerwa" będzie oddzielona od poprzedniej jednym stanem).

Aby otrzymać żądany zbiór $W$ wystarczy "przesunąć" ten zbiór stanów przy pomocy słowa $a^{n - i_{1}}$ . Ostatecznie:

f (s_{0}, w v a^{n - i_{1}}) = W

.

Ponieważ powyższym sposobem możemy uzyskać dowolny niepusty podzbiór $W$ zbioru stanów $S$ , zatem zbiór stanów $R$ automatu deterministycznego musi zawierać stany odpowiadające wszystkim niepustym podzbiorom zbioru $S$ , czyli $| R | = 2^{n} - 1$ .

Automat z pustymi przejściami

Podamy procedurę przetwarzającą niedeterministyczny automat skończony z pustymi przejściami w równoważny niedeterministyczny automat skończony bez pustych przejść.

Niech $𝒜 = (S, A, f, I, F)$ będzie niedeterministycznym automatem z p-przejściami. Dla stanu $s \in S$ zbiór

DOM (s) = {t \in S : t \in f (s, 1)}

nazywamy pustym domknięciem stanu $s$ .

Zbiór DOM $(s)$ jest zbiorem wszystkich stanów, do których można dojść ze stanu $s$ przechodząc po ścieżce etykietowanej słowem pustym 1. Zauważmy także, że dla dowolnego $s \in S$ zachodzi warunek $s \in D O M (s)$ , gdyż ze stanu $s$ do niego samego można przejść pod wpływem słowa o długości 0, a $w^{0} = 1$ .

Dla dowolnego $P \subseteq S$ określamy

DOM (P) = ⋃_{p \in P} DOM (p), f (DOM (P), a) = ⋃_{p \in P} ⋃_{t \in DOM (p)} f (t, a)

Algorytm UsuńPustePrzejścia - buduje niedeterministyczny automat bez p-przejść równoważny danemu niedeterministycznemu automatowi z p-przejściami

  1  Wejście:  $𝒜 = (S, A, f, I, F)$  - automat niedeterministyczny z p-przejściami.
  2  Wyjście:  $𝒜^{'} = (S^{'}, A, f^{'}, I^{'}, F^{'})$  - automat niedeterministyczny bez p-przejść
     taki, że  $L (𝒜^{'}) = L (𝒜)$ .
  3  for each   $s \in S$  do
  4    DOM  $[s] \leftarrow f (s, 1)$ ;                                $▹$  DOM $[s]$  jest zbiorem
  5    for  $i \leftarrow 1$  to  $| S |$  do
  6      DOM  $[s] \leftarrow f$  DOM $[s], 1)$ ;          $▹$  bardziej efektywne jest użycie IFS
  7    end for
  8  end for
  9   $S^{'} \leftarrow S$ ;
 10   $I^{'} \leftarrow I$ ;
 11   $F^{'} \leftarrow \emptyset$ ;                                   $▹$  rozpocznij od zbioru pustego
 12  for each   $s \in S$  do
 13    if  $F \cap$  DOM $[s] \neq \emptyset$  then
 14       $F^{'} \leftarrow F^{'} \cup {s}$ ;
 15    end if
 16  end for
 17  for each  $s \in S$  do
 18    for each   $a \in A$   do
 19       $Y \leftarrow f$  DOM $[s], a)$ ;                               $▹$  stosujemy wzór (1)
 20      for each  $t \in Y$   do
 21         $f^{'} (s, a) \leftarrow f^{'} (s, a) \cup$  DOM $[t]$ ;
 22      end for
 23    end for
 24  endfor
 25  return  $𝒜^{'}$ ;

Ćwiczenie 4

Przy pomocy podanego algorytmu dla automatu określonego na rysunku 4 skonstruuj równoważny automat bez pustych przejść.

Rozwiązanie

Rozważmy automat z p-przejściami pokazany na rysunku 4. Zastosujmy do niego algorytm UsuńPustePrzejścia. Obliczamy:

S^{'} = {q_{0}, q_{1}, q_{2}}, I^{'} = I = {q_{0}}

\begin{aligned} DOM (q_{0}) & = {q_{0}, q_{1}, q_{2}} \\ DOM (q_{1}) & = {q_{1}, q_{2}} \\ DOM (q_{2}) & = {q_{2}} \end{aligned}

F^{'} = {s \in S : {q_{2}} \cap DOM (s) = \emptyset} = {q_{0}, q_{1}, q_{2}}

\begin{aligned} f^{'} (q_{0}, a) & = DOM (f (DOM (q_{0}), a)) = \\ = DOM (f ({q_{0}, q_{1}, q_{2}}, a)) = DOM (q_{0} \cup \emptyset \cup \emptyset) \\ = DOM (q_{0}) = {q_{0}, q_{1}, q_{2}} . \end{aligned}

W analogiczny sposób obliczamy:

\begin{aligned} f^{'} (q_{0}, b) & = DOM (f (DOM (q_{0}), b)) = DOM (q_{1}) = {q_{1}, q_{2}} \\ f^{'} (q_{0}, c) & = DOM (f (DOM (q_{0}), c)) = DOM (q_{2}) = {q_{2}} \\ f^{'} (q_{1}, a) & = DOM (f (DOM (q_{1}), a)) = DOM (\emptyset) = \emptyset \\ f^{'} (q_{1}, b) & = DOM (f (DOM (q_{1}), b)) = DOM (q_{1}) = {q_{1}, q_{2}} \\ f^{'} (q_{1}, c) & = DOM (f (DOM (q_{1}), c)) = DOM (q_{2}) = {q_{2}} \\ f^{'} (q_{2}, a) & = DOM (f (DOM (q_{2}), a)) = DOM (\emptyset) = \emptyset \\ f^{'} (q_{2}, b) & = DOM (f (DOM (q_{2}), b)) = DOM (\emptyset) = \emptyset \\ f^{'} (q_{2}, c) & = DOM (f (DOM (q_{2}), c)) = DOM (q_{2}) = {q_{2}} \end{aligned}

Rezultatem działania algorytmu jest więc automat bez p-przejść, pokazany na rysunku 5.

Ćwiczenie 5

Udowodnij, że dla każdego automatu z p-przejściami istnieje automat z p-przejściami o jednoelementowym zbiorze stanów początkowych $I$ .

Rozwiązanie

Niech $𝒜 = (S, A, f, I, F)$ będzie automatem z

p-przejściami. Zdefiniujmy automat

ℬ = (S \cup {s_{*}}, A, f^{'}, {s_{*}}, F)

,

gdzie $s_{*}$ jest nowym stanem dołożonym do $S$ , $\forall s \in S \forall a \in A \cup {1} f^{'} (s, a) = f (s, a)$ oraz $f^{'} (s_{*}, 1) = I$ . Widać, że $L (𝒜) = L (ℬ)$ .

Ćwiczenie 6

Niech $𝒜 = (S, A, f, I, T)$ będzie automatem z p-przejściami o następującej własności:

\forall s_{1}, s_{2} \in S s_{2} \in f (s_{1}, 1)

.

Załóżmy ponadto, że $I$ oraz $T$ są dowolnymi niepustymi podzbiorami $S$ oraz że w $𝒜$ dla każdego $a \in A$ istnieje dokładnie jedna para stanów $s_{1}, s_{2}$ taka, że $s_{2} \in f (s_{1}, a)$ . Jaki język akceptuje automat $𝒜$ ?

Rozwiązanie

Automat akceptuje język $A^{*}$ . Aby to pokazać, ustalmy słowo $w \in A^{*}$ i pokażemy, że $w \in L (𝒜)$ . Niech $w = a_{1} a_{2} . . . a_{n}$ , $n \geq 0$ , $\forall 1 \leq i \leq n a_{i} \in A$ . Wybierzmy dowolny stan początkowy $i \in I$ . Niech dla dowolnego $k = 1, 2, . . ., n$ stan $s_{k}$ będzie tym stanem, dla którego zachodzi $f (s_{k}, a_{k}) = \emptyset$ . Z założenia mamy, że $s_{1} \in f (i, 1)$ . Możemy więc przejść słowem 1 ze stanu początkowego do stanu $s_{1}$ . Następnie przechodzimy pod wpływem $a_{1}$ do stanu $f (s_{1}, a_{1})$ . Zauważmy, że z założenia istnieje tylko jeden stan, do którego możemy w ten sposób przejść. Teraz dla każdego $k > 1$ możemy przejść słowem 1 ze stanu $f (s_{k - 1}, a_{k - 1}$ do stanu $s_{k}$ , a następnie pod wpływem litery $a_{k}$ do stanu $a_{k + 1}$ . Po przejściu do stanu $f (s_{n}, a_{n})$ przechodzimy słowem 1 do dowolnego stanu końcowego. Możemy to zrobić, gdyż dla dowolnego $i \in I$ z założenia mamy $i \in f (f (s_{n}, a_{n}), 1)$ . Ostatecznie przeszliśmy ścieżkę $1^{t_{1}} a_{1} 1^{t_{2}} a_{2} . . . 1^{t_{n}} a_{n} 1^{t_{n + 1}} = a_{1} a_{2} . . . a_{n} = w$ , gdzie $t_{i}$ są pewnymi liczbami naturalnymi lub są równe 0. Ponieważ powyższą procedurę możemy zastosować do dowolnego $w \in A^{*}$ , zatem $L (𝒜) = A^{*}$ , co mieliśmy dowieść.

Ćwiczenie 7

Niech $A = {a, b}$ . Wykorzystując lemat o pompowaniu udowodnij, że następujące języki nie są akceptowane:

$L = {a^{n} b^{m} : 0 \leq n \leq m}$
$L = {w \in A^{*} : #_{a} w = #_{b} w}$
$L = {w \overset{\leftarrow}{w} : w \in A^{*}}$ , gdzie dla $w = a_{1} . . . a_{n} \in A^{*}$ $\overset{\leftarrow}{w} = a_{n} . . a_{1}$ .

Słowo $\overset{\leftarrow}{w}$ nazywamy odbiciem zwierciadlanym słowa $w$ .

Rozwiązanie

We wszystkich przypadkach dowód przeprowadzimy nie

wprost, zakładając, że język $L$ jest rozpoznawany przez automat, a więc spełnia tezę lematu o pompowaniu.
Punkt 1. Rozważmy słowo $a^{n} b^{n} \in L$ , gdzie $2 n \geq N$ . Podobnie jak w przykładzie 1.1 w wykładzie 6 (patrz przykład 1.1. w wykładzie 6) pokazujemy, że nie istnieją słowa $v_{1}, v_{2} \in {a, b}^{*}$ oraz $u \in {a, b}^{+}$ takie, że

a^{n} b^{n} = v_{1} u v_{2} i \forall i \in ℕ_{0} v_{1} u^{i} v_{2} \in L

.

Punkt 2. Jeśli przyjmiemy $u = a b$ lub u= $b a$ , to dla dowolnego dostatecznie długiego słowa $w \in L$ istnieją podsłowa $v_{1}, v_{2} \in A^{*}$ takie, że

w = v_{1} u v_{2}

i

\forall i \in ℕ_{0} v_{1} u^{i} v_{2} \in L

.

Warunek pompowania jest więc spełniony. Natomiast nie dla wszystkich słów z języka jest spełniony warunek ograniczający długość $v_{1} u$ . Np. dla $n > N$ słowo $a^{n} b^{n} \in L$ , ale $| v_{1} u | > N$ .
Punkt 3. Jedynym możliwym rozkładem słowa $a_{1} . . . a_{n} a_{n} . . . a_{1}$ spełniającym warunek pompowania jest $v_{1} = a_{1} . . a_{k}$ dla pewnego $k = 1, . ., n - 1$ , $v_{2} = \overset{\leftarrow}{v_{1}}$ , $u = a_{k + 1} . . . a_{n} a_{n} . . . a_{k + 1}$ . Jednak dla $n > N | v_{1} u | = | a_{1} . . . a_{n} a_{n} . . . a_{k + 1} | > N$

Ćwiczenie 8

Wykorzystując lemat o pompowaniu udowodnij, że następujące języki nie są akceptowane:

$L = {a^{n} : n jest liczbą pierwszą}$ ,
$L = {a^{n!} : n \geq 1}$ .

Rozwiązanie

Tak samo jak w zadaniu 1 dowód przeprowadzimy nie wprost, zakładając, że język

L

jest

rozpoznawany przez automat, a więc spełnia tezę lematu o pompowaniu. Zauważmy, że dla języków nad alfabetem jednoelementowym warunek pompowania z lematu ma postać

\forall n \geq N : : a^{n} \in L \exists p \geq 0, \exists k > 0

takie, że

n = p + k oraz \forall i \in ℕ_{0} a^{p + i k} \in L

.

Wykładniki słów utworzonych dla kolejnych indeksów $i$ tworzą ciąg arytmetyczny.
Punkt 1. Dla każdej liczby pierwszej $n \geq N$ istnieje liczba pierwsza $p \geq 0$ i liczba $k > 0$ takie, że

n = p + k oraz \forall i \in ℕ_{0} n_{i} = p + i k jest liczbą pierwszą

Dla

i = p

n_{p} = (k + 1) p nie jest liczbą pierwszą.

Punkt 2. Dla każdej liczby $n \geq N$ istnieje $p \geq 0$ i $k > 0$ takie, że

n! = p + k oraz \forall i \in ℕ_{0} \exists n_{i} : n_{i}! = p + i k

Dla $i > 0$ mamy następujące nierówności

n_{i}! < n_{i}! + k = n_{i + 1}! < 2 n_{i}! < (n_{i} + 1)!

.

Nierówności

n_{i}! < n_{i + 1}! < (n_{i} + 1)!

są sprzeczne.

ZADANIA DOMOWE

Ćwiczenie 9

Dla następujących automatów określ równoważne automaty deterministyczne.

Ćwiczenie 10

Ustalmy $n > 0$ oraz $a_{1}, a_{2}, . . ., a_{n} \in A = {a, b}$ . Udowodnij, że automat deterministyczny (obliczony algorytmem determinizacji z wykładu) równoważny automatowi niedeterministycznemu $ℬ$ z rysunku 9, rozpoznającemu język

L = A^{*} a_{1} A^{*} a_{2} . . . A^{*} a_{n} A^{*}

, posiada tyle samo stanów co

ℬ

.

Rysunek 9

Wskazówka

Porównaj ćwiczenie 1 (patrz ćwiczenie 1) Wynika to wprost z algorytmu determinizacji. Oznaczmy zbiór stanów automatu niedeterministycznego $ℬ$ przez $S$ . Niech $S = {s_{1}, s_{2}, . . ., s_{n}, s_{n + 1}}$ . Wystarczy zauważyć, że w $i$ -tym kroku działania, tzn. w momencie dodawania $i$ -tego stanu w budowanym automacie deterministycznym $(i \leq n)$ , pozostałe $i - 1$ stany mają etykiety $e_{1} = {s_{1}}$ , $e_{2} = {s_{1}, s_{2}}$ , ..., $e_{i - 1} = {s_{1}, s_{2}, . . ., s_{i - 1}}$ , a funkcja przejść określona na nich ma postać: $f (e_{j}, a) = e_{j + 1}$ , jeśli $a = a_{j}$ , $f (e_{j}, a) = e_{j}$ , jeśli $a = a_{j}$ ( $1 \leq j \leq i - 2$ ). Ten fakt można w prosty sposób dowieść indukcyjnie ze względu na $i$ . Dla dodawanego $n + 1$ -szego stanu $e_{n + 1}$ funkcja przejść będzie natomiast zdefiniowana następująco: $f (e_{n + 1}, a) = e_{n + 1} \forall a \in A$ . Zatem w ostatnim, $n + 1$ kroku, automat deterministyczny będzie miał $n + 1$ stanów, czyli tyle samo co automat $ℬ$ . Algorytm zakończy w tym momencie działanie. Automat deterministyczny przedstawiony jest na rysunku 10.

Rysunek 10

Ćwiczenie 11

Niech $ℬ = (S^{'}, A, f^{'}, s_{0}, T)$ będzie automatem deterministycznym dla automatu niedeterministycznego $𝒜 = (S, A, f, s_{0}, T)$ . Czy zbiór stanów $S^{'}$ automatu deterministycznego obliczonego za pomocą algorytmu Determinizacja zależy od:

wyboru w $𝒜$ stanu początkowego $s_{0}$ ,
wyboru w $𝒜$ zbioru stanów końcowych $T$ ?

Ćwiczenie 12

Używając algorytmu UsuńPustePrzejścia, przekształć automat z rysunku 11 w równoważny automat niedeterministyczny bez p-przejść, a następnie zdeterminizuj go przy

użyciu algorytmu Determinizacja.

Ćwiczenie 13

Wykorzystując lemat o pompowaniu udowodnij, że następujące języki nie są akceptowane:

$L = {a^{n^{2}} : n \geq 0}$ ,
$L = {a^{2^{n}} : n \geq 0}$ ,
$L = {a^{n} b^{m} : 0 < n < m}$ ,
$L = {a^{n} b^{m} c^{n + m} : n, m > 0}$ ,
$L = {w w : w \in A^{*}}$ dla dowolnego alfabetu $A$ ,
$L = {w \in A^{*} : | w | = n^{2}, n \in ℕ}$ dla dowolnego alfabetu $A$ .

Języki, automaty i obliczenia/Ćwiczenia 6: Automat niedeterministyczny. Lemat o pompowaniu

Ćwiczenia 6

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia