Tekst źródłowy strony Języki, automaty i obliczenia/Wykład 3: Automat skończenie stanowy

W rozdziale tym zdefiniujemy automat - drugi, obok gramatyki, model
obliczeń. Określimy język rozpoznawany przez automat i podamy warunki równoważne na to, by język był rozpoznawany.
__FORCETOC__
==Automaty==

Wprowadzimy teraz pojęcie automatu. Jak już wspomnieliśmy w 
wykładzie drugim automat to drugi, obok gramatyki, model obliczeń 
będący przedmiotem badań teorii języków i automatów. Model 
realizujący  warunek efektywności analitycznej, czyli taki na 
podstawie którego możliwe jest sformułowanie algorytmu 
rozstrzygającego w skończonej liczbie kroków, czy dowolne słowo 
należy, czy też nie należy do  języka rozpoznawanego przez ten 
automat. Lub inaczej możemy powiedzieć, że taki automat daje 
algorytm efektywnie rozstrzygający, czy dowolne obliczenie 
sformułowane nad alfabetem automatu jest poprawne.

Wprowadzony w tym wykładzie automat, zwany automatem skończenie stanowym, jest jednym
z najprostszych modeli obliczeń. Jest to model z bardzo istotnie ograniczoną pamięcią.
Działanie takiego automatu sprowadza się do zmiany stanu  pod
wpływem określonego zewnętrznego sygnału czy impulsu.

Pomimo tych ograniczeń urządzenia techniczne oparte o modele takich 
automatów spotkać możemy dość często. Jako przykład służyć mogą 
automatyczne drzwi, automaty sprzedające napoje, winda, czy też 
urządzenia sterujące taśmą produkcyjną.

{{przyklad|1.1.||

Drzwi automatycznie otwierane są sterowane automatem, którego działanie opisać
można, przyjmując następujące oznaczenia. Fakt, że osoba chce wejść do pomieszczenia
zamykanego przez takie drzwi, identyfikowany przez odpowiedni czujnik, opiszemy symbolem
<math>\displaystyle WE</math>. Zamiar wyjścia symbolem <math>\displaystyle WY</math>. Symbol <math>\displaystyle WEWY</math> będzie związany z równoczesnym zamiarem
wejścia jakiejś osoby i wyjścia innej. Wreszcie symbol <math>\displaystyle BRAK</math> oznaczał będzie brak osób, które
chcą wejść lub wyjść. Zatem zbiór <math>\displaystyle \{ WE, WY,WEWY,BRAK \}</math>, to alfabet nad którym określimy automat
o <math>\displaystyle 2</math> stanach: <math>\displaystyle\{ OTWARTE, ZAMKNIĘTE<\}/math> poniższym grafem.
}}

{| border="0" align="center" cellspacing="10"
|<div class="thumb"><div style="width:270px;">
<flash>file=ja-lekcja03-w-rys6.swf|width=270|height=270</flash>
<div.thumbcaption>Rysunek 1</div>
</div></div>
|<div class="thumb"><div style="width:250px;">
<flashwrap>file=ja-lekcja03-w-rys7.swf|size=small</flashwrap>
<div.thumbcaption>Animacja 1</div>
</div></div>
|}

Automaty reagują więc na określone sygnały zewnętrzne reprezentowane 
przez litery alfabetu <math>\displaystyle A</math>, zmieniając swój stan.  Jeśli ustalimy  
stan początkowy automatu oraz dopuszczalne stany końcowe, to automat 
będzie testował dowolne słowo z  <math>\displaystyle A^{*}  </math> ,  startując ze stanu 
początkowego. Jeśli rezultatem finalnym działania automatu 
(obliczenia) będzie stan końcowy, to słowo będzie rozpoznawane przez 
automat, a obliczenie określone takim słowem poprawne. Automaty można graficznie reprezentować jako etykietowane grafy skierowane. W takim grafie każdy wierzchołek odpowiada stanowi automatu, a każda strzałka  pomiędzy wierzchołkami <math>\displaystyle u</math> i <math>\displaystyle v</math>, etykietowana symbolem <math>\displaystyle a</math>, oznacza przejście automatu ze stanu <math>\displaystyle u</math> do stanu <math>\displaystyle v</math> pod wpływem litery <math>\displaystyle a</math>. 
Podamy teraz definicję automatu. Niech <math>\displaystyle A</math> oznacza dowolny alfabet.
Od tego momentu wykładu zakładamy, że alfabet jest zbiorem skończonym.

{{definicja|1.1||

'''Automatem''' nad alfabetem  <math>\displaystyle A  </math>  nazywamy system  <math>\displaystyle \mathcal{A}  \displaystyle =(S,f)</math>,
w którym

<math>\displaystyle S</math> - jest dowolnym skończonym zbiorem zwanym zbiorem stanów,

<math>\displaystyle f: S \times A \rightarrow S</math> - jest funkcją przejść.

}}

Automat będąc w stanie  <math>\displaystyle s_{i}  </math>  po przeczytaniu litery  <math>\displaystyle a  </math>  zmienia
stan na  <math>\displaystyle s_{j}  </math>  zgodnie z funkcją przejścia  <math>\displaystyle f(s_{i},a)=s_{j}  </math> .

Funkcję przejść rozszerzamy na cały wolny monoid  <math>\displaystyle A^{*}  </math>  do postaci 

<center><math>\displaystyle f: S \times A^* \rightarrow S,</math></center>
przyjmując:

dla każdego <math>\displaystyle  s \in S\;\;\;f(s,1) = s </math> oraz

dla każdego <math>\displaystyle s \in S,\;\;a \in A</math> i dla dowolnego <math>\displaystyle w \in A^*</math>

<center><math>\displaystyle 
f(s,wa) = f(f(s,w),a).
</math></center>

Działanie automatu pokazane jest na poniższej animacji 2.
<center>
<div class="thumb"><div style="width:250px;">
<flashwrap>file=ja-lekcja03-w-rys1.swf|size=small</flashwrap>
<div.thumbcaption>Animacja 2</div></div></div>
</center>

Zdefiniowany powyżej automat  <math>\displaystyle \mathcal{A}  </math>  nazywamy '''skończonym''' lub
'''skończenie stanowym''' ze względu na założenie skończoności zbioru stanów <math>\displaystyle S</math>.<br>

<span id="przyklad_1_2">{{przyklad|1.2.||

Niech  <math>\displaystyle A=\left\{ a,b\right\}   </math>  będzie alfabetem, a  <math>\displaystyle \mathcal{A}=(S,f)  </math> 
automatem takim, że

<math>\displaystyle S=\left\{ s_{0},s_{1},s_{2}\right\}   </math> , a funkcja przejść zadana jest przy
pomocy tabelki
}}</span>

