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

From Studia Informatyczne

Ćwiczenia 6

Ćwiczenie 1

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

Rozwiązanie

Automat niedeterministyczny pokazany jest na rysunku 1.

<flash>file=ja-lekcja06-c-rys1.swf|width=250|height=100</flash>

Rysunek 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 \displaystyle L mają po tyle samo stanów.

Ćwiczenie 2

Zastosuj algorytm Determinizacja podany na wykładzie do

determinizacji automatu z rysunku 2.



Rysunek 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 \displaystyle S', określenie funkcji przejść \displaystyle f' oraz stany dodane do zbioru stanów końcowych \displaystyle T'.


\displaystyle \begin{array} {c|c|c|c|c|} Krok & dodane\quad do\quad S' & okreslenie\quad f' & dodane\quad do\quad T'\\ \hline 0 & \{q_0\} &  & \emptyset\\ \hline 1 & \{q_0,q_3\} & f'(\{q_0\},a)=\{q_0,q_3\} & \emptyset\\ \hline  & \{q_0,q_1\} & f'(\{q_0\},b)=\{q_0,q_1\} & \\ \hline 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\}\\ \hline  &  & f'(\{q_0,q_3\},b)=\{q_0,q_1\} & \\ \hline  &  & f'(\{q_0,q_1\},a)=\{q_0,q_3\} & \\ \hline  & \{q_0,q_1,q_2\} & f'(\{q_0,q_1\},b)=\{q_0,q_1,q_2\} & \{q_0,q_1,q_2\}\\ \hline 3 &  & f'(\{q_0,q_3,q_4\},a)=\{q_0,q_3,q_4\} & \\ \hline  & \{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\}\\ \hline  & \{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\}\\ \hline  &  & f'(\{q_0,q_1,q_2\},b)=\{q_0,q_1,q_2\} & \\ \hline 4 &  & f'(\{q_0,q_1,q_4\},a)=\{q_0,q_3,q_4\} & \\ \hline  & \{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\}\\ \hline  & \{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\}\\ \hline  &  & f'(\{q_0,q_2,q_3\},b)=\{q_0,q_1,q_2\} & \\ \hline 5 &  & f'(\{q_0,q_1,q_2,q_4\},a)=\{q_0,q_2,q_3,q_4\} & \\ \hline  &  & f'(\{q_0,q_1,q_2,q_4\},b)=\{q_0,q_1,q_2,q_4\} & \\ \hline  &  & f'(\{q_0,q_2,q_3,q_4\},a)=\{q_0,q_2,q_3,q_4\} & \\ \hline  &  & f'(\{q_0,q_2,q_3,q_4\},b)=\{q_0,q_1,q_2,q_4\} & \\ \hline \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 \displaystyle Q. Na przykład, zamiast \displaystyle \{q_0,q_1,q_2\} stan etykietowany jest wyrażeniem \displaystyle 012.

<flash>file=ja-lekcja06-c-rys3.swf|width=250|height=250</flash>

Rysunek 3

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

Ćwiczenie 3

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

Rozwiązanie

Niech \displaystyle \mathcal{A}=(S=\{s_0,...,s_{n-1}\}, A=\{a,b,c\}, f, s_0, T) będzie automatem niedeterministycznym (\displaystyle T jest dowolnym podzbiorem \displaystyle S). Zdefiniujmy funkcję \displaystyle f: S \times A \rightarrow \mathcal{P}(S) następująco:

\displaystyle \aligned \forall 0 \leq i \leq n-1\ f(s_i,a) &= \{s_{i-1\ mod\ n}\}, \\ f(s_0, b) &= \{s_0, s_1\}, \\ \forall 1 \leq i \leq n-1 f(s_i,b) &= \{s_{i+1\ mod\ n}\}, \\ f(s_0, c) &= \{s_1\}, \\ \forall 1 \leq i \leq n-1 f(s_i, c) &= \{s_i\}. \endaligned

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

