Test GR3: Różnice pomiędzy wersjami

Wersja z 12:58, 17 sie 2006

{theor}{TWIERDZENIE}[section] {rem}{UWAGA}[section] {corol}{WNIOSEK}[section] {fact}{FAKT}[section] {ex}{PRZYKŁAD}[section] {defin}{DEFINICJA}[section] {lem}{LEMAT}[section]

{prf}{DOWÓD}

{algorithm}{Algorytm}

{ Automat niedeterministyczny, lemat o pompowaniu}

Wprowadzenie: W tym wykładzie

zdefiniujemy automat niedeterministyczny, udowodnimy jego równoważność z automatem deterministycznym oraz podamy algorytm konstrukcji równoważnego automatu deterministycznego. Wprowadzimy także automaty niedeterministyczne z pustymi przejściami. W ostatniej części wykładu sformułujemy lemat o pompowaniu dla języków rozpoznawanych przez automaty skończenie stanowe.

Słowa kluczowe: automat niedeterministyczny, automat niedeterministyczny z pustymi

przejściami, lemat o pompowaniu.

Automat niedeterministyczny

Wprowadzony wcześniej automat jest modelem obliczeń, czy też mówiąc ogólniej, modelem procesu o bardzo prostym opisie. Stan procesu zmienia się w sposób jednoznaczny pod wpływem sygnału zewnętrznego reprezentowanego przez literę alfabetu. Opisem tych zmian jest więc funkcja. Pewnym uogólnieniem powyższej sytuacji może być dopuszczenie relacji, która opisuje zmiany stanu. W efekcie opis zmiany stanów staje się niedeterministyczny w tym sensie, że z danego stanu automat przechodzi w pewien zbiór stanów. Jak udowodnimy pó{z}niej, z punktu widzenia rozpoznawania lub poprawnych obliczeń, takie uogólnienie nie rozszerza klasy języków rozpoznawanych przez automaty.

Automatem niedeterministycznym nad alfabetem $A$ nazywamy

system

𝒜_{N D}

= (S,f),Parser nie mógł rozpoznać (błąd składni): {\displaystyle w którym } SParser nie mógł rozpoznać (błąd składni): {\displaystyle jest dowolnym zbiorem, zwanym zbiorem stanów, a } f: S A {P}(S) Parser nie mógł rozpoznać (błąd składni): {\displaystyle funkcją przejść. \enddefin Funkcję przejść rozszerzamy do funkcji } f: S A^* {P}(S) Parser nie mógł rozpoznać (błąd składni): {\displaystyle określonej na całym wolnym monoidzie } A^*Parser nie mógł rozpoznać (błąd składni): {\displaystyle w następujący sposób: dla każdego } s S f(s,1) = s, Parser nie mógł rozpoznać (błąd składni): {\displaystyle dla każdego } s S, a A

o r a z d o w o l n e g o

w A^* f(s,wa)=f(f(s,w),a) .Parser nie mógł rozpoznać (błąd składni): {\displaystyle Zwróćmy uwagę, że prawa strona ostatniej równości to obraz przez funkcję } f

z b i o r u

f(s,w)

i l i t e r y

aParser nie mógł rozpoznać (błąd składni): {\displaystyle . Funkcję przejść automatu niedeterministycznego można także traktować jako relację } f (S A^*) S.

Parser nie mógł rozpoznać (błąd składni): {\displaystyle W związku z powyższą definicją automat wprowadzony wcześniej, w wykładzie 3, będziemy nazywać automatem deterministycznym\index{automat deterministyczny}. \begindefin Język } L A^{*} Parser nie mógł rozpoznać (błąd składni): {\displaystyle jest rozpoznawalny przez automat nie\-de\-ter\-mi\-nis\-tycz\-ny } {A}_{ND} =(S,f)Parser nie mógł rozpoznać (błąd składni): {\displaystyle wtedy i tylko wtedy, gdy istnie\-je } I SParser nie mógł rozpoznać (błąd składni): {\displaystyle -- zbiór stanów początkowych oraz } F SParser nie mógł rozpoznać (błąd składni): {\displaystyle - zbiór stanów końcowych taki, że }

L =w A^* : f(I,w) F .

Parser nie mógł rozpoznać (nieznana funkcja „\enddefin”): {\displaystyle \enddefin Niedeterministyczny automat rozpoznający język } LParser nie mógł rozpoznać (błąd składni): {\displaystyle będziemy oznaczać jako system } {A}_{ND} = (S,A,f,I,F)

l u b

{A}_{ND}=(S,f,I,F), Parser nie mógł rozpoznać (błąd składni): {\displaystyle jeśli wiadomo, nad jakim alfabetem określono automat. Na pierwszy rzut oka mogłoby się wydawać, że wprowadzony automat istotnie rozszerza możliwości automatu deterministycznego, że jego moc obliczeniowa jest istotnie większa. Okazuje się jednak, że z punktu widzenia rozpoznawania języków, czyli właśnie z punktu widzenia mocy obliczeniowej, automaty deterministyczne i niedeterministyczne są rów\-no\-waż\-ne. \begintheor Język } L A^*Parser nie mógł rozpoznać (błąd składni): {\displaystyle jest rozpoznawany przez automat deter\-mi\-nis\-tycz\-ny wtedy i tylko wtedy, gdy jest rozpoznawany przez automat nie\-de\-ter\-mi\-nis\-tycz\-ny. \endtheor \beginprf Rozpocznijmy dowód od oczywistej obserwacji. Zauważmy, iż każdy automat deterministyczny można przekształcić w nie\-de\-ter\-mi\-nis\-tycz\-ny, modyfikując funkcję przejść w ten sposób, że jej wartościami są zbiory jednoelemen\-to\-we. Modyfikacja ta prowadzi w konsekwencji do równoważnego automatu niedeterministycznego. Dla dowodu implikacji w stronę przeciwną załóżmy, że język } L=L({A}_{ND})

, g d z i e

{A}_{ND} =

(S,f,I,F)Parser nie mógł rozpoznać (błąd składni): {\displaystyle , jest automatem niedeterministycznym. Określamy teraz równoważny, jak się okaże, automat deterministyczny. Jako zbiór stanów przyjmujemy } {P}(S) Parser nie mógł rozpoznać (błąd składni): {\displaystyle , czyli ogół podzbiorów zbioru } SParser nie mógł rozpoznać (błąd składni): {\displaystyle . Funkcję przejść } {f}:{P}(S) A^{*} {P}(S) Parser nie mógł rozpoznać (błąd składni): {\displaystyle określamy kładąc dla dowolnego stanu } S_1 {P}(S) $o r a z d o w o l n e j l i t e r y$

a A

{f} (S_1 ,a) = _{s S_1} f(s,a),

Parser nie mógł rozpoznać (błąd składni): {\displaystyle a następnie rozszerzamy ją do } A^{*} Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Łatwo sprawdzić, że funkcja } {f}Parser nie mógł rozpoznać (błąd składni): {\displaystyle spełnia warunki funkcji przejść. Przyjmując następnie zbiór } I {P}(S) Parser nie mógł rozpoznać (błąd składni): {\displaystyle jako stan początkowy oraz zbiór } T= {S}_{1} {P}(S) : S_{1} F

Parser nie mógł rozpoznać (błąd składni): {\displaystyle , jako zbiór stanów końcowych stwierdzamy, dla określo\-ne\-go automatu } {A}_{D}=(

{P}(S),{f},I,T) Parser nie mógł rozpoznać (błąd składni): {\displaystyle , równość }

L({A}_{D})=w A^{*}: {f}(I,w) T=L=L({A}_{ND}).

Parser nie mógł rozpoznać (błąd składni): {\displaystyle Skonstruowany automat jest zatem deterministyczny i równoważny wyjściowemu, co kończy dowód twierdzenia. \begincenter \endcenter \endprf {{uwaga|[Uzupelnij]|| Dla określonego w dowodzie automatu } {A}_{D} Parser nie mógł rozpoznać (błąd składni): {\displaystyle na ogół nie wszystkie stany są osiągalne ze stanu } IParser nie mógł rozpoznać (błąd składni): {\displaystyle . Aby uniknąć takich stanów, które są bezużyteczne, funkcję przejść należy zacząć definiować od stanu } IParser nie mógł rozpoznać (błąd składni): {\displaystyle i kolejno określać wartości dla już osiągniętych stanów. }} {{cwiczenie|[Uzupelnij]|| Automat } {A}_{ND} = (Q,A,f,I,F)

n a d a l f a b e t e m

A=a,b Parser nie mógł rozpoznać (błąd składni): {\displaystyle określony przez zbiory } Q=q_{0},q_{1},q_{2},q_4 , I=q_0, F=q_{3} Parser nie mógł rozpoznać (błąd składni): {\displaystyle i zadany poniższym grafem jest przykładem automatu niedeterministycznego.\\ RYSUNEK ja-lekcja6-w-rys1 Automat ten, jak łatwo teraz zauważyć, rozpoznaje język } L({A})=A^*abb Parser nie mógł rozpoznać (błąd składni): {\displaystyle . }} Przedstawimy teraz algorytm, który mając na wejściu automat niedeterministyczny konstruuje równoważny automat deterministyczny. \newpage \beginalgorithm \caption{\textsc{Determinizacja} -- buduje deterministyczny automat równoważny automatowi niedeterministycznemu} \beginalgorithmic [1] \STATE Wejście: } {A}=(S, A, f, s_0, T)Parser nie mógł rozpoznać (nieznana funkcja „\STATE”): {\displaystyle -- automat niedeterministyczny. \STATE Wyjście: } {A}'=(S', A, f', s_0', T')Parser nie mógł rozpoznać (błąd składni): {\displaystyle -- automat deterministyczny taki, że } L({A}')=L({A})Parser nie mógł rozpoznać (nieznana funkcja „\STATE”): {\displaystyle . \STATE } S' s_0Parser nie mógł rozpoznać (nieznana funkcja „\STATE”): {\displaystyle ; \STATE } s_0' s_0Parser nie mógł rozpoznać (nieznana funkcja „\STATE”): {\displaystyle ; \STATE } {L} s_0Parser nie mógł rozpoznać (nieznana funkcja „\hfill”): {\displaystyle ; \hfill } {L}Parser nie mógł rozpoznać (błąd składni): {\displaystyle jest kolejką \WHILE{} {L} = Parser nie mógł rozpoznać (nieznana funkcja „\STATE”): {\displaystyle } \STATE } M