<center><math>\displaystyle \begin{array} {c|c|c|c|c|} f & s_0 & s_1 & s_2\\
\hline a & s_1 & s_2 & s_2\\
\hline b & s_0 & s_0 & s_0\\
\hline \end{array}  </math></center>


Automat możemy również jednoznacznie określić przy pomocy grafu.

<center>
<div class="thumb"><div style="width:350px;">
<flash>file=ja-lekcja03-w-rys2.swf|width=350|height=150</flash>
<div.thumbcaption>Rysunek 2</div>
</div></div>
</center>


Podamy teraz bardzo interesujący przykład zastosowania automatów  skończonych.
Przedstawimy mianowicie wykorzystanie  tak zwanych
automatów synchronizujących w przemyśle. Automat synchronizujący nad alfabetem <math>\displaystyle A</math> to
automat <math>\displaystyle (S,f)</math>  o
następującej własności: istnieje stan <math>\displaystyle t \in S</math> oraz słowo <math>\displaystyle w \in
A^*</math> takie, że dla każdego stanu <math>\displaystyle s</math> tego automatu <math>\displaystyle   f(s, w)=t</math>. Istnieje więc pewne uniwersalne
słowo <math>\displaystyle w</math>, pod wpływem którego wszystkie stany przechodzą w jeden,
ustalony stan automatu <math>\displaystyle t \in S</math>. Mówimy, że następuje wtedy synchronizacja
wszystkich stanów automatu.

Poniżej prezentujemy przykład zaczerpnięty z pracy Ananicheva i
Volkova (D. S. Ananichev, M. V. Volkov, Synchronizing Monotonic
Automata, ''Lecture Notes in Computer Science'', 2710(2003),
111-121.), ukazujący ideę użycia automatów synchronizujących w tej
dziedzinie.

<div class="thumb tright"><div style="width:250px;">
<flash>file=ja-lekcja03-w-rys-s1.swf|width=250|height=100</flash>
<div.thumbcaption>Rysunek 3</div>
</div></div>
<div class="thumb tright"><div style="width:250px;">
<flash>file=ja-lekcja03-w-rys-s2.swf|width=250|height=100</flash>
<div.thumbcaption>Rysunek 4</div>
</div></div>
<div class="thumb tright"><div style="width:250px;">
<flash>file=ja-lekcja03-w-rys-s3.swf|width=250|height=250</flash>
<div.thumbcaption>Rysunek 5</div>
</div></div>

{{przyklad|1.3.||

Załóżmy, że pewna fabryka produkuje detale w kształcie kwadratu z
"wypustką" na jednym boku (patrz rys. 3). Po 
wyprodukowaniu detale należy umieścić w opakowaniach w ten sposób, 
by wszystkie były w tej samej orientacji - mianowicie "wypustką" w 
lewo.

Załóżmy ponadto dla uproszczenia, że detale mogą przyjmować jedną z
czterech orientacji (rys. 4): "wypustką" w
górę, w dół, w lewo lub w prawo.

Należy zatem skonstruować takie urządzenie (orienter), które będzie
ustawiało wszystkie detale w żądanej orientacji. Oczywiście istnieje
wiele metod rozwiązania tego problemu, ale z praktycznego punktu
widzenia potrzebne jest rozwiązanie najprostsze i najtańsze. Jednym
z takich sposobów jest umieszczanie detali na pasie transmisyjnym z
zamontowaną wzdłuż niego pewną ilością przeszkód dwojakiego rodzaju:
niskich (''low'') oraz wysokich (''HIGH''). Wysoka
przeszkoda ma tę własność, że każdy detal, który ją napotka, 
zostanie obrócony o 90 stopni w prawo (zakładamy, że elementy jadą 
od lewej do prawej strony). Przeszkoda niska obróci o 90 stopni w 
prawo tylko te detale, które są ułożone "wypustką" w dół. Na rys. 5
przedstawione zostały przejścia pomiędzy 
orientacjami detali w zależności od napotkania odpowiedniej 
przeszkody.

Można zauważyć, że automat z rysunku 5 jest
automatem synchronizującym. Słowem, które go synchronizuje, jest
następująca sekwencja przeszkód:

low-HIGH-HIGH-HIGH-low-HIGH-HIGH-HIGH-low.

Niezależnie od tego, w jakiej orientacji początkowej znajduje się
detal, po przejściu przez powyższą sekwencję przeszkód zawsze będzie
ułożony "wypustką" w lewo. Sytuację przedstawia poniższa animacja 3:
}}
<div class="thumb center"><div style="width:250px;">
<flashwrap>file=ja-lekcja03-w-anim-s4.swf|size=small</flashwrap>
<div.thumbcaption>Animacja 3</div></div></div>

Rozszerzymy teraz wprowadzone pojęcie automatu w ten sposób, by 
uzyskać możliwość efektywnego rozstrzygania, czy dowolne słowo 
utworzone nad alfabetem <math>\displaystyle A</math> reprezentuje poprawne obliczenie, czyli 
spełnia kryteria określone przez rozszerzony automat.

{{definicja|1.2.||

'''Język''' <math>\displaystyle \; L~\subset A^* \;</math> jest '''rozpoznawany''' ('''akceptowany''')
wtedy i tylko wtedy, gdy istnieje automat skończony  <math>\displaystyle \mathcal{A}  \displaystyle = (S,f) , \;</math> stan <math>\displaystyle \; s_0 \in S \;</math> oraz zbiór <math>\displaystyle \; T \subset S \;</math> takie, że
<center><math>\displaystyle L = \{ w \in A^* \; : \; f(s_0,w) \in T \}. </math></center>
Stan <math>\displaystyle s_0 \;</math> nazywamy '''stanem początkowym''',
a <math>\displaystyle \; T \;</math> '''zbiorem stanów końcowych''' automatu  <math>\displaystyle \mathcal{A}  </math> .

}}

Rozszerzony w powyższy sposób automat, poprzez dodanie stanu początkowgo i zbioru stanów końcowych, w dalszym ciągu
nazywamy automatem i oznaczamy jako piątkę  <math>\displaystyle \mathcal{A}  \displaystyle = (S,A,f,s_0,T)</math> lub czwórkę  <math>\displaystyle \mathcal{A}  \displaystyle =(S,f,s_0,T)</math>, jeśli
wiadomo, nad jakim alfabetem rozważamy działanie automatu.

Fakt, że język <math>\displaystyle \; L \;</math> jest rozpoznawany przez automat  <math>\displaystyle \mathcal{A},  </math>  zapisujemy jako 

<center><math>\displaystyle L=L(\mathcal{A}). </math></center>

