Test GR3

{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

${{𝒜}}_{ND}$

= (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

$orazdowolnego$

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

$zbioru$

f(s,w)

$ilitery$

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)$lub${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}) $,gdzie${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) $orazdowolnejlitery$

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)$nadalfabetem$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 = $\text{<mrow data-mjx-texclass="ORD">then</mrow>}$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}$element$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$,to$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)$,gdzie$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}_{ND}$ = (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$oraz$w=a A$,to$

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$oraz$w=ua A$,to$

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

$Stanyzezbioru$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$.

$\mathrm{♢}$

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\ge 1$ taka, że dowolne słowo $w\in L$ o długości $\mid w\mid \ge N$ można rozłożyć na katenację $w=v_1{uv}_2,$ gdzie $v_1,v_2\in A^{*},u\in A^{+}$, $\mid v_{1}u\mid \le 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=\mathrm{\#}S$ i rozważmy dowolne słowo $w=a_1....a_k\in L$ takie, że $\mid w\mid \ge 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ż $\mathrm{\#}S=N$ oraz $k=\mid w\mid \ge 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\ge 0$, co kończy dowód. Nierówność $\mid v_{1}u\mid \le N$ wynika w oczywisty sposób z przyjętego na początku dowodu założenia, że $N=\mathrm{\#}S$. }

$\mathrm{♢}$

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 Liu\ne 1.$

Jeśli rozpoznawalny język $L\subset A^{*}$ nie jest zbiorem pustym, to istnieje słowo $w\in L$ takie, że $\mid w\mid <N$, gdzie $N$ jest stałą występującą w lemacie o pompowaniu.
Jeśli słowo $w\in L$ i $\mid w\mid \ge N$, to zgodnie z lematem o pompowaniu możemy przedstawić słowo $w$ jako $w=v_{1}u{v}_2$, gdzie $u\ne 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 $\mid v_1{v}_2\mid <\mid w\mid$. 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\ge 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\ne 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 $aib$, 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:

1. problem niepustości języka $L\ne \mathrm{\varnothing },$

1. problem nieskończoności języka $cardL={\mathrm{\aleph }}_0,$

1. problem równości języków $L_1=L_2,$

1. 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 $\mid w\mid \ge 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,\mid v_1{v}_2\mid <\mid w\mid$

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\text{ nieskończony }⟺\mathrm{\exists }w\in L:N\le \mid w\mid <2N$

$⟹$
Jeśli $L$ jest nieskończonym zbiorem, to istnieje słowo $w$ dowolnie długie. Niech $\mid w\mid \ge N$. Jeśli słowo $w$ nie spełnia ograniczenia $\mid w\mid <2N$, to podobnie jak poprzednio korzystamy z lematu o pompowaniu i po skończonej ilości kroków otrzymamy słowo krótsze od $2N$. 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 $2N$ 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\ne \mathrm{\varnothing }⟺L_1\ne 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 $isprawdzamy,czy$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ść.}