Test GR3: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycja
WizualnieWikikod
Gracja (dyskusja | edycje)
4759 edycji
Nie podano opisu zmian
m Zastępowanie tekstu – „ </math>” na „</math>”
 
(Nie pokazano 33 wersji utworzonych przez 3 użytkowników)
Linia 1: Linia 1:
{theor}{TWIERDZENIE}[section]
--- przykładowo jak zrobić pierwsze pytanie z pierwszego modułu ---
{rem}{UWAGA}[section]
{corol}{WNIOSEK}[section]
{fact}{FAKT}[section]
{ex}{PRZYKŁAD}[section]
{defin}{DEFINICJA}[section]
{lem}{LEMAT}[section]


{prf}{DOWÓD}
<quiz type="exclusive">
Dowolna kategoria składa się ze zbioru obiektów i zbioru morfizmów, które
spełniają odpowiednie aksjomaty dotyczące złożenia, identyczności,
dziedzin i kodziedzin morfizmów.
<wrongoption>Prawda</wrongoption>
<rightoption>Fałsz</rightoption>
</quiz>
---------------------------------------------------------------------


{algorithm}{Algorytm}


{ Automat niedeterministyczny, lemat o pompowaniu}
<quiz>
Zaznacz zdania prawdziwe dotyczące podłogi i sufitu:
 
<option><math>n\geq 2^{\left\lceil \log_2 n \right\rceil}</math>,</option>
<option><math>n\leq 2^{\left\lceil \log_2 n \right\rceil}</math>,</option>
<option><math>\left\lceil \log_2 \left\lceil n/2 \right\rceil \right\rceil=\left\lceil \log_2 \left( n/2 \right) \right\rceil</math>,</option>
<option><math>\left\lfloor \log_2 \left\lceil n/2 \right\rceil \right\rfloor=\left\lfloor \log_2 \left( n/2 \right) \right\rfloor</math>.</option>
</quiz>


; 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
<quiz> 
: automat niedeterministyczny, automat niedeterministyczny z pustymi
Dowolny niepusty podzbiór  <math>S\subseteq \mathbb{N}</math>  zbioru liczb naturalnych
przejściami, lemat o pompowaniu.
 
ma w sobie liczbę największą
   
ma w sobie liczbę najmniejszą
ma w sobie liczbę największą oraz liczbę najmniejszą
ma w sobie liczbę najmniejszą ale nigdy nie ma największej
</quiz>


==Automat niedeterministyczny==


Wprowadzony wcześniej automat jest modelem obliczeń, czy też mówiąc
<quiz> 
ogólniej, modelem procesu o bardzo prostym opisie. Stan procesu
Zbiór  <math>S\subseteq\mathbb{N}</math>  jest taki, że jeśli  <math>s\in S</math>  to  <math>s+1\in S</math> .  
zmienia się w sposób jednoznaczny pod wpływem sygnału zewnętrznego
Jeśli  <math>9\in S</math> , to:
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 <math>A </math> nazywamy
<math>S=\mathbb{N}</math>  
system <math>\mathcal{A}_{ND} </math></center> <nowiki>=</nowiki> (S,f),<math> w którym </math>S<math> jest dowolnym zbiorem, zwanym zbiorem
stanów, a </math>f: S  A  {P}(S) <math> funkcją przejść.


\enddefin
<math>S=\mathbb{N}-\left\lbrace 0,1,2,3,4,5,6,7,8 \right\rbrace</math>


Funkcję przejść rozszerzamy do funkcji </math>f: S A^* {P}(S) <math> określonej
<math>S\subseteq\mathbb{N}-\left\lbrace 0,1,2,3,4,5,6,7,8 \right\rbrace</math>  
na całym wolnym monoidzie </math>A^*<math> w następujący sposób:


dla każdego </math>s  S f(s,1) <nowiki>=</nowiki>  s, <math>
<math>S\supseteq\mathbb{N}-\left\lbrace 0,1,2,3,4,5,6,7,8 \right\rbrace</math>  
</quiz>


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>


W związku z powyższą definicją automat wprowadzony wcześniej, w wykładzie 3,
<quiz> 
będziemy nazywać automatem deterministycznym\index{automat deterministyczny}.
Zbiór  <math>S\subseteq\mathbb{N}</math>  jest taki, że jeśli  <math>a,b\in S</math> ,  
to  <math>a+b\in S</math>  oraz  <math>a+b+1\not\in S</math> .  
Jeśli  <math>0,2 \in S</math> , to:


\begindefin
<math>S=\mathbb{N}</math>


Język </math>L A^{*} <math> jest rozpoznawalny przez automat
zbiór <math>S</math>  zawiera wszystkie liczby naturalne, które są parzyste
nie\-de\-ter\-mi\-nis\-tycz\-ny </math>{A}_{ND} <nowiki>=</nowiki>(S,f)<math>
wtedy i tylko wtedy, gdy istnie\-je </math>I S<math> -- zbiór stanów
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>