Rodzinę wszystkich języków rozpoznawalnych nad alfabetem <math>\displaystyle A</math>
oznaczamy przez  <math>\displaystyle \mathcal{REC}(\mathcal{A}^{*})  </math> .

Podobnie jak w przypadku gramatyk nie ma jednoznacznej odpowiedniości pomiędzy językami
rozpoznawalnymi a automatami. Wprowadza się więc relację, która identyfikuje
automaty rozpoznające ten sam język.

{{definicja|1.3.||

Automaty  <math>\displaystyle \mathcal{A}_{1}  </math>  i  <math>\displaystyle \mathcal{A}_{2}  </math>  są '''równoważne''',
jeśli rozpoznają ten sam język, czyli

<center><math>\displaystyle L(\mathcal{A}_{1})=L(\mathcal{A}_{2}).</math></center>

}}

W dalszych rozważaniach języków rozpoznawanych ograniczymy się do automatów
<math>\displaystyle \mathcal{A}  \displaystyle = (S,A,f,s_0,T)</math>,
które spełniają warunek  <math>\displaystyle f(s_0,A^*) = S.</math>
Nie zawęża to naszych rozważań. Jeśli bowiem język <math>\displaystyle \; L \;</math> jest rozpoznawany
przez pewien automat  <math>\displaystyle \mathcal{A}  \displaystyle = (S,A,f,s_0,T)</math>, to jest również
rozpoznawany przez automat

<center><math>\displaystyle \mathcal{B}=\left( f(s_{0},A^{*}),A,f|_{f(s_{0},A^{*})\times A^{*}},s_{0},T\cap f(s_{0},A^{*})\right) ,</math></center>

który spełnia powyższy warunek. Zauważmy, że przyjmując to założenie, upraszczamy strukturę
automatu. Z punktu widzenia grafu automatu można powiedzieć, że nie występują w nim
wierzchołki (stany) nieosiagalne z <math>\displaystyle s_0</math>.  Poniżej przedstawiamy algorytm usuwający
z automatu stany nieosiągalne ze stanu początkowego.