zdejmij({L})Parser nie mógł rozpoznać (nieznana funkcja „\STATE”): {\displaystyle ; \STATE \textbf{if } } T M = $then$ T' T' MParser nie mógł rozpoznać (nieznana funkcja „\FOR”): {\displaystyle ; \FOR{\textbf{each} } a AParser nie mógł rozpoznać (nieznana funkcja „\STATE”): {\displaystyle } \STATE } N _{m M} f(m,a)Parser nie mógł rozpoznać (nieznana funkcja „\IF”): {\displaystyle ; \IF{} N S'Parser nie mógł rozpoznać (nieznana funkcja „\STATE”): {\displaystyle } { \STATE } S' S' NParser nie mógł rozpoznać (nieznana funkcja „\STATE”): {\displaystyle ; \STATE \textbf{włóż}} ({L},N)Parser nie mógł rozpoznać (nieznana funkcja „\ENDIF”): {\displaystyle ; } \ENDIF \STATE } f'(M, a) NParser nie mógł rozpoznać (nieznana funkcja „\ENDFOR”): {\displaystyle ; \ENDFOR \ENDWHILE \RETURN } {A}'Parser nie mógł rozpoznać (nieznana funkcja „\endalgorithmic”): {\displaystyle ; \endalgorithmic \endalgorithm Funkcja \textbf{zdejmij}, występująca w linii [[##a1_l6|Uzupelnic a1_l6|]]., zdejmuje z kolejki element znajdujący się na jej początku i zwraca go jako swoją wartość. Procedura \textbf{włóż}} ({L},N)Parser nie mógł rozpoznać (błąd składni): {\displaystyle z linii [[##a1_l12|Uzupelnic a1_l12|]]. wstawia na koniec kolejki } {L} $e l e m e n t$ NParser nie mógł rozpoznać (błąd składni): {\displaystyle . Należy zauważyć, że algorytm determinizujący automat jest algorytmem eksponencjalnym. Stany wyjściowego automatu deterministycznego etykietowane są podzbiorami zbioru stanów } QParser nie mógł rozpoznać (błąd składni): {\displaystyle . Jeśli pewien stan } q'

Q'Parser nie mógł rozpoznać (błąd składni): {\displaystyle etykietowany jest zbiorem zawierającym stan końcowy z } F

, t o

q'Parser nie mógł rozpoznać (błąd składni): {\displaystyle staje się stanem końcowym w automacie } {A}'Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Z analizy algorytmu [[##alg_1|Uzupelnic alg_1|]] wynika, że w ogólności zbiór stanów wyjściowego automatu deterministycznego może osiągać wartość rzędu } O(2^n)

, g d z i e

nParser nie mógł rozpoznać (błąd składni): {\displaystyle jest ilością stanów automatu niedeterministycznego. Zastosujemy powyższy algorytm do uzyskania automatu deterministycznego równoważnego automatowi z przykładu 1.1. Kolejne etapy działania ilustruje zamieszczona tu animacja. ANIMACJA ja-lekcja6-w-anim1 ==Automaty niedeterministyczne z przejściami pustymi== Rozszerzenie definicji automatu skończenie stanowego do automatu niedeterministycznego nie spowodowało, jak wiemy, zwiększenia mocy obliczeniowej takich modeli. Nasuwać się może pytanie, czy dołączenie do tego ostatniego modelu możliwości wewnętrznej zmiany stanu, zmiany stanu bez ingerencji sygnału zewnetrznego, czyli bez czytania litery nie zwiększy rodziny jezyków rozpoznawanych. Model taki, zwany automatem z pustymi przejściami (w skrócie: automat z p-przejściami), zdefiniujemy poniżej. \begindefin \textbf{Automatem niedeterministycznym z pustymi przejściami} nad alfabetem } A Parser nie mógł rozpoznać (błąd składni): {\displaystyle nazy\-wa\-my system } {A}{^p}_{ND}

= (S, f),

w którym

S

jest dowolnym zbiorem, zwanym zbiorem

stanów, a $f : S \times (A \cup {1}) \to 𝒫 (S)$ funkcją przejść.

Uwaga [Uzupelnij]

Słowo puste $1$ występuje w powyższej definicji w dwóch rolach. Pierwsza, to znana nam rola elementu neutralnego katenacji słów. Druga, to rola jakby "dodatkowej" litery, która może powodować zmianę aktualnego stanu automatu na inny. Ponieważ słowo puste może wystąpić przed i po każdej literze dowolnego słowa $w \in A^{*}$ (i to wielokrotnie), dlatego też czytając słowo $w$ , automat zmienia stany zgodnie nie tylko z sekwencją liter tego słowa, ale także z uwzględnieniem tej drugiej roli słowa pustego.

Rozszerzając powyższą definicję poprzez dodanie zbioru stanów początkowych i zbioru stanów końcowych, uzyskamy niedeterministyczny

automat z pustymi przejściami

𝒜 {^{p}}_{N D}

= (S,A,f,I,F),Parser nie mógł rozpoznać (błąd składni): {\displaystyle dla którego będziemy mogli zdefiniować język rozpoznawany. W tym celu określimy najpierw działanie takiego automatu pod wpływem dowolnego słowa } w A^*Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Jeśli } s S

o r a z

w=a A

, t o

f(s,a)=f(1^na1^m )=f(1) ... f(1) f(a) f(1) ... f(1) : n,m {N}_0 .

Parser nie mógł rozpoznać (błąd składni): {\displaystyle Zwróćmy uwagę, iż zbiór określający wartość rozszerzonej funkcji jest skończony i efektywnie obliczalny, bo zbiór stanów automatu jest skończony. Jeśli teraz } s S

o r a z

w=ua A

, t o

f(s,w)=f(s,ua)=f(f(s,u),a).

S t a n y z e z b i o r u

f(s,w)Parser nie mógł rozpoznać (błąd składni): {\displaystyle będziemy nazywać stanami osiągalnymi z } sParser nie mógł rozpoznać (błąd składni): {\displaystyle pod wpływem słowa } wParser nie mógł rozpoznać (błąd składni): {\displaystyle . Prawdziwe jest następujące twierdzenie, które orzeka, iż z punktu widzenia rozpoznawania automaty niedeterministyczne z pustymi przejściami rozpoznają dokładnie te same języki, co automaty niedeterministyczne. \begintheor Język } L A^*Parser nie mógł rozpoznać (błąd składni): {\displaystyle jest rozpoznawany przez automat niedeter\-mi\-nis\-tycz\-ny z pustymi przejściami wtedy i tylko wtedy, gdy jest rozpoznawany przez automat nie\-de\-ter\-mi\-nis\-tycz\-ny. \endtheor \beginprf (szkic) Fakt, że język } LParser nie mógł rozpoznać (błąd składni): {\displaystyle rozpoznawany przez automat nie\-de\-ter\-mi\-nis\-tycz\-ny jest rozpoznawany przez automat niedeter\-mi\-nis\-tycz\-ny z pustymi przejściami jest oczywisty. Dowód implikacji w drugą stronę polega na takiej modyfikacji automatu niedeter\-mi\-nis\-tycz\-nego z pustymi przejściami rozpoznającego jezyk } LParser nie mógł rozpoznać (błąd składni): {\displaystyle , by uzyskać automat bez pustych przejść i nie ograniczyć ani nie zwiększyć jego możliwości rozpoznawania. Zarysujemy ideę tej konstrukcji. Niech } {A}{^p}_{ND}

= (S, A, f, I, F),

będzie automatem niedeterministycznym z

pustymi przejściami akceptującym język $L$ . W konstruowanym automacie pozostawiamy zbiór stanów i stan początkowy bez zmian. Jeśli ze stanu początkowego $I$ jest możliwość osiągnięcia jakiegoś stanu końcowego z $F$ , to dodajemy stan początkowy do zbioru stanów końcowych, czyli zbiór stanów końcowych w konstruowanym automacie ma postać $F \cup {I}$ . Jeśli nie ma takiej możliwości, to zbiór stanów końcowych pozostaje niezmieniony. Określamy wartość funkcji przejść dla dowolnego stanu $s \in S$ i litery $a \in A$ jako zbiór wszystkich stanów osiągalnych ze stanu $s$ pod wpływem $a$ . Tak skonstruowany automat niedeterministyczny nie ma pustych przejść i jak można wykazać, indukcyjnie ze względu na długość słowa, rozpoznaje dokładnie język $L$ .

$♢$

Algorytm usuwania przejść pustych i prowadzący do równoważnego automatu niedeterministycznego przedstawiony jest w ćwiczeniach do tego wykładu.

Lemat o pompowaniu

Jedną z wielu własności języków rozpoznawanych przez automaty skończone, i chyba jedną z najważniejszych, przedstawia prezentowane poniżej twierdzenie, zwane tradycyjnie w literaturze lematem o pompowaniu. Istota własności "pompowania" polega na tym, iż automat, mając skończoną ilość stanów, czytając i rozpoznając słowa dostatecznie długie, wykorzystuje w swoim działaniu pętlę, czyli powraca do stanu, w którym znajdował się wcześniej. Przez taką pętlę automat może przechodzić wielokrotnie, a co za tym idzie, "pompować" rozpoznawane słowo, wprowadzając do niego wielokrotnie powtarzane podsłowo odpowiadające tej pętli.

Niech $L \subset A^{*}$ będzie językiem rozpoznawalnym. Istnieje liczba naturalna $N \geq 1$ taka, że dowolne słowo $w \in L$ o długości $∣ w ∣ \geq N$ można rozłożyć na katenację $w = v_{1} {u v}_{2},$ gdzie $v_{1}, v_{2} \in A^{*}, u \in A^{+}$ , $∣ v_{1} u ∣ \leq N$ oraz

v_{1} u^{*} v_{2} \subset L .

Niech $L = L (𝒜)$ , gdzie $𝒜 = (S, A, f, s_{0}, T)$ jest deterministycznym automatem skończenie stanowym. Niech $N = # S$ i rozważmy dowolne słowo $w = a_{1} . . . . a_{k} \in L$ takie, że $∣ w ∣ \geq N$ . Oznaczmy:

s_{1} = f (s_{0}, a_{1}), s_{2} = f (s_{1}, a_{2}), . . ., s_{i + 1} = f (s_{i}, a_{i + 1}), . . ., s_{k} = f (s_{k - 1}, a_{k}) .

Słowo

w

jest

akceptowane przez automat $𝒜$ , więc $s_{k} \in T .$ Ponieważ $# S = N$ oraz $k = ∣ w ∣ \geq N$ , to istnieją $i, j \in {1, . . ., N}$ , $i < j$ takie, że $s_{i} = s_{j}$ .

{ Przyjmując teraz $v_{1} = a_{1} . . . a_{i}, v_{2} = a_{j + 1} . . . a_{k}, u = a_{i + 1} . . . a_{j},$ dochodzimy do nastepującej konkluzji: }

{

f (s_{0}, v_{1}) = s_{i}, f (s_{j}, v_{2}) = s_{k} \in T, f (s_{i}, u) = s_{i} = s_{j} .

}

{ A to oznacza, że słowo $v_{1} u^{k} v_{2}$ jest rozpoznawane przez automat $𝒜$ dla dowolnej liczby $k \geq 0$ , co kończy dowód. Nierówność $∣ v_{1} u ∣ \leq N$ wynika w oczywisty sposób z przyjętego na początku dowodu założenia, że $N = # S$ . }

$♢$

Istotę dowodu przedstawia następująca animacja.

ANIMACJA ja-lekcja6-w-anim2

Jeśli rozpoznawalny język $L \subset A^{*}$ jest nieskończony, to istnieją słowa $v_{1}, u, v_{2} \in A^{*}$ takie, że

v_{1} u^{*} v_{2} \subset L i u \neq 1 .

Jeśli rozpoznawalny język $L \subset A^{*}$ nie jest zbiorem pustym, to istnieje słowo $w \in L$ takie, że $∣ w ∣ < N$ , gdzie $N$ jest stałą występującą w lemacie o pompowaniu.
Jeśli słowo $w \in L$ i $∣ w ∣ \geq N$ , to zgodnie z lematem o pompowaniu możemy przedstawić słowo $w$ jako $w = v_{1} u v_{2}$ , gdzie $u \neq 1$ oraz $v_{1} u^{i} v_{2} \in L$ dla $i = 0, 1, 2 \dots$ . Przyjmując $i = 0$ , mamy $v_{1} v_{2} \in L$ i $∣ v_{1} v_{2} ∣ < ∣ w ∣$ . Powtarzając powyższy rozkład skończoną ilość razy, otrzymamy słowo należące do języka $L$ , o długości mniejszej od $N$ .

Lemat o pompowaniu wykorzystuje się najczęściej do uzasadnienia faktu, iż pewne języki nie są rozpoznawane przez automaty skończone. Przyjrzyjmy się bliżej technice takiego uzasadnienia.

Ćwiczenie [Uzupelnij]

Rozważmy język $L = {a^{n} b^{n} : n \geq 0}$ nad alfabetem $A = {a, b}$ . W oparciu o lemat o pompowaniu wykażemy, że język $L$ nie jest rozpoznawany. Dla dowodu nie wprost, przypuszczamy, że $L$ jest rozpoznawany. Na podstawie udowodnionego lematu istnieją zatem słowa $v_{1}, u, v_{2} \in A^{*}$ takie, że $v_{1} u^{*} v_{2} \subset L$ oraz $u \neq 1 .$ Biorąc pod uwagę formę słów języka $L$ , wnioskujemy, że

słowo $u$ nie może składać się tylko z liter $a$ , gdyż słowo $v_{1} u^{2} v_{2}$ zawierałoby więcej liter $a$ niż $b$ ,

słowo $u$ nie może składać się tylko z liter $b$ , gdyż słowo $v_{1} u^{2} v_{2}$ zawierałoby więcej liter $b$ niż $a$ ,

słowo $u$ nie może składać się z liter $a i b$ , gdyż w słowie $v_{1} u^{2} v_{2}$ litera $b$ poprzedzałaby literę $a$ .

Ponieważ słowo $v_{1} u^{2} v_{2},$ należy do języka $L$ , więc każdy z wyprowadzonych powyżej wniosków prowadzi do sprzeczności.

Rozstrzygalność

Udowodniony w poprzedniej części wykładu lemat o pompowaniu wykorzystywany bywa również w dowodach rozstrzygalności pewnych problemów w klasie języków rozpoznawalnych.

W klasie języków regularnych $ℛ ℰ 𝒢 (A^{*})$ następujące problemy są rozstrzygalne:

problem niepustości języka $L \neq \emptyset,$

problem nieskończoności języka $c a r d L = ℵ_{0},$

problem równości języków $L_{1} = L_{2},$

problem należenia słowa do języka $w \in L .$

Uzupelnic niepusty|. Wystarczy sprawdzić niepustość skończonego podzbioru języka $L .$ Prawdziwa jest bowiem równoważność

Parser nie mógł rozpoznać (błąd składni): {\displaystyle L\neq \oslash \: \Leftrightarrow \: \exists w\in L\, :\, \mid w\mid <N,}

gdzie $N$ jest stałą występującą w lemacie o pompowaniu. Prawdziwość implikacji $\Leftarrow$ jest oczywista. Fakt, że do niepustego języka należy słowo o długości ograniczonej przez $N$ , wynika z lematu o pompowaniu. Jeśli $w \in L$ i $∣ w ∣ \geq N$ , rozkładamy słowo $w$ następująco:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle w=v_{1}uv_{2},\; \; u\neq 1,\; \; \forall i=0,1,2\ldots \: v_{1}u^{i}v_{2}\in L. }

Przyjmując $i = 0$ mamy:

v_{1} v_{2} \in L, ∣ v_{1} v_{2} ∣ < ∣ w ∣

Powtarzając powyższy rozkład skończoną ilość razy otrzymamy słowo należące do języka, o długości ograniczonej przez $N$ .

Uzupelnic nieskonczony|.

Należy udowodnić równoważność :

L nieskończony ⟺ \exists w \in L : N \leq ∣ w ∣ < 2 N

$⟹$
Jeśli $L$ jest nieskończonym zbiorem, to istnieje słowo $w$ dowolnie długie. Niech $∣ w ∣ \geq N$ . Jeśli słowo $w$ nie spełnia ograniczenia $∣ w ∣ < 2 N$ , to podobnie jak poprzednio korzystamy z lematu o pompowaniu i po skończonej ilości kroków otrzymamy słowo krótsze od $2 N$ . Należy jeszcze zauważyć, że wykorzystując lemat o pompowaniu możemy założyć, że usuwane słowo $u$ ma długość ograniczoną przez $N$ . (Zawsze znajdziemy słowo $u$ spełniające ten warunek.) Oznacza to, że ze słowa dłuższego od $2 N$ nie dostaniemy słowa krótszego od $N$ .
$⟸$
Jeśli do języka $L$ należy słowo $w$ o długości większej lub równej $N$ , to z lematu o pompowaniu wynika, że

Parser nie mógł rozpoznać (błąd składni): {\displaystyle w=v_{1}uv_{2},\: u\neq 1\;\;\; i\;\;\; v_{1}u^{*}v_{2}\subset L}

Istnieje więc nieskończony podzbiór zawierający się w $L$ , a zatem język $L$ jest nieskończony. Uzupelnic rownosc|. Niech $L = (L_{1} \cap \overline{L_{2}}) \cup (\overline{L_{1}} \cap L_{2})$ . Z domkniętości klasy $ℒ_{3}$ na operaje boolowskie wynika, że język $L$ jest regularny. Prawdziwa jest równoważność

L \neq \emptyset ⟺ L_{1} \neq L_{2} .

Poblem równoważności języków został sprowadzony do problemu niepustości.

Uzupelnic nalezenie|.

Konstruujemy automat

𝒜

=(S,f,s_0,T)Parser nie mógł rozpoznać (błąd składni): {\displaystyle rozpoznający język } L

i s p r a w d z a m y, c z y

f(s_{0},w) T. Parser nie mógł rozpoznać (nieznana funkcja „\begincenter”): {\displaystyle \begincenter \endcenter \endprf Ilustracją dla powyższego wprowadzenia może być problem skończoności w~klasie jezyków regularnych. Problem jest rozstrzygalny, bowiem w oparciu o lemat o~pom\-po\-wa\-niu można skonstruować algorytm, który dla dowolnego języka regularnego rozstrzygnie ten problem, czyli odpowie twierdząco lub przecząco na pytanie o jego skończoność.}

Test GR3: Różnice pomiędzy wersjami

Wersja z 12:58, 17 sie 2006

Automat niedeterministyczny

Lemat o pompowaniu

Rozstrzygalność

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia

@@ Linia 1: / Linia 1: @@
-{stre}{Streszczenie}
-{wsk}{Wskazówka}
-{rozw}{Rozwiązanie}
-{textt}{}
-{thm}{Twierdzenie}[section]
-{stw}[thm]{Stwierdzenie}
-{lem}[thm]{Lemat}
-{uwa}[thm]{Uwaga}
-{exa}[thm]{Example}
-{dfn}[thm]{Definicja}
-{wn}[thm]{Wniosek}
-{prz}[thm]{Przykład}
-{zadan}[thm]{Zadanie}
-{}
-{}
 {theor}{TWIERDZENIE}[section]
 {rem}{UWAGA}[section]
@@ Linia 28: / Linia 11: @@
 {algorithm}{Algorytm}
-{procedure}{Procedura}
+{ Automat niedeterministyczny, lemat o pompowaniu}
-{ Algorytmy konstrukcji automatu minimalnego }
 ; Wprowadzenie
-:  W  tym wykładzie podamy  algorytmy konstrukcji  automatu minimalnego
+:  W tym wykładzie
-i twierdzenia dowodzące ich poprawności.<br>
+zdefiniujemy automat niedeterministyczny,
+udowodnimy jego równoważność z automatem deterministycznym oraz podamy  algorytm
+konstrukcji równoważnego automatu deterministycznego. Wprowadzimy także automaty
+niedeterministyczne z pustymi przejściami. W ostatniej części wykładu
+sformułujemy lemat o pompowaniu dla
+języków rozpoznawanych przez automaty skończenie stanowe.
 ; Słowa kluczowe
-:   automat minimalny, pochodna Brzozowskiego, algorytmy
+:  automat niedeterministyczny, automat niedeterministyczny z pustymi
-minimalizacji.
+przejściami, lemat o pompowaniu.
-==algorytmy konstrukcji automatu minimalnego==
+==Automat niedeterministyczny==
-Dla języka rozpoznawanego <math>L</math> konstrukcję automatu minimalnego można
+Wprowadzony wcześniej automat jest modelem obliczeń, czy też mówiąc
-rozpocząć, startując z opisu języka danego na przykład przez
+ogólniej, modelem procesu o bardzo prostym opisie. Stan procesu
-wyrażenie regularne lub też jakiegoś automatu rozpoznającego ten
+zmienia się w sposób jednoznaczny pod wpływem sygnału zewnętrznego
-język. W niniejszym wykładzie przedstawimy  algorytmy konstrukcji
+reprezentowanego przez literę alfabetu. Opisem tych zmian jest więc
-automatu minimalnego obejmujące oba wspomniane punkty startu. Jako
+funkcja. Pewnym uogólnieniem powyższej sytuacji może być
-pierwszy, nawiązując do rezulatów przedstawionych w poprzednim
+dopuszczenie relacji, która opisuje zmiany stanu. W efekcie opis
-wykładzie, prezentujemy algorytm, dla którego punktem wyjścia jest
+zmiany stanów staje się niedeterministyczny w tym sensie, że z
-język <math>L</math>. Prezentację poprzedzimy wprowadzeniem pewnej operacji na
+danego stanu automat przechodzi w pewien zbiór stanów. Jak
-słowach zwanej pochodną J.Brzozowskiego.
+udowodnimy pó{z}niej, z punktu widzenia rozpoznawania lub
+poprawnych obliczeń, takie uogólnienie nie rozszerza klasy języków
+rozpoznawanych przez automaty.
-Niech <math>\; L \subset A^* \;</math> będzie dowolnym językiem, a  <math>\; u \in A^* \;</math>   dowolnym
+'''Automatem niedeterministycznym''' nad alfabetem <math>A </math> nazywamy
-słowem. '''Pochodną Brzozowskiego''' (residuum) z języka <math>L</math> względem słowa <math>u</math> nazywamy
+system <math>\mathcal{A}_{ND} </math></center> <nowiki>=</nowiki> (S,f),<math> w którym </math>S<math> jest dowolnym zbiorem, zwanym zbiorem
-język
+stanów, a </math>f: S  A  {P}(S) <math> funkcją przejść.
-<center><math> u^{-1}L=\{w \in A^*\;\; :\;\;\; uw \in L \}.</math></center>
-Podczas obliczeń  pochodnych Brzozowskiego
+\enddefin
-(residuów języka <math>L</math>) można wykorzystać poniższe równości.
-Niech <math>L_1, L_2\subset A^* \;</math> będą
+Funkcję przejść rozszerzamy do funkcji </math>f: S  A^* {P}(S) <math> określonej
-dowolnymi językami, <math>a \in A</math> dowolną literą, a <math> u,v \in A^*</math> dowolnymi słowami.
+na całym wolnym monoidzie </math>A^*<math> w następujący sposób:
-Prawdziwe są  następujące równości:
-<center><math>\aligned\nonumber u^{-1}(L_1 \cup L_2) & = & u^{-1}L_1 \cup u^{-1}L_2, \\
+dla każdego </math>s  S f(s,1) <nowiki>=</nowiki>  s, <math>
-\nonumber u^{-1}(L_1 \backslash L_2) & = & u^{-1}L_1 \backslash
-u^{-1}L_2, \\
-\nonumber u^{-1}(L_1 \cap L_2) & = & u^{-1}L_1 \cap u^{-1}L_2, \\
-\nonumber a^{-1}(L_1L_2) & = & (a^{-1}L_1)L_2 \mbox{, jeśli }
-\notin L_1, \\
-\nonumber a^{-1}(L_1L_2) & = & (a^{-1}L_1)L_2 \cup a^{-1}L_2 \mbox{,
-jeśli } 1 \in L_1, \\
-\nonumber a^{-1}L^* & = & (a^{-1}L)L^*, \\
-\nonumber v^{-1}(u^{-1}L) & = & (uv)^{-1}L.
-\endaligned</math></center>
-{{cwiczenie|[Uzupelnij]||
+dla każdego </math>s  S,  a  A<math> oraz dowolnego </math>w  A^*  f(s,wa)<nowiki>=</nowiki>f(f(s,w),a)
+.<math>
+Zwróćmy uwagę, że prawa strona ostatniej równości to obraz przez funkcję </math>f<math> zbioru
+</math>f(s,w)<math> i litery </math>a<math>.
+Funkcję przejść automatu niedeterministycznego można także traktować jako relację
+</math></center>f&nbsp;&nbsp;(S&nbsp;&nbsp;A^*)&nbsp;&nbsp; S.<center><math>
-Obliczmy wszystkie pochodne dla języka <math>L=a^+b^+</math>. Okazuje się, że są tylko
+W związku z powyższą definicją automat wprowadzony wcześniej, w wykładzie 3,
-cztery różne pochodne liczone względem <math>a</math>, <math>b</math>, <math>ab</math> i słowa pustego <math>1</math>. Mianowicie:<br>
+będziemy nazywać automatem deterministycznym\index{automat deterministyczny}.
-<math> a^{-1}L=a^*b^+ </math>,<br>
-<math> b^{-1}L= \emptyset </math>,<br>
-<math>ab^{-1} L=b^*</math>,<br>
-<math>1^{-1}L=L</math>.<br>
-Dla wszystkich innych słów
-otrzymujemy uzyskane powyżej języki, co wynika z własności pochodnych (patrz wyżej
-wypisane równości) i z następujacych obliczeń: <br>
-<math>\forall n \in \mathbb{N} (a^n)^{-1}L=a^*b^+  </math>,<br>
-<math>\forall n \in \mathbb{N} (b^n)^{-1}L= \emptyset </math>,<br>
-<math>\forall n \in \mathbb{N}(ab^n)^{-1} L=b^*</math>.
-}}
-Zauważmy również, nawiązując raz jeszcze do rezulatów
+\begindefin
-przedstawionych w poprzednim wykładzie, że prawdziwa jest
-następująca równoważność wiążąca wprowadzone pojęcie pochodnej
-Brzozowskiego z prawą kongruencją syntaktyczną:
-<center><math>u \;P{^r}_L\; v  \Longleftrightarrow u^{-1}L=v^{-1}L.</math></center>
-Rozpisując z definicji lewą stronę tej równoważności, otrzymujemy,
+Język </math>L A^{*} <math> jest rozpoznawalny przez automat
-iż dla dowolnego słowa <math>z \in A^*</math> słowo <math>uz \in L</math> wtedy i tylko
+nie\-de\-ter\-mi\-nis\-tycz\-ny </math>{A}_{ND} <nowiki>=</nowiki>(S,f)<math>
-wtedy, gdy  <math>vz \in L</math>. A to równoważnie oznacza (znów z definicji),
+wtedy i tylko wtedy, gdy istnie\-je </math>I  S<math> -- zbiór stanów
-że   <math>u^{-1}L=v^{-1}L.</math>
+początkowych oraz </math>F  S<math> - zbiór stanów końcowych taki, że
+</math></center>L <nowiki>=</nowiki>w  A^*  :  f(I,w) F   .<center><math>
-Z uzasadnionej równoważności oraz twierdzenia 3.4 o prawej kongruencji syntaktycznej z
+\enddefin
-poprzedniego wykładu wnioskujemy równoważność rozpoznawalności języka <math>L</math>
-i skończonej ilości różnych pochodnych Brzozowskiego tego języka.
-Pierwszy z przedstawianych algorytmów będzie konstruował automat
+Niedeterministyczny automat rozpoznający język </math>L<math> będziemy oznaczać jako
-minimalny, wyznaczając prawą kongruencję automatową poprzez
+system </math>{A}_{ND}  <nowiki>=</nowiki> (S,A,f,I,F)<math> lub </math>{A}_{ND}<nowiki>=</nowiki>(S,f,I,F), <math>
-zastosowanie metody pochodnych Brzozowskiego. Metoda ta umożliwia
+jeśli wiadomo, nad jakim alfabetem określono automat.
-przeprowadzanie odpowiednich obliczeń bezpośrednio na wyrażeniach
-regularnych. Ogólny opis algorytmu jest następujący.  Stany
-konstruowanego automatu minimalnego etykietowane są  zbiorami
-odpowiadającymi pewnym językom. Mając dany język <math>L</math>, ustanawiamy
-stan początkowy automatu jako <math>L</math>, wpisujemy go na listę
-<math>\mathcal{L}</math> i obliczamy <math>a^{-1}L</math> dla każdej litery <math>a \in A</math>.
-Jeśli wśród obliczonych wartości znajduje się język niewystępujący
-na liście, dodajemy go do listy. Obliczenia pochodnych Brzozowskiego
-wykonujemy, dopóki będziemy uzyskiwać nowe języki (nowe stany).
-Funkcja przejść konstruowanego automatu minimalnego zdefiniowana
-jest następująco:
-<center><math>f(X, a)=a^{-1}X,</math></center> gdzie <math>X</math> jest pewnym językiem  z listy <math>\mathcal{L}</math>.
-Obliczone języki określają stany automatu minimalnego.
----- dla dociekliwych - start ----
+Na pierwszy rzut oka mogłoby się wydawać, że wprowadzony automat istotnie rozszerza
+możliwości automatu deterministycznego, że jego moc obliczeniowa jest istotnie większa.
+Okazuje się jednak,  że z punktu widzenia rozpoznawania
+języków, czyli właśnie z punktu widzenia mocy obliczeniowej,
+automaty deterministyczne i niedeterministyczne są rów\-no\-waż\-ne.
-Obliczone języki określające stany automatu minimalnego  to
+\begintheor
-elementy monoidu syntaktycznego języka <math>L</math>.
----- dla dociekliwych - end ----
+Język </math>L  A^*<math> jest rozpoznawany przez automat deter\-mi\-nis\-tycz\-ny wtedy i tylko wtedy, gdy jest rozpoznawany
+przez automat nie\-de\-ter\-mi\-nis\-tycz\-ny.
-Automatem minimalnym dla automatu <math>\mathcal{A}=(S, A, f, s_0, T)</math>
+\endtheor
-będzie zatem automat
-<center><math>\mathcal{A}_L=(S_L, A, f_L, s_0^L, T_L),</math></center>
-gdzie:
-* <math>S_L=\{u^{-1}L:\ u \in A^*\}</math>,
+\beginprf
-* <math>s_0^L = L </math>,
+Rozpocznijmy dowód od oczywistej obserwacji. Zauważmy, iż każdy
+automat deterministyczny można przekształcić w
+nie\-de\-ter\-mi\-nis\-tycz\-ny, modyfikując funkcję przejść w ten
+sposób, że jej wartościami są zbiory jednoelemen\-to\-we.
+Modyfikacja ta prowadzi w konsekwencji do równoważnego automatu
+niedeterministycznego.
-* <math>T_L = \{u^{-1}L:\ u \in L\}</math>,
+Dla dowodu implikacji w stronę przeciwną załóżmy, że język </math>L<nowiki>=</nowiki>L({A}_{ND}) <math>, gdzie </math>{A}_{ND} <nowiki>=</nowiki>
+(S,f,I,F)<math>, jest automatem niedeterministycznym. Określamy teraz
+równoważny, jak się okaże, automat deterministyczny. Jako zbiór
+stanów przyjmujemy </math>{P}(S) <math>, czyli ogół podzbiorów
+zbioru </math>S<math>. Funkcję przejść </math>{f}:{P}(S)
+A^{*} {P}(S) <math> określamy kładąc dla
+dowolnego stanu </math>S_1 {P}(S) <math> oraz dowolnej litery </math>
+a  A</center>{f} (S_1 ,a) <nowiki>=</nowiki> _{s S_1} f(s,a),<center><math> a
+następnie rozszerzamy ją do </math>A^{*} <math>. Łatwo sprawdzić, że funkcja
+</math>{f}<math> spełnia warunki funkcji przejść. Przyjmując następnie
+zbiór </math>I  {P}(S) <math> jako stan początkowy oraz zbiór
+</math>T<nowiki>=</nowiki> {S}_{1} {P}(S) : S_{1} F
+<math>, jako zbiór stanów końcowych stwierdzamy, dla
+określo\-ne\-go automatu </math>{A}_{D}<nowiki>=</nowiki>(
+{P}(S),{f},I,T)  <math>, równość
-* <math>f_L(u^{-1}L,a) = a^{-1}(u^{-1}L)=(ua)^{-1}L</math>.
+</math></center>L({A}_{D})<nowiki>=</nowiki>w A^{*}: {f}(I,w)
+T<nowiki>=</nowiki>L<nowiki>=</nowiki>L({A}_{ND}).<center><math>
-Jeśli zdefiniujmy odwzorowanie <math>\nu: S \rightarrow S_L</math>, kładąc:
+Skonstruowany automat jest zatem
-<center><math>\nu(s)=u^{-1}L, \mbox{ gdzie } s=f(s_0,u),</math></center> to można dowieść,
+deterministyczny i równoważny wyjściowemu,
-że <math>\nu</math> jest dobrze określone, jest epimorfizmem oraz <math>\nu(s_0) =
+co kończy dowód twierdzenia.
-s_0^L</math> - porównaj twierdzenie 3.1 z wykładu 4. Prawdą jest też, iż
-<math>s \in T</math> wtedy i tylko wtedy, gdy <math>\nu(s) \in T_L</math> oraz że
-następujący diagram komutuje:
-<center><math>\beginCD
+\begincenter   \endcenter  \endprf
-s @>{a}>> s' @. \ \ \ \ \mbox{ w } \mathcal{A} \\
-@V{\nu}VV  @V{\nu}VV \\
-u^{-1}L @>{a}>> (ua)^{-1}L @. \ \ \ \ \mbox{ w } \mathcal{A}_L.
-\endCD  </math></center>
-Formalny zapis algorytmu przedstawiony jest poniżej.
+{{uwaga|[Uzupelnij]||
-{{Minimalizuj1} - algorytm minimalizacji
+Dla określonego w dowodzie automatu </math>{A}_{D} <math> na ogół
-wykorzystujący pochodne Brzozowskiego}
+nie wszystkie stany są osiągalne ze stanu </math>I<math>. Aby uniknąć takich
-[1]
+stanów, które są bezużyteczne, funkcję przejść należy zacząć
-Wejście: <math>\mathcal{A}=(S, A, f, s_0, T)</math> - automat taki, że
+definiować od stanu </math>I<math> i kolejno  określać wartości
-<math>L=L(\mathcal{A})</math>
+dla już osiągniętych stanów.
-Wyjście: automat minimalny <math>\mathcal{A}'=(S_L, A, f_L, s_L,
+}}
-T_L)</math> dla <math>\mathcal{A}S_L \leftarrow \{L\}</math>;
-'''włóż'''<math>(\mathcal{L},L)</math>;
+{{cwiczenie|[Uzupelnij]||
-{<math>\mathcal{L} \not =</math>}
-<math>M \leftarrow </math> '''zdejmij'''<math>(\mathcal{L})</math>;
-{'''each''' <math>a \in A</math>}
-<math>N \leftarrow a^{-1}M</math>;
-{<math>N \cap S_L = </math> }
-<math>S_L \leftarrow S_L \cup \{N\}</math>;
-'''włóż'''<math>(\mathcal{L},N)</math>;
+Automat </math>{A}_{ND}  <nowiki>=</nowiki> (Q,A,f,I,F)<math> nad alfabetem </math>A<nowiki>=</nowiki>a,b <math>
+określony przez zbiory </math>Q<nowiki>=</nowiki>q_{0},q_{1},q_{2},q_4 , I<nowiki>=</nowiki>q_0, F<nowiki>=</nowiki>q_{3} <math> i
+zadany poniższym grafem jest przykładem automatu niedeterministycznego.\\
-{'''each''' <math>M \in S_L</math>}
+RYSUNEK ja-lekcja6-w-rys1
-{'''each''' <math>a \in A</math>}
+Automat ten, jak łatwo teraz zauważyć, rozpoznaje język </math>L({A})<nowiki>=</nowiki>A^*abb <math>.
-<math>f_L(M,a) \leftarrow a^{-1}M</math>;
-<math>s_L \leftarrow L</math>;
-<math>T_L \leftarrow \{u^{-1}L:\ u \in L\}</math>;
-<math>\mathcal{A}'</math>;
-Funkcja '''zdejmij'''<math>(\mathcal{L})</math>, występująca w linii 6.,
-zdejmuje z kolejki <math>\mathcal{L}</math> pierwszy element  i zwraca go jako
-swoją wartość. Procedura '''włóż'''<math>(\mathcal{L},L)</math>, występująca
-w liniach 4. oraz 11., wstawia na koniec kolejki <math>\mathcal{L}</math>
-element <math>L</math>.
-{{cwiczenie|[Uzupelnij]||
-Dla języka <math>L=a^+b^+</math> z przykładu 1.1 w wyniku działania powyższego algorytmu
-otrzymamy czterostanowy automat
-<math>\mathcal{A}_L=(S_L,A,  f, L, T),</math> gdzie<br>
-<math>S_L= \{L, a^*b^+  ,\emptyset, b^*\}</math>,<br>
-a funkcja
-przejść zadana jest grafem: <br>
-RYSUNEK ja-lekcja5-w-rys1
 }}
-Prezentowane poniżej twierdzenie uzasadnia kolejny algorytm  konstrukcji automatu
+Przedstawimy teraz algorytm, który mając na wejściu automat niedeterministyczny konstruuje
-minimalnego. Tym razem punktem wyjścia jest dowolny automat rozpoznający język
+równoważny automat deterministyczny.
-<math>L </math>.
----- dla dociekliwych - start -----
-Algorytm oblicza również monoid syntaktyczny języka <math>L </math>.
----- dla dociekliwych - end -----
-Analogicznie do konstrukcji relacji <math>\rho _{i} </math>, przedstawionej
-w wykładzie 4, możemy określić ciąg odpowiednich relacji na
-zbiorze stanów dowolnego automatu rozpoznającego język <math>L </math>.
-Relacje te służą do efektywnego określenia automatu minimalnego,
-równoważnego zadanemu.
-Niech <math>\mathcal{A} </math></center><nowiki>=</nowiki> (S,A,f,s_0,T)<math> będzie dowolnym automatem i
-niech </math>L<nowiki>=</nowiki>L({A}) <math>.
-Przez </math>  _{{A}}   S  S  <math> oznaczmy relację
-równoważności
-zawierającą dwie klasy równoważności </math>T<math> i </math>S  T<math>. Przez </math>{}_i<math> dla </math>i { N} <math>
-oznaczmy zstępujący ciąg relacji określony następująco:
-</math>{}_1 <nowiki>=</nowiki>  _{{A}} <math>, a dla </math> i <nowiki>=</nowiki> 2,... <math> przyjmijmy
-</math>{}_i <nowiki>=</nowiki>  (s,t)   S  S  :   a  A  1   f(s,a) {}_{i-1} f(t,a) . <math>
-{\par\raggedright Wtedy </math>  {}_i <math> jest największą prawą kongruencją automatową zawartą w relacji </math>{}_1 <nowiki>=</nowiki>  _{{A}} <math> i automat minimalny ma postać\par}
-</math></center>{A}_{L}<nowiki>=</nowiki>( S/_{ { }_{i}},A,f^{*},[s_{0}],T/_{ { }_{i}}) .<center><math>
-\endtheor
-Dowód tego twierdzenia przebiega analogicznie do dowodu twierdzenia 3.3 z
-wykładu 4.
-Algorytm działajacy w oparciu o powyższe twierdzenie na podstawie
-zadanego automatu </math>{A}<nowiki>=</nowiki>(S, A, f, s_0, T)<math>, konstruuje
-efektywnie automat minimalny dla </math>{A}<math>, obliczając ciąg
-relacji </math>{}_i<math>. Proces konstrukcji przebiega w sposób
-iteracyjny. Zaczynamy od zdefiniowania relacji
-</math>_{{A}}<math>, która posiada tylko dwie klasy abstrakcji:
-do pierwszej z nich należą wszystkie stany końcowe, a do drugiej --
-wszystkie pozostałe stany. Tak więc
-</math></center> s, t  Ss _{{A}} t  (s  T  t  T)  (s  S  T  t  S  T).<center><math>
-Definiujemy pierwszą z relacji </math>{}<math>, czyli relację
-</math>{}_1<math>  jako równą </math>_{{A}}<math>, a
-następnie, dla każdej obliczonej już relacji
-</math>{}_{i-1}<math>, obliczamy relację </math>{}_i<math> w
-następujący sposób:
-</math></center>s_1 {}_i
-s_2  (s_1 {}_{i-1} s_2)  (
-a  Af(s_1, a) {}_{i-1} f(s_2,a)).<center><math> Nowo obliczona
-relacja </math>{}_i<math> albo podzieli jedną lub kilka klas
-abstrakcji relacji </math>{}_{i-1}<math>, albo będzie identyczna z
-relacją </math>{}_{i-1}<math>. Jeśli zajdzie ta druga sytuacja, to
-znaczy, że dla każdego </math>j>i<math> w oczywisty sposób spełniona jest
-równość </math>{_j}<nowiki>=</nowiki>{}_i<math>, czyli ciąg relacji
-ustabilizuje się. W tym momencie algorytm kończy swoje działanie i
-klasy abstrakcji relacji </math>{}_i<math> będą reprezentować
-stany automatu minimalnego.
 \newpage
-\beginalgorithm
+\beginalgorithm  \caption{\textsc{Determinizacja} -- buduje deterministyczny automat
-\caption{\textsc{Minimalizuj2} -- algorytm minimalizacji automatu
+równoważny automatowi niedeterministycznemu}
-wykorzystujący stabilizujący się ciąg relacji}
 \beginalgorithmic [1]
-\STATE Wejście: </math>{A}<nowiki>=</nowiki>(S, A, f, s_0, T)<math> -- automat taki, że
+\STATE Wejście: </math>{A}<nowiki>=</nowiki>(S, A, f, s_0, T)<math> -- automat
-</math>L<nowiki>=</nowiki>L({A})<math>.
+niedeterministyczny.
-\STATE Wyjście: automat minimalny </math>{A}'<nowiki>=</nowiki>(S',A',f', s_0',
+\STATE Wyjście: </math>{A}'<nowiki>=</nowiki>(S', A, f', s_0', T')<math> -- automat
-T')<math> dla </math>{A}<math>.
+deterministyczny taki, że </math>L({A}')<nowiki>=</nowiki>L({A})<math>.
-\STATE </math>{}_1_{{A}}<math>;
+\STATE </math>S'  s_0<math>;
-\STATE </math>i  1<math>;
+\STATE </math>s_0'  s_0<math>;
-\REPEAT
+\STATE </math>{L}  s_0<math>;  \hfill
+</math>{L}<math> jest kolejką
-\STATE  oblicz </math>{}_i<math>: </math>s_1
+\WHILE{</math>{L}  <nowiki>=</nowiki> <math>}
-{}_i s_2  (s_1 {}_{i-1}
-s_2)  ( a  Af(s_1, a) {}_{i-1}
-f(s_2,a))<math>;
-\STATE </math>i  i+1<math>;
+\STATE </math>M
+'''zdejmij'''({L})<math>;
-\STATE \textbf{empty}</math>({}_i)<math>
+\STATE \textbf{if } </math>T  M  <nowiki>=</nowiki> <math> \textbf{ then } </math>T'
+T'  M<math>;
-\FOR{\textbf{each} </math>(s_1,s_2) S S<math>}
+\FOR{\textbf{each} </math>a  A<math>}
-\STATE flag\textbf{true};
-\FOR{\textbf{each} </math>a A<math>}
+\STATE </math>N  _{m  M} f(m,a)<math>;
-\IF{\textbf{not} </math>f(s_1, a) {}_{i-1} f(s_2,a)<math>}
+\IF{</math>N   S'<math>}
-\STATE flag\textbf{false};
+{
+\STATE </math>S'  S'  N<math>;
+\STATE \textbf{włóż}</math>({L},N)<math>;
+}
 \ENDIF
-\ENDFOR
+\STATE </math>f'(M, a)  N<math>;
-\IF{flag=\textbf{true} \textbf{and} </math>s_1 {}_{i-1} s_2<math>}
-\STATE </math>{}_{i}  {}_{i}
-(s_1,s_2)<math>;
-\ENDIF
 \ENDFOR
-\UNTIL{</math>{}_i <nowiki>=</nowiki> {}_{i-1}<math>}
+\ENDWHILE
-\STATE </math>S'  S  {}_i<math>;
-\FOR{\textbf{each} </math>[s]_{{}_i}  S
-{}_i<math>}
-\FOR{\textbf{each} </math>a  A<math>}
-\STATE </math>f'([s]_{{}_i},a)
-[f(s,a)]_{{}_i}<math>;
-\ENDFOR
+\RETURN </math>{A}'<math>;
-\ENDFOR
-\STATE </math>s_0'  [s_0]_{{}_i}<math>;
-\STATE </math>T'  [t]_{{}_i}:t  T<math>;
-\RETURN </math>{A}'<nowiki>=</nowiki>(S', A, f', s_0', T')<math>;
 \endalgorithmic
 \endalgorithm
-{{cwiczenie|[Uzupelnij]||
+Funkcja \textbf{zdejmij}, występująca w linii [[##a1_l6|Uzupelnic a1_l6|]]., zdejmuje
+z kolejki element znajdujący się na jej początku i zwraca go jako
-Zminimalizujemy automat </math>{A}<nowiki>=</nowiki>(S,A,f,s_0,T)<math>, dla którego\\
+swoją wartość. Procedura \textbf{włóż}</math>({L},N)<math> z linii
-</math>S<nowiki>=</nowiki> s_{0},s_{1},s_{2},s_{3},s_{4},s_5 , A<nowiki>=</nowiki>a,b,
+[[##a1_l12|Uzupelnic a1_l12|]]. wstawia na koniec kolejki </math>{L}<math> element </math>N<math>.
-T<nowiki>=</nowiki>s_1, s_{2},s_{4}  <math>,
-a funkcja przejść określona jest przy pomocy grafu.\\
-RYSUNEK ja-lekcja5-w-rys2\\
-Konstruujemy ciąg
-relacji </math>{}_i<math>.
-Na początku  </math>{}_1<math> dzieli </math>S<math> na dwie klasy
-abstrakcji; pierwsza zawiera stany końcowe, a druga -- wszystkie
-pozostałe, czyli uzyskujemy dwa zbiory </math>s_1,s_2,s_4<math> oraz
-</math>s_0, s_3, s_5<math>.Obliczmy </math>{}_2<math> (pierwszy przebieg pętli w liniach 5.-20. algorytmu). Aby dwa elementy
-(stany) </math>s<math> i </math>t<math> były ze sobą w relacji </math>{}_2<math> muszą
-być ze sobą w relacji </math>{}_1<math> oraz musi zachodzić
-</math></center> a  A  f(s, a) {}_1 f(t,a).<center><math>
-Czyli kolejna, nowa relacja może ewentualnie podzielić już
-istniejące zbiory zdefiniowane przez poprzednią relację. Nie może
-więc zajść taka sytuacja, że w jednej klasie abstrakcji relacji
-</math>{}_{i+1}<math> znajdą się elementy z różnych klas
-abstrakcji relacji </math>{}_i<math>.
-Rozważmy najpierw zbiór </math>s_1, s_2, s_4<math>. Oczywiście każde dwa
-stany z tego zbioru są ze sobą w relacji </math>{}_1<math>.
-Zauważmy, że </math>f(s_2, a)<nowiki>=</nowiki>f(s_4,a)<nowiki>=</nowiki>s_2<math>, </math>f(s_2,b)<nowiki>=</nowiki>f(s_4,b)<nowiki>=</nowiki>s_4<math>, więc
-</math>s_2 {}_2 s_4<math> (bo </math>s_2 {}_1 s_2<math> oraz </math>s_4 {}_1 s_4<math>).
-Ponieważ </math>f(s_1,b)<nowiki>=</nowiki>s_5<math> i </math>f(s_2,b)<nowiki>=</nowiki>s_4<math>, a wiemy, że </math>s_5<math> nie jest
-w relacji </math>{}_1<math> z  </math>s_4<math>, zatem stany </math>s_1<math> i </math>s_2<math>
-nie mogą być ze sobą w relacji </math>{}_2<math>, a to oznacza, że
-także stany </math>s_1<math> i </math>s_4<math> nie mogą być ze sobą w relacji
-</math>{}_2<math>.
-W analogiczny sposób można sprawdzić, że relacja </math>{}_2<math> nie
+Należy zauważyć, że algorytm determinizujący automat jest algorytmem
-podzieli zbioru </math>s_0, s_3, s_5<math>. Ostatecznie, po pierwszym
+eksponencjalnym. Stany wyjściowego automatu deterministycznego
-wykonaniu pętli algorytmu minimalizacji obliczyliśmy relację
+etykietowane są podzbiorami zbioru stanów </math>Q<math>. Jeśli pewien stan </math>q'
-</math>{}_2<math>, która dzieli </math>S<math> na następujące podzbiory:
+Q'<math> etykietowany jest zbiorem zawierającym stan końcowy z </math>F<math>,
-</math></center>s_1, s_2, s_4, s_0, s_3, s_5.<center><math>
+to </math>q'<math> staje się stanem końcowym w automacie </math>{A}'<math>.
-W kolejnym kroku obliczamy </math>{}_3<math>. Zbiór </math>s_1<math>
+Z analizy algorytmu [[##alg_1|Uzupelnic alg_1|]] wynika, że w ogólności zbiór stanów
-oczywiście nie może być już podzielony na mniejsze podzbiory.
+wyjściowego automatu deterministycznego może osiągać wartość rzędu
-Łatwo zauważyć, że </math>{}_3<math> nie podzieli także zbioru </math>s_2,
+</math>O(2^n)<math>, gdzie </math>n<math> jest ilością stanów automatu
-s_4<math>.
+niedeterministycznego.
-Rozważmy teraz zbiór </math>s_0, s_3, s_5<math>. Mamy </math>f(s_3, a)<nowiki>=</nowiki>f(s_5, a)<math> oraz
+Zastosujemy powyższy algorytm do uzyskania automatu deterministycznego równoważnego
-</math>f(s_3, b)<nowiki>=</nowiki>s_3<math>, </math>f(s_5, b)<nowiki>=</nowiki>s_5<math> i wiadomo, że </math>s_3 {}_2
+automatowi z przykładu 1.1. Kolejne etapy działania
-s_5<math>, zatem </math>s_3<math> i </math>s_5<math> będą ze sobą w relacji
+ilustruje zamieszczona tu animacja.
-</math>{}_3<math>.
-Ponieważ </math>f(s_0, a)<nowiki>=</nowiki>s_2<math> i </math>f(s_3, a)<nowiki>=</nowiki>s_1<math>, ale </math>s_2<math> i </math>s_1<math> nie są
+ANIMACJA ja-lekcja6-w-anim1
-ze sobą w relacji </math>{}_2<math>, zatem nie mogą być także ze
-sobą w relacji </math>{}_3<math>. Relacja </math>{}_3<math>
-dzieli więc zbiór </math>s_0, s_3, s_5<math> na zbiory </math>s_0<math> oraz
-</math>s_3, s_5<math>.
-Podział zbioru </math>S<math> przez relację </math>{}_3<math> wygląda więc
+==Automaty niedeterministyczne z przejściami pustymi==
-następująco: </math></center>s_0, s_1, s_2, s_4, s_3, s_5.<center><math>
-Relacja </math>{}_4<math> nie podzieli już ani zbioru </math>s_2,
+Rozszerzenie definicji automatu skończenie stanowego do automatu niedeterministycznego
-s_4<math>, ani zbioru </math>s_3, s_5<math>, więc uzyskujemy równość
+nie spowodowało, jak wiemy, zwiększenia mocy obliczeniowej takich modeli. Nasuwać się
-</math>{_4}<nowiki>=</nowiki>{}_3<math> i ponieważ ciąg relacji się
+może pytanie, czy dołączenie do tego ostatniego modelu możliwości wewnętrznej zmiany
-ustabilizował, algorytm kończy działanie.
+stanu, zmiany stanu bez ingerencji sygnału zewnetrznego, czyli bez czytania litery nie zwiększy
+rodziny jezyków rozpoznawanych.
-Podsumowując, mamy:
+Model taki, zwany automatem z pustymi przejściami (w skrócie:
+automat z p-przejściami), zdefiniujemy poniżej.
-; </math>{} _{1}<math>
+\begindefin
-:   </math>s_1, s_{2},s_{4}, s_{0},s_{3},s_5,  <math>
-; </math>{} _{2}<math>
+\textbf{Automatem niedeterministycznym z pustymi przejściami} nad alfabetem </math>A <math> nazy\-wa\-my
-:  </math>s_{1},s_2,s_{4}, s_{0},s_{3},s_5,<math>
+system </math>{A}{^p}_{ND} <center><math> = (S,f),</math> w którym <math>S</math> jest dowolnym zbiorem, zwanym zbiorem
+stanów, a <math>f: S \times (A \cup \{1\}) \rightarrow \mathcal{P}(S) </math> funkcją przejść.
-; </math>{} _{3}<math>
+{{uwaga|[Uzupelnij]||
-:  </math>s_{1},s_2,s_{4}, s_{0},s_{3},s_5.{} _{3}<nowiki>=</nowiki>{} _{4}<math> i równoważny minimalny automat </math>{A}_L<nowiki>=</nowiki>(S,f^*,s_0,T)<math> ma </math>4<math> stany. \\
-</math>q_0<nowiki>=</nowiki>s_{0}, q_1<nowiki>=</nowiki>s_{1}, q_2 <nowiki>=</nowiki> s_2,s_{4}, q_3
-<nowiki>=</nowiki>s_{3},s_5<math>, </math>T<nowiki>=</nowiki>q_1 ,q_2<math>.
-Jak łatwo zauważyć jest to automat z przykładu 3.1 zamieszczonego w wykładzie 4.
-RYSUNEK ja-lekcja5-w-rys3
+Słowo puste <math>1</math> występuje w powyższej definicji w dwóch rolach.
+Pierwsza, to znana nam rola elementu neutralnego katenacji słów.
+Druga, to rola jakby "dodatkowej" litery, która może powodować
+zmianę aktualnego stanu automatu na inny. Ponieważ słowo puste może
+wystąpić przed i po każdej literze dowolnego słowa  <math>w \in A^*</math> (i
+to wielokrotnie), dlatego też czytając słowo <math>w</math>, automat zmienia
+stany zgodnie nie tylko z sekwencją liter tego słowa, ale także z
+uwzględnieniem tej drugiej roli słowa pustego.
 }}
-Jednym z najczęściej stosowanych algorytmów automatu minimalnego jest algorytm, który
+Rozszerzając  powyższą definicję poprzez dodanie zbioru stanów
-buduje "tabelkę" na podstawie której określa się automat minimalny.
+początkowych i zbioru stanów końcowych, uzyskamy niedeterministyczny
-Poprawność tego
+automat z pustymi przejściami <math>\mathcal{A}{^p}_{ND} </math></center> <nowiki>=</nowiki>
-algorytmu również uzasadnia twierdzenie  [[##twrho|Uzupelnic twrho|]].
+(S,A,f,I,F),<math> dla którego będziemy mogli zdefiniować język
+rozpoznawany. W tym celu określimy najpierw działanie takiego
+automatu pod wpływem dowolnego słowa </math>w  A^*<math>.  Jeśli </math>s  S<math>
+oraz </math>w<nowiki>=</nowiki>a  A<math>, to
-W algorytmie tym wyznaczać będziemy tzw. stany rozróżnialne.
+</math></center>f(s,a)<nowiki>=</nowiki>f(1^na1^m )<nowiki>=</nowiki>f(1) ... f(1) f(a) f(1) ... f(1) : n,m  {N}_0 .<center><math>
-Algorytm działa w czasie </math>O(|A|n^2)<math>, gdzie </math>|A|<math> jest mocą
-alfabetu, a </math>n<math> -- liczbą stanów automatu wejściowego, czyli
-podlegajacego  minimalizacji. Złożoność pamięciowa jest również
-</math>O(|A|n^2)<math>. Prezentowany algorytm nosi nazwę algorytmu
-Hopcrofta-Ullmana. Znana w literaturze jest pewna zmodyfikowana
-wersja tego algorytmu. Jest to algorytm Aho-Sethiego-Ullmana, który
-ma tę samą złożoność czasową, ale lepszą złożoność pamięciową -
-</math>O(|A|n)<math>. Natomiast w ramach ćwiczeń prezentujemy jeszcze jeden
-algorytm, znany jako algorytm minimalizacji Hopcrofta. Czas
-działania  tego algorytmu wynosi </math>O(n  n)<math>.
-Niech  będzie relacją zdefiniowaną przez funkcję przejść automatu
+Zwróćmy uwagę, iż zbiór określający wartość rozszerzonej funkcji jest skończony i efektywnie
-w następujący sposób:
+obliczalny, bo zbiór stanów automatu jest skończony. Jeśli teraz </math>s  S<math> oraz </math>w<nowiki>=</nowiki>ua  A<math>, to
-</math></center>p  q   w  A^* (f(p,w)  T
+</math></center> f(s,w)<nowiki>=</nowiki>f(s,ua)<nowiki>=</nowiki>f(f(s,u),a).<center><math>
-f(q,w)  T).<center><math>
+Stany ze zbioru </math>f(s,w)<math> będziemy nazywać stanami osiągalnymi z </math>s<math>
+pod wpływem słowa </math>w<math>. Prawdziwe jest następujące twierdzenie, które
+orzeka, iż z punktu widzenia rozpoznawania automaty
+niedeterministyczne z pustymi przejściami  rozpoznają dokładnie te
+same języki, co automaty niedeterministyczne.
-\begindefin
+\begintheor
-Stany </math>p<math> i </math>q<math> są równoważne, jeśli </math>p  q<math>.
+Język </math>L  A^*<math> jest rozpoznawany przez automat niedeter\-mi\-nis\-tycz\-ny
-\enddefin
+z pustymi przejściami wtedy i tylko wtedy, gdy jest rozpoznawany
+przez automat nie\-de\-ter\-mi\-nis\-tycz\-ny.
-Jeśli stany nie są równoważne, to będziemy mówić, że są
+\endtheor
-rozróżnialne.
-Zadaniem algorytmu jest wyznaczenie stanów równoważnych, celem ich
+\beginprf  (szkic)
-utożsamienia ze sobą. Algorytm musi zdecydować, dla każdej pary
+Fakt, że język </math>L<math>  rozpoznawany przez automat nie\-de\-ter\-mi\-nis\-tycz\-ny jest
-stanów </math>(p,q)<math>, czy są one rozróżnialne. Jeśli pod koniec działania
+rozpoznawany przez automat niedeter\-mi\-nis\-tycz\-ny
-algorytmu okaże się, że nie stwierdziliśmy rozróżnialności tych
+z pustymi przejściami jest oczywisty.
-stanów, to znaczy, że są one równoważne; następuje ich utożsamienie,
-czyli "połączenie" ich w jeden stan. Gdy takiego połączenia dokonamy
-dla wszystkich par stanów, wobec których nie stwierdziliśmy ich
-rozróżnialności, powstanie automat o minimalnej liczbie stanów.
-W praktyce algorytm nie wyznacza stanów równoważnych, ale stany
+Dowód implikacji w drugą stronę polega na takiej modyfikacji
-rozróżnialne, gdyż jest to po prostu łatwiejsze. Po wyznaczeniu
+automatu niedeter\-mi\-nis\-tycz\-nego z pustymi przejściami
-wszystkich par stanów rozróżnialnych pozostałe pary stanowić będą
+rozpoznającego jezyk </math>L<math>, by uzyskać automat bez pustych przejść i
-stany równoważne.
+nie ograniczyć ani nie zwiększyć jego możliwości rozpoznawania.
+Zarysujemy ideę tej konstrukcji. Niech  </math>{A}{^p}_{ND} <center><math>
+= (S,A,f,I,F),</math> będzie  automatem niedeterministycznym z
+pustymi przejściami akceptującym język <math>L</math>. W konstruowanym
+automacie pozostawiamy zbiór stanów i stan początkowy bez zmian.
+Jeśli ze stanu początkowego <math>I</math> jest możliwość osiągnięcia jakiegoś
+stanu końcowego z <math>F</math>, to dodajemy stan początkowy do zbioru stanów
+końcowych, czyli zbiór stanów końcowych w konstruowanym automacie ma
+postać <math>F \cup \{I\}</math>. Jeśli nie ma takiej możliwości, to zbiór
+stanów końcowych pozostaje niezmieniony. Określamy wartość funkcji
+przejść dla dowolnego stanu <math>s \in S</math> i litery <math>a \in A</math> jako zbiór
+wszystkich stanów osiągalnych  ze stanu <math>s</math> pod wpływem <math>a</math>. Tak
+skonstruowany automat niedeterministyczny nie ma pustych przejść i
+jak można wykazać, indukcyjnie ze względu na długość słowa,
+rozpoznaje dokładnie język <math>L</math>.
-W algorytmie wykorzystywać będziemy tablicę list </math>{L}[p,q]<math>,
+<math>\diamondsuit</math>
-po jednej liście dla każdej pary stanów. Funkcja
-</math>'''initialize'''({L}[p,q])<math> inicjalizuje listę pustą,
-funkcja </math>'''zdejmij'''({L}[p,q])<math> zdejmuje jeden z
-elementów, natomiast funkcja
-</math>'''włóż'''({L}[p,q],x)<math> wkłada element </math>x<math> na listę
-</math>{L}[p,q]<math>. Funkcja </math>'''empty'''({L}[p,q])<math>
-zwraca wartość </math>'''true'''<math> gdy lista jest pusta, oraz
-</math>'''false'''<math> w przeciwnym wypadku. Zwróćmy uwagę, że elementami
-każdej z list </math>{L}[p,q]<math> są pary stanów </math>(s,t) S S<math>.
-\newpage
+Algorytm usuwania przejść pustych i prowadzący do równoważnego automatu
+niedeterministycznego  przedstawiony jest w ćwiczeniach do tego wykładu.
-\beginalgorithm
+==Lemat o pompowaniu==
-\caption{\textsc{Minimalizuj3} -- algorytm minimalizacji
-wykorzystujący relację }
-\beginalgorithmic [1]
-\STATE Wejście: </math>{A}<nowiki>=</nowiki>(S, A, f, s_0, T)<math> -- automat
-\STATE Wyjście: </math>{A}'<nowiki>=</nowiki>(S', A, f', s_0', T')<math> -- automat
+Jedną z wielu własności języków rozpoznawanych przez automaty
-minimalny taki, że </math>L({A}')<nowiki>=</nowiki>L({A})<math>.
+skończone, i chyba jedną z najważniejszych, przedstawia prezentowane
+poniżej twierdzenie, zwane tradycyjnie w literaturze lematem o
+pompowaniu. Istota własności "pompowania"
+polega na tym, iż automat, mając skończoną ilość stanów, czytając i
+rozpoznając słowa dostatecznie długie, wykorzystuje w swoim
+działaniu pętlę, czyli powraca do stanu, w którym znajdował się
+wcześniej. Przez taką pętlę  automat może przechodzić wielokrotnie,
+a co za tym idzie, "pompować" rozpoznawane słowo, wprowadzając do
+niego wielokrotnie powtarzane podsłowo odpowiadające tej pętli.
-\FOR{\textbf{each} </math>p  T<math>}
+Niech <math>L \subset A^*</math> będzie językiem rozpoznawalnym. Istnieje liczba
+naturalna <math>N \geq 1</math> taka, że
+dowolne słowo <math>{ w} \in L</math>  o długości <math>\mid { w} \mid \geq N </math> można rozłożyć na
+katenację <math>{ w} = { v}_1 { u v}_2,</math> gdzie <math>{ v}_1 , { v}_2 \in A^*, { u}\in A^+</math>,
+<math>\mid {v_{1}u} \mid \leq N</math> oraz
-\FOR{\textbf{each} </math>q  S  T<math>}
+<center><math>{ v}_1 u^* { v}_2 \subset L.</math></center>
-\STATE \textbf{zaznaczone}</math>[p,q]  1<math>;
+Niech <math>L=L(\mathcal{A}) </math>, gdzie <math>\mathcal{A} =(S,A,
+f,s_0,T)</math> jest deterministycznym automatem skończenie stanowym.
+Niech  <math>N = \#S </math> i rozważmy dowolne słowo <math>{ w } = a_1....a_k \in
+L</math> takie, że <math>\mid { w} \mid \geq N</math>. Oznaczmy:
+<center><math>s_1 = f(s_0,a_1), \;\; s_2 = f(s_1,a_2), ..., s_{i+1} = f(s_i,a_{i+1}),..., s_k = f(s_{k-1},a_k). </math></center> Słowo <math>w</math> jest
+akceptowane przez automat <math>\mathcal{A} </math>, więc <math>s_k \in T.</math> Ponieważ <math>\#S = N</math> oraz  <math>k = \mid { w} \mid \geq N</math>,
+to istnieją <math>i,j\in \{1,...,N\} </math>,
+<math>i< j</math> takie, że <math>s_i =s_j</math>.
-\STATE \textbf{initialize}(</math>{L}[p,q]<math>)
+{ Przyjmując teraz <math>{ v}_1 = a_1...a_i ,\;\;\; {
+v}_2 = a_{j+1}...a_k , \;\;\; { u} =a_{i+1}...a_j,</math> dochodzimy do
+nastepującej konkluzji: }
-\ENDFOR
+{ <center><math>f(s_0, { v}_1) = s_i , \;\;\; f(s_j, { v}_2) = s_k \in T, \;\;\;f(s_i,{ u}) = s_i =s_j.</math></center> }
-\ENDFOR
+{ A to oznacza, że słowo <math>v_{1}u^{k}v_{2} </math> jest rozpoznawane przez
+automat <math>\mathcal{A} </math> dla dowolnej liczby <math>k\geq 0 </math>, co
+kończy dowód. Nierówność <math>\mid {v_{1}u} \mid \leq N</math> wynika w oczywisty sposób
+z przyjętego na początku dowodu założenia, że <math>N = \#S</math>.  }
-\FOR{</math>'''each'''(p,q)  (T  T)  ((S  T)
+<math>\diamondsuit</math>
-(S  T))<math>}
-\STATE \textbf{zaznaczone}</math>[p,q]  0<math>;
+Istotę dowodu przedstawia następująca animacja.
-\ENDFOR
+ANIMACJA ja-lekcja6-w-anim2
-\FOR{</math>'''each ''' (p,q)  (T  T)  ((S  T)
+Jeśli rozpoznawalny język <math>L \subset A^*</math> jest nieskończony, to
-(S  T))<math>}
+istnieją słowa <math>{ v}_1 , { u}, { v}_2 \in A^*</math> takie, że
+<center><math>{ v}_1 u^* { v}_2 \subset L \;\; i \;\; { u} \neq 1.</math></center>
-\STATE flag\textbf{false}
+Jeśli rozpoznawalny język <math>L \subset A^*</math> nie jest zbiorem pustym, to
+istnieje słowo <math>w\in L </math>
+takie, że <math>\mid w\mid <N </math>, gdzie <math>N </math> jest stałą występującą
+w lemacie o pompowaniu. <br>
+Jeśli słowo <math>w\in L </math> i <math>\mid w\mid \geq N </math>, to zgodnie z lematem
+o pompowaniu możemy przedstawić słowo <math>w </math> jako <math>w=v_{1}uv_{2}
+</math>, gdzie <math>u\neq 1 </math> oraz <math>v_{1}u^{i}v_{2}\in L </math> dla <math>i=0,1,2\ldots  </math>. Przyjmując <math>i=0 </math>, mamy <math>v_{1}v_{2}\in L </math>
+i <math>\mid v_{1}v_{2}\mid <\mid w\mid  </math>. Powtarzając powyższy
+rozkład skończoną ilość razy, otrzymamy słowo należące do języka <math>L </math>, o długości mniejszej od <math>N </math>.
-\FOR{\textbf{each } </math>a  A<math>}
+Lemat o pompowaniu wykorzystuje się najczęściej do uzasadnienia faktu, iż pewne
+języki nie są rozpoznawane przez automaty skończone. Przyjrzyjmy się bliżej technice
+takiego uzasadnienia.
-\IF{ \textbf{zaznaczone}</math>[f(p,a),f(q,a)]<nowiki>=</nowiki>1<math>}
+{{cwiczenie|[Uzupelnij]||
-\STATE flag\textbf{true};
-\ENDIF
+Rozważmy język <math>L = \{ a^n b^n : n \geq 0 \}</math> nad alfabetem <math>A = \{
-\ENDFOR
+a,b\}</math>. W oparciu o lemat o pompowaniu wykażemy, że język <math>L</math> nie
+jest rozpoznawany. Dla dowodu nie wprost, przypuszczamy, że <math>L</math> jest
+rozpoznawany. Na podstawie udowodnionego lematu istnieją zatem słowa
+<math>{ v}_1 , { u}, { v}_2 \in A^*</math> takie, że <math>{ v}_1 u^* { v}_2 \subset
+L</math> oraz <math>{ u} \neq 1.</math> Biorąc pod uwagę formę słów języka <math>L </math>,
+wnioskujemy, że
-\IF{flag=\textbf{true}}
+* słowo <math>{ u} </math> nie może składać się tylko z liter <math>a</math>, gdyż słowo <math>{ v}_1 { u}^2 { v}_2</math> zawierałoby więcej liter <math>a</math> niż <math>b</math>,
-\STATE \textsc{Oznacz}</math>(p,q)<math>;\hfill  para
+* słowo <math>{ u} </math> nie może składać się tylko z liter <math>b</math>, gdyż słowo <math>{ v}_1 { u}^2 { v}_2</math> zawierałoby więcej liter <math>b</math> niż <math>a</math>,
-</math>(f(p,a),f(q,a))<math> była oznaczona dla pewnego </math>a<math>;
-\ELSE
+* słowo <math>{ u} </math> nie może składać się z liter <math>a \; i \; b</math>, gdyż w słowie <math>{ v}_1 { u}^2 { v}_2</math> litera <math>b</math> poprzedzałaby literę <math>a</math>.
-\FOR{\textbf{each } </math>a  A<math>}
+Ponieważ słowo  <math>{ v}_1 { u}^2 { v}_2,</math>
+należy do języka <math>L </math>, więc każdy z wyprowadzonych powyżej
+wniosków prowadzi do sprzeczności.
-\IF{</math>f(p,a) f(q,a)<math>}
+}}
-\STATE \textbf{włóż}</math>({L}[p,q],(f(p,a),f(q,a)))<math>;
+==Rozstrzygalność==
-\ENDIF
+Udowodniony w poprzedniej części wykładu lemat o pompowaniu wykorzystywany bywa
+również w dowodach rozstrzygalności pewnych problemów w klasie języków rozpoznawalnych.
-\ENDFOR
+W klasie języków regularnych <math>\mathcal{REG}(A^{*}) </math> następujące
+problemy są rozstrzygalne:
-\ENDIF
+#  problem niepustości języka <math>L\neq \emptyset,  </math>
-\ENDFOR
+#  problem nieskończoności języka <math>card\, L=\aleph _{0}, </math>
-\STATE </math>S'  S _<math>;\hfill
+#  problem równości języków <math>L_{1}=L_{2}, </math>
-relacja  jest dopełnieniem tabeli </math>'''zaznaczone'''<math>
-\FOR{\textbf{each} </math>[s]_{ }  S _<math>}
+#  problem należenia słowa do języka <math>w\in L. </math>
-\FOR{\textbf{each} </math>a  A<math>}
+[[##niepusty|Uzupelnic niepusty|]].
+Wystarczy sprawdzić niepustość skończonego podzbioru języka
+<math>L. </math> Prawdziwa jest bowiem równoważność
-\STATE </math>f'([s]_{},a)  [f(s,a)]_{}<math>;
+<center><math>L\neq \oslash \: \Leftrightarrow \: \exists w\in L\, :\, \mid w\mid <N,</math></center>
-\ENDFOR
+gdzie <math>N </math> jest stałą występującą w lemacie o pompowaniu.
+Prawdziwość implikacji <math>\Leftarrow  </math> jest oczywista. Fakt, że
+do niepustego języka należy słowo o długości ograniczonej
+przez <math>N </math>, wynika z lematu o pompowaniu. Jeśli <math>w\in L </math> i <math>\mid w\mid \geq N </math>,
+rozkładamy słowo <math>w </math>   następująco:
-\ENDFOR
+<center><math>w=v_{1}uv_{2},\; \; u\neq 1,\; \; \forall i=0,1,2\ldots \: v_{1}u^{i}v_{2}\in L. </math></center>
-\STATE </math>s_0'  [s_0]_{}<math>;
+Przyjmując <math>i=0 </math> mamy:
-\STATE </math>T'  [t]_{}:t  T<math>;
+<center><math>v_{1}v_{2}\in L,\; \mid v_{1}v_{2}\mid <\mid w\mid </math></center>
-\RETURN </math>{A}'<nowiki>=</nowiki>(S', A, f', s_0', T')<math>;
+Powtarzając powyższy rozkład skończoną ilość razy
+otrzymamy słowo należące do języka, o długości ograniczonej
+przez <math>N </math>.
-\endalgorithmic
+[[##nieskonczony|Uzupelnic nieskonczony|]].
-\endalgorithm
+Należy udowodnić równoważność : <center><math>L \mbox{ nieskończony } \;\; \Longleftrightarrow \;\;\exists w \in L \;\; : \;\; N \leq \mid w \mid < 2N</math></center>
-Występujaca w algorytmie procedura \textsc{Oznacz} opisana jest poniżej.
-\beginalgorithm
+<math>\Longrightarrow  </math> <br>
-\beginalgorithmic [1]
+Jeśli <math>L </math> jest nieskończonym zbiorem, to istnieje słowo <math>w </math>
+dowolnie długie. Niech <math>\mid w\mid \geq N </math>''.'' Jeśli słowo
+<math>w </math> nie spełnia ograniczenia <math>\mid w\mid <2N </math>, to podobnie jak
+poprzednio korzystamy z lematu o pompowaniu i po skończonej ilości
+kroków otrzymamy słowo krótsze od <math>2N </math>. Należy jeszcze zauważyć,
+że wykorzystując lemat o pompowaniu możemy założyć,
+że usuwane słowo <math>u </math> ma długość ograniczoną
+przez <math>N </math>. (Zawsze znajdziemy słowo <math>u </math> spełniające ten
+warunek.) Oznacza to, że ze słowa dłuższego od <math>2N </math> nie
+dostaniemy słowa krótszego od <math>N </math>. <br>
+<math>\Longleftarrow  </math><br>
+Jeśli do języka <math>L </math> należy słowo <math>w </math> o długości
+większej lub równej  <math>N </math>, to z lematu o&nbsp;pompowaniu wynika, że
-\STATE \textbf{procedure} \textsc{Oznacz}</math>(p,q  S)<math>
+<center><math>w=v_{1}uv_{2},\: u\neq 1\;\;\; i\;\;\; v_{1}u^{*}v_{2}\subset L</math></center>
-\IF{\textbf{zaznaczone}</math>[p,q]<nowiki>=</nowiki>1<math>}
+Istnieje więc nieskończony podzbiór zawierający się w <math>L </math>, a zatem język <math>L </math> jest  nieskończony.
-\STATE{ \textbf{return}}
+[[##rownosc|Uzupelnic rownosc|]].
-\ENDIF
+Niech <math>L=(L_{1}\cap \overline{L_{2}})\cup (\overline{L_{1}}\cap L_{2}) </math>.
+Z domkniętości klasy <math>\mathcal{L}_{3} </math> na operaje boolowskie
-\STATE{\textbf{zaznaczone}</math>[p,q] 1<math>}
+wynika, że język <math>L </math> jest regularny. Prawdziwa jest równoważność
-\WHILE{\textbf{not empty}</math>({L}[p,q])<math>}
-\STATE{\textsc{Oznacz}(\textbf{zdejmij}</math>({L}[p,q])<math>)}
-\ENDWHILE
-\STATE \textbf{end procedure}
-\endalgorithmic
-\endalgorithm
-Działanie algorytmu łatwo przedstawić na tabelce, która
-złożona jest z kwadratów -- pól, odpowiadających parom stanów automatu.
-Fakt znalezienia przez algorytm pary stanów rozróżnialnych
-zaznaczamy symbolem "x" w polu tabelki odpowiadającym tej parze, co
-wykorzystamy w przykładzie.
-{{cwiczenie|[Uzupelnij]||
-Zminimalizujemy automat przedstawiony na rysunku
-[[##ja-lekcja5-w-rys4|Uzupelnic ja-lekcja5-w-rys4|]], używając algorytmu \textsc{Minimalizuj3}.
-RYSUNEK ja-lekcja5-w-rys4
-Proces działania algorytmu i konstrukcji tabelki przedstawiony jest
-na poniższej animacji
-}}
-TUTAJ ANIMACJA. Opis animacji znajduje się w pliku
+<center><math>L\neq \emptyset \Longleftrightarrow L_{1}\neq L_{2}. </math></center>
-ja-lekcja5-w-anim1.pdf. Wygląd ekranu animacji znajduje się w pliku
-ja-lekcja5-w-anim1.jpg.\\
-Wypełniona tabelka po zakończeniu działania algorytmu przedstawiona
+Poblem równoważności języków został sprowadzony do problemu
-jest na rysunku [[##ja-lekcja5-w-rys5|Uzupelnic ja-lekcja5-w-rys5|]].
+niepustości.
-RYSUNEK ja-lekcja5-w-rys5.
+[[##nalezenie|Uzupelnic nalezenie|]].
+Konstruujemy automat <math>\mathcal{A} </math></center><nowiki>=</nowiki>(S,f,s_0,T)<math> rozpoznający język
+</math>L <math> i sprawdzamy, czy </math>f(s_{0},w) T. <math>
-Z tabelki odczytujemy, że stanami równoważnymi są stany </math>s_1, s_5<math>,
+\begincenter   \endcenter  \endprf
-stany </math>s_2, s_8<math> oraz stany </math>s_4, s_6<math>. Automat minimalny
-przedstawiony jest na rysunku [[##ja-lekcja5-w-rys6|Uzupelnic ja-lekcja5-w-rys6|]].
-RYSUNEK ja-lekcja5-w-rys6.</math>
+Ilustracją dla powyższego wprowadzenia może być problem skończoności w~klasie
+jezyków regularnych. Problem jest rozstrzygalny, bowiem w oparciu o lemat
+o~pom\-po\-wa\-niu można skonstruować algorytm, który dla dowolnego języka regularnego
+rozstrzygnie ten problem, czyli odpowie twierdząco lub przecząco na pytanie
+o jego skończoność.</math>