\enddefin
zbiór  <math>S</math>  jest zawarty w zbiorze liczb naturalnych, które są parzyste


Niedeterministyczny automat rozpoznający język </math>L<math> będziemy oznaczać jako
zbiór  <math>S</math>  jest zbiorem wszystkich liczb naturalnych, które są parzyste
system </math>{A}_{ND} <nowiki>=</nowiki> (S,A,f,I,F)<math> lub </math>{A}_{ND}<nowiki>=</nowiki>(S,f,I,F), <math>
</quiz>
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
<quiz> 
Ostatnią cyfrą liczby  <math>3^{3^n}</math>  jest:


Język </math>L  A^*<math> jest rozpoznawany przez automat deter\-mi\-nis\-tycz\-ny wtedy i tylko wtedy, gdy jest rozpoznawany
zawsze  <math>3</math>  
przez automat nie\-de\-ter\-mi\-nis\-tycz\-ny.


\endtheor
zawsze  <math>3</math>  lub  <math>7</math>


\beginprf
zawsze  <math>7</math>


Rozpocznijmy dowód od oczywistej obserwacji. Zauważmy, iż każdy
jakakolwiek z cyfr  <math>0,1,2,3,4,5,6,7,8,9</math>
automat deterministyczny można przekształcić w
</quiz>
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 </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></center>L({A}_{D})<nowiki>=</nowiki>w A^{*}: {f}(I,w)
<quiz>
T<nowiki>=</nowiki>L<nowiki>=</nowiki>L({A}_{ND}).<center><math>
Jeśli <math>Z \subseteq \mathbb{N}</math> jest jakimś zbiorem liczb naturalnych,  
który wraz z każdym początkowym fragmentem zbioru  <math>\mathbb{N}</math>
postaci <math>\left\lbrace 0,\ldots,k-1 \right\rbrace</math> zawiera również kolejną liczbę  <math>k</math>, to wtedy


Skonstruowany automat jest zatem
zbiór  <math>Z</math>  zawiera wszystkie liczby naturalne poza skończonym podzbiorem
deterministyczny i równoważny wyjściowemu,
co kończy dowód twierdzenia.


\begincenter  \endcenter \endprf
zbiór <math>Z</math>  zawiera wszystkie liczby naturalne


{{uwaga|[Uzupelnij]||
zbiór  <math>Z</math>  zawiera nieskończenie wiele liczb naturalnych


Dla określonego w dowodzie automatu </math>{A}_{D} <math> na ogół
zbiór  <math>Z</math> jest pusty
nie wszystkie stany są osiągalne ze stanu </math>I<math>. Aby uniknąć takich
</quiz>
stanów, które są bezużyteczne, funkcję przejść należy zacząć
definiować od stanu </math>I<math> i kolejno  określać wartości
dla już osiągniętych stanów.


}}


{{cwiczenie|[Uzupelnij]||
<quiz> 
Grupa uczniów stojących przed klasą skłóciła się do tego stopnia, że nikt z nikim się nie lubił. Jeden z nich, aby naprawić relacje, wymyślił, że jeżeli wszyscy znajdujący się wewnątrz klasy będą pogodzeni, to nie powinno być problemu, aby któryś stojący na zewnątrz klasy wszedł do środka i pogodził się ze wszystkimi, będącymi w klasie. Drugi z nich zauważył jednak, że nic z tego nie wyjdzie, bo w środku nikogo nie ma. Czy klasa jest w stanie się pogodzić?


Automat </math>{A}_{ND}  <nowiki>=</nowiki> (Q,A,f,I,F)<math> nad alfabetem </math>A<nowiki>=</nowiki>a,b <math>
klasa na pewno się nie pogodzi
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.\\


RYSUNEK ja-lekcja6-w-rys1
klasa się pogodzi, jeżeli każdy pójdzie za radą pierwszego ucznia


Automat ten, jak łatwo teraz zauważyć, rozpoznaje język </math>L({A})<nowiki>=</nowiki>A^*abb <math>.
jeżeli w klasie byłaby już jedna osoba, to reszta klasy miałaby szansę się pogodzić


}}
jeżeli w klasie byłyby już co najmniej dwie osoby,
przy czym osoby w klasie byłyby ze sobą pogodzone,
to reszta klasy miałaby szansę się pogodzić
</quiz>


Przedstawimy teraz algorytm, który mając na wejściu automat niedeterministyczny konstruuje
   
równoważny automat deterministyczny.
<quiz>   
 