Zauważmy, że \displaystyle f(s_0, b^{n-1})=S. Niech początek szukanego słowa \displaystyle w

ma postać \displaystyle b^{n-1}. Będziemy redukować ilość stanów zbioru \displaystyle f(s_0,b^{n-1}) poprzez doklejanie liter \displaystyle c, oraz "przesuwać" układ aktualnie występujących stanów używając liter \displaystyle a.

Niech \displaystyle S'=f(s_0,wv), gdzie

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

Aby otrzymać żądany zbiór \displaystyle W wystarczy "przesunąć" ten zbiór

stanów przy pomocy słowa \displaystyle a^{n-i_1}. Ostatecznie:

\displaystyle f(s_0, wva^{n-i_1})=W.

Ponieważ powyższym sposobem możemy uzyskać dowolny niepusty podzbiór \displaystyle W zbioru stanów \displaystyle S, zatem zbiór stanów \displaystyle R automatu deterministycznego musi zawierać stany odpowiadające wszystkim niepustym podzbiorom zbioru \displaystyle S, czyli \displaystyle |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 \displaystyle \mathcal{A}=(S, A, f, I, F) będzie niedeterministycznym automatem z p-przejściami. Dla stanu \displaystyle s \in S zbiór

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

nazywamy pustym domknięciem stanu \displaystyle s.

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

Dla dowolnego \displaystyle P \subseteq S określamy

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



Ćwiczenie 4

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



Rysunek 4

Rozwiązanie

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

\displaystyle S'=\{q_0,q_1,q_2\},\ I'=I=\{q_0\}


\displaystyle \aligned \nonumber \mbox{DOM}(q_0) &= \{q_0,q_1,q_2\} \\ \nonumber \mbox{DOM}(q_1) &= \{q_1,q_2\} \\ \nonumber \mbox{DOM}(q_2) &= \{q_2\} \endaligned


\displaystyle F'=\{s \in S:\ \{q_2\} \cap \mbox{DOM}(s) \not = \mbox{\O}\}=\{q_0,q_1,q_2\}


\displaystyle \aligned \nonumber f'(q_0,a) & = \mbox{DOM}(f(\mbox{DOM}(q_0),a)) = \\ \nonumber &= \mbox{DOM}(f(\{q_0,q_1,q_2\},a)) = \mbox{DOM}(q_0 \cup \mbox{\O} \cup \mbox{\O}) \\ \nonumber &= \mbox{DOM}(q_0)=\{q_0,q_1,q_2\}. \endaligned

W analogiczny sposób obliczamy:

\displaystyle \aligned \nonumber f'(q_0,b) &= \mbox{DOM}(f(\mbox{DOM}(q_0),b)) = \mbox{DOM}(q_1) = \{q_1,q_2\} \\ \nonumber f'(q_0,c) &= \mbox{DOM}(f(\mbox{DOM}(q_0),c)) = \mbox{DOM}(q_2) = \{q_2\} \\ \nonumber f'(q_1,a) &= \mbox{DOM}(f(\mbox{DOM}(q_1),a)) = \mbox{DOM}(\mbox{\O}) = \mbox{\O} \\ \nonumber f'(q_1,b) &= \mbox{DOM}(f(\mbox{DOM}(q_1),b)) = \mbox{DOM}(q_1) = \{q_1,q_2\} \\ \nonumber f'(q_1,c) &= \mbox{DOM}(f(\mbox{DOM}(q_1),c)) = \mbox{DOM}(q_2) = \{q_2\} \\ \nonumber f'(q_2,a) &= \mbox{DOM}(f(\mbox{DOM}(q_2),a)) = \mbox{DOM}(\mbox{\O}) = \mbox{\O} \\ \nonumber f'(q_2,b) &= \mbox{DOM}(f(\mbox{DOM}(q_2),b)) = \mbox{DOM}(\mbox{\O}) = \mbox{\O} \\ \nonumber f'(q_2,c) &= \mbox{DOM}(f(\mbox{DOM}(q_2),c)) = \mbox{DOM}(q_2) = \{q_2\} \endaligned

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