{{algorytm|UsuńStanyNieosiągalne - usuwa z automatu
<math>\displaystyle \mathcal{A}</math> stany nieosiągalne||

   1  Wejście: <math>\displaystyle \mathcal{A}=(S, A, f, s_0, T)</math> - automat.
   2  Wyjście: <math>\displaystyle \mathcal{A}'=(S', A, f', s_0, T')</math> - automat równoważny automatowi <math>\displaystyle \mathcal{A}</math> bez<br>     stanów nieosiągalnych.
   3  '''for''' '''each''' <math>\displaystyle p\in S</math> '''do'''
   4    '''zaznaczone'''<math>\displaystyle [p] \leftarrow 0</math>;
   5  '''end''' '''for'''
   6  '''zaznaczone'''<math>\displaystyle [s_0] \leftarrow 1</math>;
   7  OZNACZ<math>\displaystyle (s_0)</math>;
   8  <math>\displaystyle S' \leftarrow \{s \in S:\</math> '''zaznaczone''' <math>\displaystyle  [s]=1\}</math>;
   9  <math>\displaystyle T' \leftarrow T \cap S'</math>;
  10  flag<math>\displaystyle \leftarrow</math>'''false'''   <math>\displaystyle \triangleright</math> jeśli nie dodamy stanu to na końcu pętli nadal flag<nowiki>=</nowiki>'''false'''
  11  <math>\displaystyle f' \leftarrow f</math>;
  12  '''for''' '''each''' <math>\displaystyle p \in S</math> '''do'''
  13    '''for''' '''each''' <math>\displaystyle a\in A</math> '''do'''
  14      '''if''' <math>\displaystyle f'(p,a)=</math>NULL '''then'''
  15        <math>\displaystyle f'(p,a)\leftarrow s_f</math>;                         <math>\displaystyle \triangleright\displaystyle f'(p,a)</math> była nieokreślona
  16        flag <math>\displaystyle \leftarrow</math>'''true'''; 
  17      '''end''' '''if'''
  18    '''end''' '''for'''
  19  '''end''' '''for'''
  20  '''if''' flag<nowiki>=</nowiki>'''true''' '''then'''
  21    <math>\displaystyle S'\leftarrow S'\cup \{s_f\}</math>;
  22  '''end''' '''if''' 
  23  '''return''' <math>\displaystyle \mathcal{A}'=(S', A, f', s_0, T')</math>;
}}


{{algorytm|Procedure Oznacz||


   1  '''procedure''' OZNACZ<math>\displaystyle (x \in S)</math>
   2  '''for''' '''each''' <math>\displaystyle p \in S</math> 
   3    flag<math>\displaystyle \leftarrow</math>'''false'''
   4    '''for''' '''each''' <math>\displaystyle a \in A</math> '''do'''
   5      '''if''' <math>\displaystyle f(x,a)=p</math> '''then'''
   6        flag<math>\displaystyle \leftarrow</math>'''true'''
   7      '''end''' '''if'''
   8    '''end''' '''for'''
   9    '''if''' flag<nowiki>=</nowiki>'''true''' '''and zaznaczone'''<math>\displaystyle [p]=0</math> '''then'''
  10      '''zaznaczone'''<math>\displaystyle [p] \leftarrow 1</math>;
  11      OZNACZ<math>\displaystyle (p)</math>;
  12    '''end''' '''if'''
  13  '''end''' '''for'''
  14  '''end procedure'''


}}


Powyższy algorytm, dla ustalonego
alfabetu <math>\displaystyle A</math>, posiada złożoność <math>\displaystyle O(|A| \cdot |S|)</math>, czyli liniową
względem liczby stanów.

Przedstawiając automat przy pomocy grafu przyjmujemy następującą konwencję.
Jeśli w automacie występuje stan początkowy, oznaczać go  będziemy zieloną strzałką wchodzącą do tego stanu. Jeśli w automacie występują stany końcowe, oznaczać je będziemy niebieską obwódką.


{{przyklad|1.4.||

Jeśli w przykładzie 1.2 (patrz [[#przyklad_1_2|przykład 1.2.]])  przyjmiemy stan  <math>\displaystyle s_{0}  </math>  jako stan
początkowy,  <math>\displaystyle T=\left\{ s_{2}\right\}   </math>  jako zbiór stanów końcowych, to
automat <math>\displaystyle \mathcal{A} = (S,A,f,s_0,T)</math>  rozpoznaje język 

<center><math>\displaystyle L(\mathcal{A})= A^{*}\left\{ a^2\right\}</math></center>

złożony ze słów, kończących się na  <math>\displaystyle a^2  </math> .<br>
Słowo <math>\displaystyle aba</math> nie jest akceptowane.}}
<center>
<div class="thumb"><div style="width:350px;">
<flash>file=ja-lekcja03-w-rys3.swf|width=350|height=350</flash>
<div.thumbcaption>Animacja 4</div>
</div></div>
</center>
Słowo <math>\displaystyle abaa</math>  jest akceptowane.
<center>
<div class="thumb"><div style="width:350px;">
<flash>file=ja-lekcja03-w-rys4.swf|width=350|height=350</flash>
<div.thumbcaption>Animacja 5</div>
</div></div>
</center>


Każdy automat  <math>\displaystyle \mathcal{A}  \displaystyle = (S,A,f,s_0,T)</math> wyznacza w wolnym monoidzie <math>\displaystyle A^*</math>
prawą kongruencję, nazywaną '''prawą kongruencją automatową''', określoną w następujący
sposób:<br>
<math>\displaystyle \forall u,v \in A^*</math>

<center><math>\displaystyle u\sim _{\mathcal{A}}v\Longleftrightarrow f(s_{0},u)=f(s_{0},v).</math></center>

Dla automatu skończonego (o skończonym zbiorze stanów), a takie rozważamy,
relacja  <math>\displaystyle \sim _{A}  </math>  ma
skończony indeks, czyli skończoną liczbę klas równoważności.

{{przyklad|1.5.||

Automat z przykładu 1.2 (patrz [[#przyklad_1_2|przykład 1.2.]]) ze stanem  <math>\displaystyle s_{0}  </math>  jako początkowym wyznacza
relację równoważności o trzech klasach:

<math>\displaystyle [1]=A^*\left\{ b \right\}\cup \left\{ 1\right\}</math>,<br\>
<math>\displaystyle [a]=A^*\left\{ ba\right\}  \cup \left\{ a\right\}</math>,<br\>
<math>\displaystyle [a^2]=A^*\left\{ a^2 \right\}.</math> 

}}

Na odwrót, każda prawa kongruencja <math>\displaystyle \rho \subset (A^*)^2</math> wyznacza 
automat, zwany '''ilorazowym''', w 
następujący sposób:

<center><math>\displaystyle \mathcal{A}_{\rho }=(A^{*}/_{\rho },f^{*}),\; \; gdzie\; \; f^{*}([w]_{\rho },u)=[wu]_{\rho }.</math></center>

<math>\displaystyle \mathcal{A}  \displaystyle _\rho</math> jest automatem ze stanem początkowym <math>\displaystyle [1]_\rho</math>.  <math>\displaystyle \mathcal{A}_{\rho }  </math>  jest automatem skończonym
wtedy i&nbsp;tylko wtedy, gdy relacja <math>\displaystyle \rho</math> ma skończony indeks.<br>
Z definicji prawej kongruencji wynika, że funkcja przejść <math>\displaystyle f^*</math> jest określona poprawnie.

{{definicja|1.4.||

Niech  <math>\displaystyle \mathcal{A}  \displaystyle =(S,f)</math> i  <math>\displaystyle \, \mathcal{B}  \displaystyle =(T,g)</math> będą dowolnymi automatami.
Odwzorowanie <math>\displaystyle  \varphi:S\longrightarrow T </math>
nazywamy '''homomorfizmem automatów'''
wtedy i&nbsp;tylko
wtedy, jeśli <center><math>\displaystyle \forall s \in S,\;\; \forall w \in A^*\;\;\;\varphi(f(s,w)) \; = \; g(\varphi(s),w).</math></center>
Homomorfizm
automatów oznaczamy  <math>\displaystyle \varphi :\mathcal{A}\longrightarrow \mathcal{B}  </math> .

}}

{{twierdzenie|1.1.||

Prawdziwe są następujące fakty:

(1)  Dla dowolnej prawej kongruencji <math>\displaystyle \; \rho \; \subset \; (A^*)^2 </math>

<center><math>\displaystyle \sim _{\mathcal{A}_{\rho }}=\rho ,</math></center>
(2)  Dowolny automat  <math>\displaystyle \mathcal{A}  \displaystyle = (S,A,f,s_0,T)</math> jest izomorficzny z automatem  <math>\displaystyle \mathcal{A}_{\sim _{\mathcal{A}}}  </math> ,

(3)  Dla dowolnych automatów  <math>\displaystyle \mathcal{A}_1 \displaystyle = (S_1,A,f_1,s^1_0,T_1)</math>
i  <math>\displaystyle \mathcal{A}_2  \displaystyle = (S_2,A,f_2,s^2_0,T_2)</math>  prawdziwa jest równoważność

<math>\displaystyle \sim _{\mathcal{A}_1}\ : \subseteq \ : \sim _{\mathcal{A}_2}\ : \ : \Longleftrightarrow \ :   </math> 
istnieje epimorfizm  <math>\displaystyle \varphi :\mathcal{A}_1\longrightarrow \mathcal{A}_2  </math>  taki,
że <math>\displaystyle \varphi(s^1_0) = s^2_0</math>.

}}

{{dowod|||

(1) Identyczność relacji wynika wprost z&nbsp;definicji automatu ilorazowego  <math>\displaystyle \mathcal{A}  \displaystyle _\rho</math> oraz prawej kongruencji  <math>\displaystyle \sim _{A_{\rho }}  </math> .

(2) Rozważmy automat  <math>\displaystyle \mathcal{A}  \displaystyle = (S,A,f,s_0,T)</math> i  odwzorowanie

<center><math>\displaystyle \psi :\mathcal{A}\longrightarrow \mathcal{A}_{\sim _{\mathcal{A}}}, </math></center>

gdzie
<math>\displaystyle \forall s\in S  </math>   

<center><math>\displaystyle \psi (s)=[w]_{\sim _{\mathcal{A}}} \;\;\text{dla}\;\;  w\in A^{*} \;\;\text{i} \;\; f(s_{0},w)=s. </math></center>

Istnienie słowa <math>\displaystyle w</math> wynika z faktu, że <math>\displaystyle s_0</math> jest stanem początkowym, natomiast z definicji relacji <math>\displaystyle \sim _{\mathcal{A}}</math> wynika, że odwzorowanie <math>\displaystyle \psi</math> jest poprawnie określone.<br>
Odwzorowanie <math>\displaystyle \psi</math> ma być homomorfizmem, czyli dla każdego stanu  <math>\displaystyle s\in S  </math>  i dowolnego
słowa  <math>\displaystyle w\in A^{*}  </math>  spełniać warunek

<center><math>\displaystyle \psi (f(s,w))=f^{*}(\psi (s),w). </math></center>

Warunek ten wynika z następujących równości

<center><math>\displaystyle \begin{array} {c}
f^{*}(\psi (s),w)=f^{*}([u]_{\sim_{\mathcal{A}}},w)=[uw]_{\sim _{\mathcal{A}}}=\\
=\left\{ v\in A^{*}:f(s_{0},uw)=f(s_{0},v)\right\} = \\
\left\{ v\in A^{*}:f(f(s_{0},u),w)=f(s_{0},v)\right\} = \\
=\left\{ v\in A^{*}:f(s,w)=f(s_{0},v)\right\} =\psi (f(s,w))
\end{array} </math></center>

gdzie <math>\displaystyle f(s_0,u)=s</math>.

Z prostych  obserwacji wynika, że <math>\displaystyle \psi </math> jest suriekcją i iniekcją.

(3) Dowód implikacji "<math>\displaystyle \Rightarrow</math>" <br>
Załóżmy, że  <math>\displaystyle \ : \sim _{\mathcal{A}_1}\ : \subseteq \ : \sim _{\mathcal{A}_2 }  </math> . Niech

<center><math>\displaystyle \varphi :\mathcal{A}_1\longrightarrow \mathcal{A}_2 </math></center>

będzie odwzorowaniem takim, że<br>
<math>\displaystyle \forall  s\in S_1  </math>  <center><math>\displaystyle  \varphi (s) = f_2(s^2_0,w),\;\;\text{gdzie}\;\;  w\in A^{*}\;\; i \;\; f_1(s^1_0,w) = s.</math></center>

Stąd, że  <math>\displaystyle s^1_0  </math>  jest stanem początkowym automatu  <math>\displaystyle \mathcal{A}_1,  </math> 
wynika, że istnieje słowo <math>\displaystyle \; w \in A^* \;</math> potrzebne do określenia epimorfizmu <math>\displaystyle  \varphi</math>.<br>
Z założenia  <math>\displaystyle \ : \sim _{\mathcal{A}_1}\ : \subseteq \ : \sim _{\mathcal{A}_2}  </math> 
wynika, że <math>\displaystyle \varphi \;</math> jest poprawnie zdefiniowaną funkcją. <br>
Uzasadnienie faktu, że <math>\displaystyle \varphi</math> jest
homomorfizmem, jest analogiczne jak w punkcie (2) dla <math>\displaystyle \psi</math>.<br>
<math>\displaystyle \varphi</math> jest suriekcją, gdyż <math>\displaystyle \; s^2_0 \; </math>
jest stanem początkowym automatu  <math>\displaystyle \mathcal{A}_2  </math> .<br>
<math>\displaystyle \; \varphi (s^1_0) = s^2_0, \;</math> ponieważ <math>\displaystyle \; f_1(s^1_0,1) = s^1_0</math>. <br>
Dowód implikacji "<math>\displaystyle \Leftarrow</math>" <br>
Niech  <math>\displaystyle \varphi :\mathcal{A}_1\longrightarrow \mathcal{A}_2  </math>  będzie epimorfizmem
takim, że <math>\displaystyle \; \varphi (s^1_0) = s^2_0 \;</math>.<br>
Wówczas prawdziwy jest następujący ciąg wnioskowań.

<center><math>\displaystyle \begin{array} {c}
u\sim _{\mathcal{A}_1}v \Leftrightarrow f_1(s^1_0,u)=f_1(s^1_0,v)
\Rightarrow\\
\Rightarrow \varphi (f_1(s^1_{0},u))=\varphi (f_1(s^1_{0},v))\Rightarrow f_2(s^2_{0},u)=f_2(s^2_{0}v)\Leftrightarrow
u\sim _{\mathcal{A}_2}v
\end{array} 
</math></center>

To oznacza, że  <math>\displaystyle \sim _{\mathcal{A}_1}\subseteq \sim _{\mathcal{A}_2}  </math> .

}}

Symbolem <math>\displaystyle S^S</math> oznaczamy rodzinę wszystkich funkcji określonych na zbiorze <math>\displaystyle S</math> i przyjmujących
wartości w <math>\displaystyle S</math>. Łatwo zauważyć, iż  rodzina ta wraz ze składaniem odwzorowań jest
monoidem  <math>\displaystyle (S^S,\circ)</math> .

{{definicja|1.5.||

Niech  <math>\displaystyle \mathcal{A}  \displaystyle = (S,f)</math> będzie dowolnym automatem.
'''Reprezentacją automatu'''  <math>\displaystyle \mathcal{A}  </math>  nazywamy funkcję  <math>\displaystyle \tau 
_{\mathcal{A}}:A^{*}\longrightarrow S^{S}  </math> , określoną dla 
dowolnych <math>\displaystyle  w \in A^*</math> i <math>\displaystyle \; s \in S \;</math> równością

<center><math>\displaystyle \tau _{\mathcal{A}}(w)(s)=f(s,w). </math></center>

}}

Reprezentacja automatu jest
homomorfizmem monoidu <math>\displaystyle A^*</math> w monoid <math>\displaystyle S^S</math>, bowiem dla dowolnych <math>\displaystyle  v,w \in A^* </math>
spełnione są warunki

<center><math>\displaystyle \begin{array} {c}
\tau _{\mathcal{A}}(vw)=\tau _{\mathcal{A}}(w)\circ \tau _{\mathcal{A}}(v),\\
\tau _{\mathcal{A}}(1)=id_{S}.
\end{array} </math></center>

{{definicja|1.6.||

Niech  <math>\displaystyle \mathcal{A}  \displaystyle = (S,f)</math> będzie dowolnym automatem. '''Monoidem przejść'''
automatu  <math>\displaystyle \mathcal{A}  </math>  nazywamy monoid

<center><math>\displaystyle \mathcal{M}(\mathcal{A})=\tau _{\mathcal{A}}(A^{*})\subset S^{S}.</math></center>

}}

Następujące wnioski są konsekwencjami rozważań przeprowadzonych 
powyżej.

{{wniosek|1.1.||

(1) Monoid przejść automatu  <math>\displaystyle \mathcal{A}  </math>  jest podmonoidem monoidu <math>\displaystyle S^S</math> i  zbiór
<math>\displaystyle \left\{ \tau _{\mathcal{A}}(a):a\in A\right\}   </math>  jest zbiorem 
generatorów tego monoidu. <center><math>\displaystyle \mathcal{M}(\mathcal{A})=\left\{ \tau 
_{\mathcal{A}}(a):a\in A\right\} ^{*}.</math></center>
Wynika to z faktu, że  <math>\displaystyle \tau _{\mathcal{A}}  </math>  jest epimorfizmem i z twierdzenia 2.1 z wykładu 1. (patrz [[Języki, automaty i obliczenia/Wykład 1: Słowa, katenacja - elementy teorii półgrup, półgrupy i monoidy wolne#uwaga_Dla_zainteresowanych_twierdzenie_2.1|twierdzenie 2.1. wykład 1]])

(2) Monoid przejść automatu skończonego jest skończony.

(3) Monoid przejść automatu  <math>\displaystyle \mathcal{A}  </math>  jest izomorficzny z monoidem ilorazowym  <math>\displaystyle A^{*}/_{Ker_{\tau _{\mathcal{A}}}}  </math> .
Jest to wniosek z twierdzenia o rozkładzie epimorfizmu, które w tym przypadku ilustruje poniższy diagram.}}

<center>
<div class="thumb"><div style="width:350px;">
<flash>file=ja-lekcja03-w-rys5.swf|width=350|height=200</flash>
<div.thumbcaption>Rysunek 6</div>
</div></div>
</center>

{{przyklad|1.6.||

Określimy monoid przejść dla automatu z przykładu 1.2 (patrz [[#przyklad_1_2|przykład 1.2.]]). 
Wypisujemy kolejne funkcje  <math>\displaystyle \tau _{\mathcal{A}}(w)  </math>  dla  <math>\displaystyle w\in 
\{a,b\}^{*}  </math> . Zauważmy, że ze względu na występujące w tabelce 
powtórzenia, będące wynikiem równości, np.  <math>\displaystyle \tau 
_{\mathcal{A}}(b^2)=\tau _{\mathcal{A}}(b),  </math>  nie ma potrzeby 
określać funkcji  <math>\displaystyle \tau _{\mathcal{A}}(b^{n})  </math>  dla  <math>\displaystyle n\geq 3  </math> . 
Podobna obserwacja ma miejsce w innych przypadkach, co sprawia, że 
tabelka zawiera skończoną liczbę różnych funkcji.
}}


<center><math>\displaystyle \begin{array} {c|c|c|c|c|}  & s_0 & s_1 & s_2\\
\hline \tau _{\mathcal{A}}(1) & s_0 & s_1 & s_2\\
\hline \tau _{\mathcal{A}}(a) & s_1 & s_2 & s_2\\
\hline \tau _{\mathcal{A}}(b) & s_0 & s_0 & s_0\\
\hline \tau _{\mathcal{A}}(a^{2}) & s_2 & s_2 & s_2\\
\hline \tau _{\mathcal{A}}(ab) & s_0 & s_0 & s_0\\
\hline \tau _{\mathcal{A}}(ba) & s_1 & s_1 & s_1\\
\hline \tau _{\mathcal{A}}(b^{2}) & s_0 & s_0 & s_0\\
\hline \tau _{\mathcal{A}}(aba) & s_1 & s_1 & s_2\\
\hline ... & ... & ... & ...\\
\hline \end{array}  </math></center>


<center><math>\displaystyle M(\mathcal{A})=\left\{ \tau _{\mathcal{A}}(1),\tau _{\mathcal{A}}(a),\tau _{\mathcal{A}}(b),
\tau _{\mathcal{A}}(a^2),\tau _{\mathcal{A}}(b), \tau _{\mathcal{A}}(ba), \tau _{\mathcal{A}}(aba)\right\}
.</math></center>



Poniżej zamieszczamy algorytm obliczający monoid przejść dla automatu skończenie stanowego.

{{algorytm|WyznaczMonoidPrzejść - wyznacza monoid przejść dla
automatu||

   1  Wejście: <math>\displaystyle \mathcal{A}=(S, A, f, s_0, T)</math> - automat
   2  Wyjście: <math>\displaystyle M</math> - monoid przejść dla <math>\displaystyle \mathcal{A}</math>
   3  <math>\displaystyle L \leftarrow \emptyset</math>;  <math>\displaystyle \triangleright L</math> jest listą
   4  <math>\displaystyle M \leftarrow \emptyset</math>;
   5  '''for''' '''each''' <math>\displaystyle a \in A \cup \{1\}</math> '''do'''
   6    '''insert'''<math>\displaystyle (L, \{\tau_{\mathcal{A}}(a)\})</math>;  <math>\displaystyle \triangleright </math> gdzie <math>\displaystyle \tau_{\mathcal{A}}(a)(s)=f(s, a)</math> dla każdego <math>\displaystyle s \in S</math>
   7  '''end''' '''for'''
   8  '''while''' <math>\displaystyle L \not = \emptyset</math>; '''do''' 
   9   <math>\displaystyle \tau_{\mathcal{A}}(w) \leftarrow </math> '''first''' <math>\displaystyle  (L)</math>;
  10   <math>\displaystyle M \leftarrow M \cup \tau_{\mathcal{A}}(w)</math>;
  11   '''for''' '''each''' <math>\displaystyle a \in A</math> '''do'''
  12     '''for''' '''each''' <math>\displaystyle s \in S</math> '''do'''
  13        <math>\displaystyle \tau'_{\mathcal{A}}(wa)(s)\leftarrow f(\tau_{\mathcal{A}}(w)(s),a)</math>;
  14      '''end''' '''for'''
  15      '''if''' <math>\displaystyle \tau'_{\mathcal{A}}(wa) \not \in L \cup M</math> 
  16        '''insert'''<math>\displaystyle (L, \tau'_{\mathcal{A}}(wa))</math>;
  17      '''end''' '''if'''
  18    '''end''' '''for'''
  19  '''end''' '''while'''
  20  '''return''' <math>\displaystyle M</math>;
}}


Procedura '''insert'''<math>\displaystyle (L, x)</math> wkłada na koniec listy <math>\displaystyle L</math> element
<math>\displaystyle x</math>. Funkcja '''first'''<math>\displaystyle (L)</math> wyjmuje pierwszy element znajdujący
się na liście <math>\displaystyle L</math> i zwraca go. Algorytm działa w następujący sposób:
najpierw na listę <math>\displaystyle L</math> wkładane są elementy monoidu przejść
<math>\displaystyle \tau_{\mathcal{A}}(a)</math> dla każdej litery <math>\displaystyle a \in A \cup 1</math>. Te
funkcje można obliczyć bezpośrednio z tabelki reprezentującej
funkcję przejścia automatu <math>\displaystyle \mathcal{A}</math>. Następnie z listy po kolei
ściągane są poszczególne funkcje <math>\displaystyle \tau_{\mathcal{A}}(w)</math>. Każda z
nich dodawana jest do zbioru <math>\displaystyle M</math>, a następnie algorytm sprawdza dla
każdej litery <math>\displaystyle a \in A</math>, czy funkcja <math>\displaystyle \tau_{\mathcal{A}}(wa)</math>
istnieje już na liście <math>\displaystyle L</math> lub w zbiorze <math>\displaystyle M</math>. Jeśli nie, to funkcja
ta dodawana jest do listy. Procedura powyższa trwa do czasu, gdy
lista <math>\displaystyle L</math> zostanie pusta. Wtedy wszystkie elementy monoidu przejść
znajdą się w zbiorze <math>\displaystyle M</math>.

Przeanalizujmy działanie algorytmu dla automatu z przykładu 1.2
(patrz [[#przyklad_1_2|przykład 1.2.]]).

Na początku na listę <math>\displaystyle L</math> włożone zostaną funkcje
<math>\displaystyle \tau_{\mathcal{A}}(1)</math>, <math>\displaystyle \tau_{\mathcal{A}}(a)</math> oraz
<math>\displaystyle \tau_{\mathcal{A}}(b)</math>. Z listy zdejmujemy funkcję
<math>\displaystyle \tau_{\mathcal{A}}(1)</math> i dodajemy ją do zbioru <math>\displaystyle M</math>. Ponieważ
<math>\displaystyle \forall a \in A\displaystyle \tau_{\mathcal{A}}(1a)=\tau_{\mathcal{A}}(a)</math>, a
funkcje <math>\displaystyle \tau_{\mathcal{A}}(a)</math> oraz <math>\displaystyle \tau_{\mathcal{A}}(b)</math>
znajdują się już na liście, zatem nie dodajemy ich do <math>\displaystyle L</math>. Bierzemy
kolejny element listy, <math>\displaystyle \tau_{\mathcal{A}}(a)</math>, dodajemy go do <math>\displaystyle M</math> i
obliczamy funkcje <math>\displaystyle \tau_{\mathcal{A}}(aa)</math> oraz
<math>\displaystyle \tau_{\mathcal{A}}(ab)</math>. Ponieważ <math>\displaystyle \tau_{\mathcal{A}}(aa)</math> nie jest
tożsama z żadną funkcją ze zbioru <math>\displaystyle L \cup M</math>, dodajemy ją do listy.
Funkcja <math>\displaystyle \tau_{\mathcal{A}}(ab)</math> również nie jest równa żadnej z
funkcji należących do zbioru <math>\displaystyle L \cup M</math>, zatem wstawiamy ją na
koniec listy. Na liście <math>\displaystyle L</math> mamy zatem teraz następujące elementy:
<math>\displaystyle \tau_{\mathcal{A}}(b)</math>, <math>\displaystyle \tau_{\mathcal{A}}(a^2)</math> oraz
<math>\displaystyle \tau_{\mathcal{A}}(ab)</math>. Zdejmujemy z listy funkcję
<math>\displaystyle \tau_{\mathcal{A}}(b)</math>, dodajemy ją do <math>\displaystyle M</math> i obliczamy
<math>\displaystyle \tau_{\mathcal{A}}(ba)</math> oraz <math>\displaystyle \tau_{\mathcal{A}}(bb)</math>. Pierwsza z
tych funkcji jest nowa, tzn. nie jest tożsama z żadną funkcją ze
zbioru <math>\displaystyle L \cup M</math> więc dodajemy ją na koniec listy. Druga z nich
równa jest funkcji <math>\displaystyle \tau_{\mathcal{A}}(b)</math>, więc nie dodajemy jej do
listy. W tym momencie zbiór <math>\displaystyle M</math> zawiera następujące elementy:
<math>\displaystyle \tau_{\mathcal{A}}(1)</math>, <math>\displaystyle \tau_{\mathcal{A}}(a)</math>,
<math>\displaystyle \tau_{\mathcal{A}}(b)</math>, natomiast lista zawiera elementy
<math>\displaystyle \tau_{\mathcal{A}}(a^2)</math>, <math>\displaystyle \tau_{\mathcal{A}}(ab)</math>,
<math>\displaystyle \tau_{\mathcal{A}}(ba)</math>. Zdejmujemy z <math>\displaystyle L</math> funkcję
<math>\displaystyle \tau_{\mathcal{A}}(a^2)</math>, dodajemy ja do <math>\displaystyle M</math> i ponieważ
<math>\displaystyle \tau_{\mathcal{A}}(a^2a)=\tau_{\mathcal{A}}(a^2)</math> i
<math>\displaystyle \tau_{\mathcal{A}}(a^2b)=\tau_{\mathcal{A}}(b)</math>, nic nie dodajemy 
do <math>\displaystyle L</math>. Zdejmujemy teraz z listy funkcję <math>\displaystyle \tau_{\mathcal{A}}(ab)</math>, 
dodajemy ją do <math>\displaystyle M</math> i ponieważ <math>\displaystyle \tau_{\mathcal{A}}(aba)</math> nie należy 
do <math>\displaystyle L \cup M</math> dodajemy ją do listy. 
<math>\displaystyle \tau_{\mathcal{A}}(abb)=\tau_{\mathcal{A}}(b)</math>, więc tej funkcji 
nie dodajemy do <math>\displaystyle L</math>. Z <math>\displaystyle L</math> ściągamy <math>\displaystyle \tau_{\mathcal{A}}(ba)</math>, 
dodajemy ją do <math>\displaystyle M</math> i widzimy, że 
<math>\displaystyle \tau_{\mathcal{A}}(baa)=\tau_{\mathcal{A}}(a^2)</math> oraz 
<math>\displaystyle \tau_{\mathcal{A}}(bab)=\tau_{\mathcal{A}}(b)</math>, więc nic nie 
dodajemy do <math>\displaystyle L</math>. Na liście pozostała funkcja 
<math>\displaystyle \tau_{\mathcal{A}}(aba)</math>. Ściągamy ją z listy i dodajemy do <math>\displaystyle M</math>. 
Widzimy, że <math>\displaystyle \tau_{\mathcal{A}}(abaa)=\tau_{\mathcal{A}}(a^2)</math> i 
<math>\displaystyle \tau_{\mathcal{A}}(abab)=\tau_{\mathcal{A}}(b)</math>, zatem nic nie 
dodajemy do listy <math>\displaystyle L</math>. Lista jest w tym momencie pusta i działanie 
algorytmu zakończyło się. Ostatecznie mamy
<center><math>\displaystyle M(\mathcal{A})=\{ \tau_{\mathcal{A}}(1),\tau_{\mathcal{A}}(a),
\tau_{\mathcal{A}}(b),\tau_{\mathcal{A}}(a^2),\tau_{\mathcal{A}}(ab),
\tau_{\mathcal{A}}(ba),\tau_{\mathcal{A}}(aba)\},</math></center>

co zgadza się z wynikiem otrzymanym w przykładzie.

Twierdzenie poniższe zbiera dotychczas uzyskane charakteryzacje języków rozpoznawanych.

<span id="twierdzenie_1_2">{{twierdzenie|1.2.||

Niech <math>\displaystyle \; L \subset A^* \;</math> będzie dowolnym językiem. Równoważne są następujące warunki:
:(1)  Język <math>\displaystyle \; L \;</math> jest rozpoznawalny,
:(2)  Język <math>\displaystyle \; L \;</math> jest sumą wybranych klas równoważności pewnej prawej kongruencji <math>\displaystyle \rho</math> na <math>\displaystyle \; A^* \;</math> o skończonym indeksie: <center><math>\displaystyle L = \bigcup_{w\in L}[w]_\rho.</math></center>
: (3)  Język <math>\displaystyle \; L \;</math> jest sumą wybranych klas równoważności pewnej kongruencji <math>\displaystyle \rho</math> na <math>\displaystyle \; A^* \;</math> o skończonym indeksie: <center><math>\displaystyle L = \bigcup_{w\in L}[w]_\rho.</math></center>
: (4)  Istnieje skończony monoid <math>\displaystyle \; M \;</math> i istnieje epimorfizm <math>\displaystyle \varphi : A^* \longrightarrow M</math> taki, że <center><math>\displaystyle L = \varphi^{-1}(\varphi (L)).</math></center>

}}</span>

{{dowod|||

Dowód równoważności czterech powyższych warunków przeprowadzimy zgodnie z następującym schematem:

<center><math>\displaystyle 4 \Longrightarrow 3 \Longrightarrow 2\Longrightarrow 1 \Longrightarrow 4</math></center>

<math>\displaystyle 4 \Longrightarrow 3</math> 

Dany jest homomorfizm <center><math>\displaystyle \varphi: A^* \longrightarrow M, </math></center>
gdzie <math>\displaystyle M</math> jest skończonym monoidem.<br>
Określamy relację <math>\displaystyle \; \rho \;</math> na <math>\displaystyle A^*</math>, przyjmując dla dowolnych <math>\displaystyle  u, v \in A^* </math>
<center><math>\displaystyle u \; \rho \; v \;\; \Longleftrightarrow \;\; \varphi (u) = \varphi (v).</math></center>

Tak określona relacja jest kongruencją.  Natomiast jej skończony indeks wynika z faktu, że monoid <math>\displaystyle \; M \;</math> jest skończony.
Pokażemy teraz, że:

<center><math>\displaystyle L = \bigcup_{w\in L}[w]_\rho .</math></center>
Inkluzja <math>\displaystyle \; \subseteq \;</math> jest oczywista.<br>
Inkluzja w przeciwną stronę (<math>\displaystyle L \supseteq \bigcup_{w\in L}[w]_\rho,</math>) oznacza, że każda klasa równoważności relacji
<math>\displaystyle \; \rho \;</math> albo cała zawiera się w języku <math>\displaystyle L</math>, albo cała zawiera się w uzupełnieniu języka <math>\displaystyle L</math>.<br>
Załóżmy, że <math>\displaystyle \; u \in [w]_\rho</math> dla pewnego <math>\displaystyle  w \in L. \;</math>
Oznacza to, że
<center><math>\displaystyle u \; \rho \; w \Leftrightarrow \varphi (u) = \varphi (w) \in \varphi (L)\Rightarrow
u \in \varphi^{-1}(\varphi (u)) \;\; \subset \varphi^{-1}(\varphi (L)) = L.</math></center>

Implikuje to ostatecznie, że <math>\displaystyle u \in L</math>.

<math>\displaystyle 3 \Longrightarrow 2</math>

Każda kongruencja jest prawą kongruencją.

<math>\displaystyle 2 \Longrightarrow 1</math>

Niech <math>\displaystyle \; \rho \;</math> będzie prawą kongruencją o skończonym indeksie na <math>\displaystyle \; A^* \;</math> taką, że
<center><math>\displaystyle L = \bigcup_{w\in L}[w]_\rho .</math></center>

Automat  <math>\displaystyle \mathcal{A}_{\rho }  \displaystyle = (A^*/\rho,f^*,[1]_\rho,T),</math> dla którego

<center><math>\displaystyle f^*([w]_\rho,u) =[wu]_\rho \;, \;\;\;\;\; T = \{ [w]_\rho \; : \; w \in L \}</math></center>
akceptuje język <math>\displaystyle L</math>.

<math>\displaystyle 1 \Longrightarrow 4</math>

Niech język <math>\displaystyle \; L=L(\mathcal{A}) \;</math>, gdzie   <math>\displaystyle \mathcal{A}  \displaystyle = (S,f,s_0,T)</math>.<br>
Określamy odwzorowanie 

<center><math>\displaystyle \varphi :A^{*}\longrightarrow A^{*}/_{Ker\tau _{\mathcal{A}}}, </math></center>

przyjmując dla każdego  <math>\displaystyle v\in A^{*}  </math>  

<center><math>\displaystyle \varphi (v)=[v]_{Ker\tau _{\mathcal{A}}}. </math></center>

Jest to odwzorowanie kanoniczne monoidu <math>\displaystyle \; A^* \;</math> na monoid ilorazowy, a więc jest to epimorfizm.<br>
<math>\displaystyle A^{*}/_{Ker\tau _{\mathcal{A}}}  </math>  jest monoidem skończonym, ponieważ <math>\displaystyle \; S \;</math> jest zbiorem skończonym.

Dla dowodu równości <math>\displaystyle L = \varphi^{-1}(\varphi (L))</math> wystarczy udowodnić
inkluzję <math>\displaystyle L \supset \varphi^{-1}(\varphi (L))</math>. (Inkluzja <math>\displaystyle \; L \subseteq \varphi^{-1}(\varphi (L))\;</math>
wynika z&nbsp;definicji przeciwobrazu.) <br>
Niech <math>\displaystyle \; u \in \varphi^{-1}(\varphi (L)) .\;</math> Oznacz to, że

<center><math>\displaystyle \begin{array} {c}
\varphi (u)\in \varphi (L) \Leftrightarrow \exists v\in L :\varphi (u)=\varphi (v) \Leftrightarrow
\exists v\in L : [u]_{_{Ker\tau _{\mathcal{A}}}}=[v]_{_{Ker\tau _{\mathcal{A}}}} \Leftrightarrow \\
\Leftrightarrow \exists v\in L :  \tau _{\mathcal{A}}(u)=\tau _{\mathcal{A}}(v) \Leftrightarrow,
\exists v\in L : \forall s \in S \;f(s,u)=f(s,v)

\end{array} </math></center>

W szczególności  <center><math>\displaystyle  f(s_0,u) = f(s_0,v) \in T, </math></center>
czyli  <math>\displaystyle u \in L.
}}</math>
}}