Jeśli <math>S\subseteq\mathbb{N}</math> , to:
\newpage
   
 
zbiór <math>S</math>  ma element największy
\beginalgorithm \caption{\textsc{Determinizacja} -- buduje deterministyczny automat
   
równoważny automatowi niedeterministycznemu}
zbiór <math>S</math>  ma element najmniejszy
\beginalgorithmic [1]
   
\STATE Wejście: </math>{A}<nowiki>=</nowiki>(S, A, f, s_0, T)<math> -- automat
zbiór <math>S</math>  ma element największy, o ile <math>S</math>  jest niepusty
niedeterministyczny.
   
 
zbiór <math>S</math>  ma element najmniejszy, o ile <math>S</math>  jest niepusty
\STATE Wyjście: </math>{A}'<nowiki>=</nowiki>(S', A, f', s_0', T')<math> -- automat
</quiz>
deterministyczny taki, że </math>L({A}')<nowiki>=</nowiki>L({A})<math>.
 
\STATE </math>S' s_0<math>;
 
\STATE </math>s_0'  s_0<math>;
 
\STATE </math>{L}  s_0<math>;  \hfill
</math>{L}<math> jest kolejką
 
\WHILE{</math>{L}  <nowiki>=</nowiki> <math>}
 
\STATE </math>M
'''zdejmij'''({L})<math>;
 
\STATE \textbf{if } </math>T  M  <nowiki>=</nowiki> <math> \textbf{ then } </math>T'
T'  M<math>;
 
\FOR{\textbf{each} </math>a  A<math>}
 
\STATE </math>N _{m  M} f(m,a)<math>;
 
\IF{</math>N  S'<math>}
 
{
\STATE </math>S'  S'  N<math>;
\STATE \textbf{włóż}</math>({L},N)<math>;
}
 
\ENDIF
 
\STATE </math>f'(M, a)  N<math>;
 
\ENDFOR
 
\ENDWHILE
 
\RETURN </math>{A}'<math>;
 
\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łóż}</math>({L},N)<math> z linii
[[##a1_l12|Uzupelnic a1_l12|]]. wstawia na koniec kolejki </math>{L}<math> element </math>N<math>.
 
Należy zauważyć, że algorytm determinizujący automat jest algorytmem
eksponencjalnym. Stany wyjściowego automatu deterministycznego
etykietowane są podzbiorami zbioru stanów </math>Q<math>. Jeśli pewien stan </math>q'
Q'<math> etykietowany jest zbiorem zawierającym stan końcowy z </math>F<math>,
to </math>q'<math> staje się stanem końcowym w automacie </math>{A}'<math>.
 
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
</math>O(2^n)<math>, gdzie </math>n<math> 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 </math>A <math> nazy\-wa\-my
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ść.
 
{{uwaga|[Uzupelnij]||
 
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.
 
}}
 
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 <math>\mathcal{A}{^p}_{ND} </math></center> <nowiki>=</nowiki>
(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
 
</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>
 
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 </math>s  S<math> oraz </math>w<nowiki>=</nowiki>ua A<math>, to
</math></center> f(s,w)<nowiki>=</nowiki>f(s,ua)<nowiki>=</nowiki>f(f(s,u),a).<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.
 
\begintheor
Język </math>L A^*<math> 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 </math>L<math>  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 </math>L<math>, by uzyskać automat bez pustych przejść i
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>.
 
<math>\diamondsuit</math>   
 
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 <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
 
<center><math>{ v}_1 u^* { v}_2 \subset L.</math></center>
 
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>.
 
{ 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: }
 
{ <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> }
 
{ 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>.  }
 
<math>\diamondsuit</math>   
 
Istotę dowodu przedstawia następująca animacja.
 
ANIMACJA ja-lekcja6-w-anim2
 
Jeśli rozpoznawalny język <math>L \subset A^*</math> jest nieskończony, to
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>
 
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>.
 
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.
 
{{cwiczenie|[Uzupelnij]||
 
Rozważmy język <math>L = \{ a^n b^n : n \geq 0 \}</math> nad alfabetem <math>A = \{
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
 
* 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>,
 
* 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>,
 
* 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>.
 
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.
 
}}
 
==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 <math>\mathcal{REG}(A^{*}) </math> następujące
problemy są rozstrzygalne:
 
#  problem niepustości języka <math>L\neq \emptyset,  </math>
 
#  problem nieskończoności języka <math>card\, L=\aleph _{0}, </math>
 
#  problem równości języków <math>L_{1}=L_{2}, </math>
 
# problem należenia słowa do języka <math>w\in L. </math>
 
[[##niepusty|Uzupelnic niepusty|]].
Wystarczy sprawdzić niepustość skończonego podzbioru języka
<math>L. </math> Prawdziwa jest bowiem równoważność
 
<center><math>L\neq \oslash \: \Leftrightarrow \: \exists w\in L\, :\, \mid w\mid <N,</math></center>
 
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:
 
<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>
 
Przyjmując <math>i=0 </math> mamy:
 
<center><math>v_{1}v_{2}\in L,\; \mid v_{1}v_{2}\mid <\mid w\mid </math></center>
 
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>.
 
[[##nieskonczony|Uzupelnic nieskonczony|]].
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>
 
<math>\Longrightarrow  </math> <br>
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
 
<center><math>w=v_{1}uv_{2},\: u\neq 1\;\;\; i\;\;\; v_{1}u^{*}v_{2}\subset L</math></center>
 
Istnieje więc nieskończony podzbiór zawierający się w <math>L </math>, a zatem język <math>L </math> jest  nieskończony.
[[##rownosc|Uzupelnic rownosc|]].
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
wynika, że język <math>L </math> jest regularny. Prawdziwa jest równoważność
 
<center><math>L\neq \emptyset \Longleftrightarrow L_{1}\neq L_{2}. </math></center>
 
Poblem równoważności języków został sprowadzony do problemu
niepustości.
 
[[##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>
 
\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ść.</math>

Aktualna wersja na dzień 11:02, 5 wrz 2023

--- przykładowo jak zrobić pierwsze pytanie z pierwszego modułu ---

Dowolna kategoria składa się ze zbioru obiektów i zbioru morfizmów, które spełniają odpowiednie aksjomaty dotyczące złożenia, identyczności, dziedzin i kodziedzin morfizmów.

Prawda

Fałsz


Zaznacz zdania prawdziwe dotyczące podłogi i sufitu:


n≥2⌈log2n⌉,

n≤2⌈log2n⌉,

⌈log2⌈n/2⌉⌉=⌈log2(n/2)⌉,

⌊log2⌈n/2⌉⌋=⌊log2(n/2)⌋.


Dowolny niepusty podzbiór S⊆ℕ zbioru liczb naturalnych


ma w sobie liczbę największą

ma w sobie liczbę najmniejszą

ma w sobie liczbę największą oraz liczbę najmniejszą

ma w sobie liczbę najmniejszą ale nigdy nie ma największej


Zbiór S⊆ℕ jest taki, że jeśli s∈S to s+1∈S . Jeśli 9∈S , to:

S=ℕ

S=ℕ−{0,1,2,3,4,5,6,7,8}

S⊆ℕ−{0,1,2,3,4,5,6,7,8}

S⊇ℕ−{0,1,2,3,4,5,6,7,8}


Zbiór S⊆ℕ jest taki, że jeśli a,b∈S , to a+b∈S oraz a+b+1∉S . Jeśli 0,2∈S , to:

S=ℕ

zbiór S zawiera wszystkie liczby naturalne, które są parzyste

zbiór S jest zawarty w zbiorze liczb naturalnych, które są parzyste

zbiór S jest zbiorem wszystkich liczb naturalnych, które są parzyste


Ostatnią cyfrą liczby 33n jest:

zawsze 3

zawsze 3 lub 7

zawsze 7

jakakolwiek z cyfr 0,1,2,3,4,5,6,7,8,9


Jeśli Z⊆ℕ jest jakimś zbiorem liczb naturalnych, który wraz z każdym początkowym fragmentem zbioru ℕ postaci {0,…,k−1} zawiera również kolejną liczbę k, to wtedy

zbiór Z zawiera wszystkie liczby naturalne poza skończonym podzbiorem

zbiór Z zawiera wszystkie liczby naturalne

zbiór Z zawiera nieskończenie wiele liczb naturalnych

zbiór Z jest pusty


Grupa uczniów stojących przed klasą skłóciła się do tego stopnia, że nikt z nikim się nie lubił. Jeden z nich, aby naprawić relacje, wymyślił, że jeżeli wszyscy znajdujący się wewnątrz klasy będą pogodzeni, to nie powinno być problemu, aby któryś stojący na zewnątrz klasy wszedł do środka i pogodził się ze wszystkimi, będącymi w klasie. Drugi z nich zauważył jednak, że nic z tego nie wyjdzie, bo w środku nikogo nie ma. Czy klasa jest w stanie się pogodzić?

klasa na pewno się nie pogodzi

klasa się pogodzi, jeżeli każdy pójdzie za radą pierwszego ucznia

jeżeli w klasie byłaby już jedna osoba, to reszta klasy miałaby szansę się pogodzić

jeżeli w klasie byłyby już co najmniej dwie osoby, przy czym osoby w klasie byłyby ze sobą pogodzone, to reszta klasy miałaby szansę się pogodzić


Jeśli S⊆ℕ , to:

zbiór S ma element największy

zbiór S ma element najmniejszy

zbiór S ma element największy, o ile S jest niepusty

zbiór S ma element najmniejszy, o ile S jest niepusty

Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Test_GR3&oldid=81550”