<flash>file=ja-lekcja06-c-rys5.swf|width=250|height=150</flash>

Rysunek 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 \displaystyle I.

Rozwiązanie

Niech \displaystyle \mathcal{A}=(S, A, f, I, F) będzie automatem z

p-przejściami. Zdefiniujmy automat
\displaystyle \mathcal{B}=(S \cup \{s_*\}, A, f', \{s_*\}, F),

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

Ćwiczenie 6

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

\displaystyle \forall s_1, s_2 \in S\ s_2 \in f(s_1,1).

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

Rozwiązanie

Automat akceptuje język \displaystyle A^*. Aby to pokazać, ustalmy słowo \displaystyle w \in A^* i pokażemy, że \displaystyle w \in L(\mathcal{A}). Niech \displaystyle w=a_1a_2...a_n, \displaystyle n \geq 0, \displaystyle \forall 1 \leq i \leq n\ a_i \in A. Wybierzmy dowolny stan początkowy \displaystyle i \in I. Niech dla dowolnego \displaystyle k=1, 2, ..., n stan \displaystyle s_k będzie tym stanem, dla którego zachodzi \displaystyle f(s_k, a_k) \not = \emptyset. Z założenia mamy, że \displaystyle s_1 \in f(i, 1). Możemy więc przejść słowem 1 ze stanu początkowego do stanu \displaystyle s_1. Następnie przechodzimy pod wpływem \displaystyle a_1 do stanu \displaystyle 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 \displaystyle k>1 możemy przejść słowem 1 ze stanu \displaystyle f(s_{k-1},a_{k-1} do stanu \displaystyle s_k, a następnie pod wpływem litery \displaystyle a_k do stanu \displaystyle a_{k+1}. Po przejściu do stanu \displaystyle f(s_n, a_n) przechodzimy słowem 1 do dowolnego stanu końcowego. Możemy to zrobić, gdyż dla dowolnego \displaystyle i \in I z założenia mamy \displaystyle i \in f(f(s_n, a_n), 1). Ostatecznie przeszliśmy ścieżkę \displaystyle 1^{t_1}a_11^{t_2}a_2...1^{t_n}a_n1^{t_{n+1}}=a_1a_2...a_n=w, gdzie \displaystyle t_i są pewnymi liczbami naturalnymi lub są równe 0. Ponieważ powyższą procedurę możemy zastosować do dowolnego \displaystyle w \in A^*, zatem \displaystyle L(\mathcal{A})=A^*, co mieliśmy dowieść.

Ćwiczenie 7

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

  1. \displaystyle L=\left\{ a^{n}b^{m}:0\leq n\leq m\right\},
  2. \displaystyle L=\left\{ w\in A^{*}:\#_{a}w=\#_{b}w\right\},
  3. \displaystyle L=\left\{ w\overleftarrow{w} : w \in A^{*}\right\}, gdzie dla \displaystyle w=a_1...a_n \in A^*
    \displaystyle \overleftarrow{w}=a_n..a_1.

Słowo \displaystyle \overleftarrow{w} nazywamy odbiciem zwierciadlanym słowa \displaystyle w.

Rozwiązanie

We wszystkich przypadkach dowód przeprowadzimy nie

wprost, zakładając, że język \displaystyle L jest rozpoznawany przez automat, a więc spełnia tezę lematu o pompowaniu.
Punkt 1. Rozważmy słowo \displaystyle  a^{n}b^{n} \in L, gdzie \displaystyle 2n \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 \displaystyle v_1,v_2 \in \{a,b\}^* oraz \displaystyle u \in \{a,b\}^+ takie, że

\displaystyle a^{n}b^{n} = v_1 uv_2  \; \text{i} \; \forall i \in \mathbb{N}_0\;v_1 u^i v_2 \in L.

Punkt 2. Jeśli przyjmiemy \displaystyle u=ab lub u=\displaystyle ba, to dla dowolnego dostatecznie długiego słowa \displaystyle w\in L istnieją podsłowa \displaystyle v_1,v_2 \in A^* takie, że

\displaystyle w=v_1 uv_2 i
\displaystyle \forall i \in \mathbb{N}_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ść \displaystyle v_1u. Np. dla \displaystyle n>N słowo \displaystyle a^nb^n \in L, ale \displaystyle |v_1u|>N.
Punkt 3. Jedynym możliwym rozkładem słowa \displaystyle a_1...a_na_n...a_1 spełniającym warunek pompowania jest \displaystyle v_1=a_1..a_k dla pewnego \displaystyle k=1,..,n-1, \displaystyle v_2=\overleftarrow{v_1}, \displaystyle u=a_{k+1}...a_na_n...a_{k+1}. Jednak dla \displaystyle n>N\displaystyle |v_1u|=|a_1...a_na_n...a_{k+1}|>N

Ćwiczenie 8

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

  1. \displaystyle L = \{a^n : n \; \text{ jest liczbą pierwszą} \},
  2. \displaystyle L=\left\{ a^{n!}: n \geq 1 \right\}.

Rozwiązanie

Tak samo jak w zadaniu 1 dowód przeprowadzimy nie wprost, zakładając, że język \displaystyle 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ć

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

takie, że

\displaystyle n=p+k \;\; \text{oraz}\;\; \forall i \in \mathbb{N}_0\; a^{ p+ik} \in L.

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

\displaystyle n=p+k \;\; \text{oraz}\;\; \forall i \in \mathbb{N}_0\; n_i = p+ik \;\text{jest liczbą pierwszą}
Dla \displaystyle i=p
\displaystyle n_p=(k+1)p \; \text { nie jest liczbą pierwszą.}

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

\displaystyle n!=p+k \;\; \text{oraz}\;\; \forall i \in \mathbb{N}_0\; \exists n_i \;:\;  n_i != p+ik

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

\displaystyle n_i !<n_i! +k=n_{i+1} ! <2n_i !<(n_i +1)!.

Nierówności

\displaystyle 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.


Rysunek 6


Rysunek 7


Rysunek 8

Ćwiczenie 10

Ustalmy \displaystyle n>0 oraz \displaystyle 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 \displaystyle \mathcal{B} z rysunku 9, rozpoznającemu język

\displaystyle L=A^*a_1A^*a_2...A^*a_nA^*, posiada tyle samo stanów co \displaystyle \mathcal{B}.



Rysunek 9

Wskazówka

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



Rysunek 10

Ćwiczenie 11

Niech \displaystyle \mathcal{B}=(S', A, f', s_0, T) będzie automatem deterministycznym dla automatu niedeterministycznego \displaystyle \mathcal{A}=(S, A, f, s_0, T). Czy zbiór stanów \displaystyle S' automatu deterministycznego obliczonego za pomocą algorytmu Determinizacja zależy od:

  1. wyboru w \displaystyle \mathcal{A} stanu początkowego \displaystyle s_0,
  2. wyboru w \displaystyle \mathcal{A} zbioru stanów końcowych \displaystyle 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.



Rysunek 11

Ćwiczenie 13

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

  1. \displaystyle L = \{a^{n^2} : n \geq 0 \},
  2. \displaystyle L=\left\{ a^{2^{n}}: n \geq 0 \right\},
  3. \displaystyle L=\left\{ a^{n}b^{m}:0<n<m \right\},
  4. \displaystyle L=\left\{ a^{n}b^{m}c^{n+m}:n,m>0\right\},
  5. \displaystyle L=\left\{ ww : w \in A^{*}\right\} dla dowolnego alfabetu \displaystyle A,
  6. \displaystyle L=\left\{  w \in A^{*} : |w|=n^2, n \in \mathbb{N} \right\} dla dowolnego alfabetu \displaystyle A.