Test GR

{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 skończenie stanowy}

Wprowadzenie

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.

Słowa kluczowe

automat skończenie stanowy, język rozpoznawany, prawa kongruencja

automatowa, homomorfizm automatów, monoid przejść automatu.

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ą.

Ćwiczenie [Uzupelnij]

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 $WE$. Zamiar wyjścia symbolem $WY$. Symbol $WEWY$ będzie związany z równoczesnym zamiarem wejścia jakiejś osoby i wyjścia innej. Wreszcie symbol $BRAK$ oznaczał będzie brak osób, które chcą wejść lub wyjść. Zatem zbiór $\{WE,WY,WEWY,BRAK\}$, to alfabet nad którym określimy automat o $2$ stanach: Parser nie mógł rozpoznać (błąd składni): {\displaystyle OTWARTE, ZAMKNIĘTE} poniższym grafem.

RYSUNEK ja-lekcja3-w-rys6

ANIMACJA ja-lekcja-w-rys7 działania drzwi

Automaty reagują więc na określone sygnały zewnętrzne reprezentowane przez litery alfabetu $A$ 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 $A^{*}$ 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.

Podamy teraz definicję automatu. Niech $A$ oznacza dowolny alfabet. Od tego momentu wykładu zakładamy, że alfabet jest zbiorem skończonym.

Automatem nad alfabetem $A$ nazywamy system ${𝒜}=(S,f)$, w którym

$S$ - jest dowolnym skończonym zbiorem zwanym zbiorem stanów,

$f:S\times A\to S$ - jest funkcją przejść.

Automat będąc w stanie $s_i$ po przeczytaniu litery $a$ zmienia stan na $s_j$ zgodnie z funkcją przejścia $f(s_i,a)=s_j$.

Funkcję przejść rozszerzamy na cały wolny monoid

$A^{*}$

do postaci

$f:S\times A^{*}\to S$

przyjmując:

dla każdego $s\in Sf(s,1)=s$ oraz

dla każdego $s\in S,a\in A$ i dla dowolnego $w\in A^{*}$

$f(s,wa)=f(f(s,w),a).$

Działanie automatu pokazane jest na rysunku.

rys3.1

Zdefiniowany powyżej automat ${𝒜}$ nazywamy skończonym lub skończenie stanowym ze względu na założenie skończoności zbioru stanów $S$.

Ćwiczenie [Uzupelnij]

Niech $A=\{a,b\}$ będzie alfabetem, a ${𝒜}=(S,f)$ automatem takim, że

$S=\{s_0,s_1,s_2\}$, a funkcja przejść zadana jest przy pomocy tabelki

{

{

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 $A$ to automat $(S,f)$ o następującej własności: istnieje stan $t\in S$ oraz słowo $w\in A^{*}$ takie, że dla każdego stanu $s$ tego automatu $f(s,w)=t$. Istnieje więc pewne uniwersalne słowo $w$, pod wpływem którego wszystkie stany przechodzą w jeden, ustalony stan automatu $t\in S$. 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.

Ćwiczenie [Uzupelnij]

RYSUNEK pojedynczego detalu - ja-lekcja3-w-rys-s1

Załóżmy, że pewna fabryka produkuje detale w kształcie kwadratu z "wypustką" na jednym boku (patrz rys. Uzupelnic ja-lekcja3-w-rys-s1|). 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. Uzupelnic ja-lekcja3-w-rys-s2|): "wypustką" w górę, w dół, w lewo lub w prawo.

RYSUNEK ja-lekcja3-w-rys-s2

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. Uzupelnic ja-lekcja3-w-rys-s3| przedstawione zostały przejścia pomiędzy orientacjami detali w zależności od napotkania odpowiedniej przeszkody.

RYSUNEK ja-lekcja3-w-rys-s3

Można zauważyć, że automat z rysunku Uzupelnic ja-lekcja3-w-rys-s3| 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:

ANIMACJA ja-lekcja3-w-anim-s4

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

Język $L\subset A^{*}$ jest rozpoznawany (akceptowany) wtedy i tylko wtedy, gdy istnieje automat skończony ${𝒜}=(S,f),$ stan $s_0\in S$ oraz zbiór $T\subset S$ takie, że

$L=\{w\in A^{*}:f(s_0,w)\in T\}.$

Stan

$s_0$

nazywamy stanem początkowym,

a $T$ zbiorem stanów końcowych automatu ${𝒜}$.

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ę ${𝒜}=(S,A,f,s_0,T)$ lub czwórkę ${𝒜}=(S,f,s_0,T)$, jeśli wiadomo, nad jakim alfabetem rozważamy działanie automatu.

Fakt, że język $L$ jest rozpoznawany przez automat ${𝒜},$ zapisujemy jako

$L=L({𝒜}).$

Rodzinę wszystkich języków rozpoznawalnych nad alfabetem $A$ oznaczamy przez ${ℛ}{ℰ}{𝒞}({{𝒜}}^{*})$.

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.

Automaty ${{𝒜}}_1$ i ${{𝒜}}_2$ są równoważne, jeśli rozpoznają ten sam język, czyli

$L({{𝒜}}_1)=L({{𝒜}}_2).$

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

${ℬ}=(f(s_0,A^{*}),A,f{|}_{f(s_0,A^{*})\times A^{*}},s_0,T\cap f(s_0,A^{*})),$

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 ze z $s_0$. Poniżej przedstawiamy algorytm usuwający z automatu stany nieosiągalne ze stanu początkowego.

{{UsuńStanyNieosiągalne} - usuwa z automatu ${𝒜}$ stany nieosiągalne} [1] Wejście: ${𝒜}=(S,A,f,s_0,T)$ - automat

Wyjście: ${{𝒜}}^{\prime }=(S^{\prime },A,f^{\prime },s_0,T^{\prime })$ - automat równoważny automatowi ${𝒜}$ bez stanów nieosiągalnych.

procedure {Oznacz}$(x\in S)$

{Parser nie mógł rozpoznać (błąd składni): {\displaystyle p \in S:\ \exists a \in A\ f(x,a)=p \wedge \mbox{\textbf{zaznaczone}}[p]==0} }

zaznaczone$[p]\leftarrow 1$;

{Oznacz}$(p)$;

end procedure

{$p\in S$}

zaznaczone$[p]\leftarrow 0$;

zaznaczone$[s_0]\leftarrow 1$;

{Oznacz}$(s_0)$;

Parser nie mógł rozpoznać (błąd składni): {\displaystyle S' = \{s \in S:\ \mbox{\textbf{zaznaczone}}[s]==1\}} ;

$T^{\prime }=T\cap S^{\prime }$;

jeśli istnieje przynajmniej jeden stan, dla którego funkcja przejścia $f$ nie jest określona dla jakiejś litery $a\in A$, dodaj stan $s_f$ do $S^{\prime }$ i dla każdego stanu $s$ i litery $a$ jeśli $f(s,a)$ jest nieokreślone, to zdefiniuj $f(s,a)=s_f$;

$f^{\prime }\leftarrow f$;

${{𝒜}}^{\prime }=(S^{\prime },A,f^{\prime },s_0,T^{\prime })$;

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

Ćwiczenie [Uzupelnij]

Jeśli w przykładzie Uzupelnic ex.3.1.1| przyjmiemy stan $s_0$ jako stan początkowy, $T=\left\{s_2\right\}$ jako zbiór stanów końcowych, to automat ${𝒜}=(S,A,f,s_0,T)$ rozpoznaje język

$L({𝒜})=A^{*}\left\{a^2\right\}$

złożony ze słów, kończących się na $a^2$.
Słowo $aba$ nie jest akceptowane. rys3.3
Słowo $abaa$ jest akceptowane. rys3.4

Każdy automat ${𝒜}=(S,A,f,s_0,T)$ wyznacza w wolnym monoidzie $A^{*}$ prawą kongruencję, nazywaną prawą kongruencją automatową, określoną w następujący sposób:
$\mathrm{\forall }u,v\in A^{*}$

$u{\sim }_{{𝒜}}v⟺f(s_0,u)=f(s_0,v).$

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

Ćwiczenie [Uzupelnij]

Automat z przykładu Uzupelnic ex.3.1.1| ze stanem $s_0$ jako początkowym wyznacza relację równoważności o trzech klasach:

$[1]=A^{*}\left\{b\right\}\cup \left\{1\right\}[a]=A^{*}\left\{ba\right\}\cup \left\{a\right\}[a^2]=A^{*}\left\{a^2\right\}$

Na odwrót, każda prawa kongruencja $\rho \subset (A^{*}{)}^2$ wyznacza automat, zwany ilorazowym, w następujący sposób:

${{𝒜}}_{\rho }=(A^{*}{/}_{\rho },f^{*}),gdzie{f}^{*}([w{]}_{\rho },u)=[wu{]}_{\rho }.$ ${𝒜}$

_Parser nie mógł rozpoznać (błąd składni): {\displaystyle jest automatem ze stanem początkowym } [1]_

$.$

{A}_{ } Parser nie mógł rozpoznać (błąd składni): {\displaystyle jest automatem skończonym wtedy i~tylko wtedy, gdy relacja ma skończony indeks.\\ Z definicji prawej kongruencji wynika, że funkcja przejść } f^*Parser nie mógł rozpoznać (błąd składni): {\displaystyle jest określona poprawnie. \begindefin Niech {A} <nowiki>=</nowiki>(S,f)<math> i } {B} =(T,g)Parser nie mógł rozpoznać (błąd składni): {\displaystyle będą dowolnymi automatami. Odwzorowanie } :S T Parser nie mógł rozpoznać (błąd składni): {\displaystyle nazywamy \textbf{homomorfizmem automatów}\index{homomorfizm automatów} wtedy i~tylko wte\-dy, jeśli } s S, w A^*(f(s,w)) = g((s),w).

Parser nie mógł rozpoznać (błąd składni): {\displaystyle Homomorfizm automatów oznaczamy }  :{A} {B} Parser nie mógł rozpoznać (nieznana funkcja „\enddefin”): {\displaystyle . \enddefin \begintheor Prawdziwe są następujące fakty: # Dla dowolnej prawej kongruencji } (A^*)^2

_{{A}_{ }}= ,

Parser nie mógł rozpoznać (błąd składni): {\displaystyle # Dowolny automat } {A} = (S,A,f,s_0,T)$jestizomorficznyzautomatem${A}_{ _Szablon:A} Parser nie mógł rozpoznać (błąd składni): {\displaystyle , # Dla dowolnych automatów } {A}_1= (S_1,A,f_1,s^1_0,T_1)$i${A}_2 = (S_2,A,f_2,s^2_0,T_2)Parser nie mógł rozpoznać (błąd składni): {\displaystyle prawdziwa jest równoważność {\par\centering } _{{A}_1} _{{A}_2} $istniejeepimorfizm$ :{A}_1 {A}_2 Parser nie mógł rozpoznać (błąd składni): {\displaystyle taki, że } (s^1_0) = s^2_0Parser nie mógł rozpoznać (nieznana funkcja „\par”): {\displaystyle . \par} \endtheor \beginprf \hfill # Identyczność relacji wynika wprost z~defi\-ni\-cji automatu ilorazowego } {A} ${}_{\rho }$ oraz prawej kongruencji ${\sim }_{A_{\rho }}$.

1. Rozważmy automat ${𝒜}=(S,A,f,s_0,T)$ i odwzorowanie

$\psi :{𝒜}⟶{{𝒜}}_{{\sim }_{{𝒜}}},$

gdzie $\mathrm{\forall }s\in S$

$\psi (s)=[w{]}_{{\sim }_{{𝒜}}}\text{dla}w\in A^{*}\text{i}f(s_0,w)=s.$

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

$\psi (f(s,w))=f^{*}(\psi (s),w).$

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

$\begin{array}{c}{f}^{*}(\psi (s),w)=f^{*}([u{]}_{{\sim }_{{𝒜}}},w)=[uw{]}_{{\sim }_{{𝒜}}}=\\ =\{v\in A^{*}:f(s_0,uw)=f(s_0,v)\}=\\ \{v\in A^{*}:f(f(s_0,u),w)=f(s_0,v)\}=\\ =\{v\in A^{*}:f(s,w)=f(s_0,v)\}=\psi (f(s,w))\end{array}$

gdzie $f(s_0,u)=s$.

Z prostych obserwacji wynika, że $\psi$ jest suriekcją i iniekcją.

1. Dowód implikacji "$\Rightarrow$"
   

Załóżmy, że Parser nie mógł rozpoznać (błąd składni): {\displaystyle \: \sim _{\mathcal{A}_1}\: \subseteq \: \sim _{\mathcal{A}_2 } } . Niech

$\phi :{{𝒜}}_1⟶{{𝒜}}_2$

będzie odwzorowaniem takim, że

$\mathrm{\forall }s\in S_1$ $\phi (s)=f_2(s_0^2,w),\text{gdzie}w\in A^{*}i{f}_1(s_0^1,w)=s.$

Stąd, że $s_0^1$ jest stanem początkowym automatu ${{𝒜}}_1,$ wynika, że istnieje słowo $w\in A^{*}$ potrzebne do określenia epimorfizmu $\phi$.
Z założenia Parser nie mógł rozpoznać (błąd składni): {\displaystyle \: \sim _{\mathcal{A}_1}\: \subseteq \: \sim _{\mathcal{A}_2} } wynika, że $\phi$ jest poprawnie zdefiniowaną funkcją.
Uzasadnienie faktu, że $\phi$ jest homomorfizmem, jest analogiczne jak w punkcie Uzupelnic tb| dla $\psi$.
$\phi$ jest suriekcją, gdyż $s_0^2$ jest stanem początkowym automatu ${{𝒜}}_2$.
$\phi (s_0^1)=s_0^2,$ ponieważ $f_1(s_0^1,1)=s_0^1$.
Dowód implikacji "$\Leftarrow$"
Niech $\phi :{{𝒜}}_1⟶{{𝒜}}_2$ będzie epimorfizmem takim, że $\phi (s_0^1)=s_0^2$.
Wówczas prawdziwy jest następujący ciąg wnioskowań.

$\begin{array}{c}u{\sim }_{{{𝒜}}_1}v\iff f_1(s_0^1,u)=f_1(s_0^1,v)\Rightarrow \\ \Rightarrow \phi (f_1(s_0^1,u))=\phi (f_1(s_0^1,v))\Rightarrow f_2(s_0^2,u)=f_2(s_0^{2}v)\iff u{\sim }_{{{𝒜}}_2}v\end{array}$

To oznacza, że ${\sim }_{{{𝒜}}_1}\subseteq {\sim }_{{{𝒜}}_2}$.

$\mathrm{♢}$

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

Niech ${𝒜}=(S,f)$ będzie dowolnym automatem. Reprezentacją automatu ${𝒜}$ nazywamy funkcję ${\tau }_{{𝒜}}:A^{*}⟶S^S$ określoną dla dowolnych $w\in A^{*}$ i $s\in S$ równością

${\tau }_{{𝒜}}(w)(s)=f(s,w).$

Reprezentacja automatu jest homomorfizmem monoidu $A^{*}$ w monoid $S^S$, bowiem dla dowolnych $v,w\in A^{*}$ spełnione są warunki

$\begin{array}{c}{\tau }_{{𝒜}}(vw)={\tau }_{{𝒜}}(w)\circ {\tau }_{{𝒜}}(v),\\ {\tau }_{{𝒜}}(1)=i{d}_S.\end{array}$ Niech ${𝒜}$= (S,f)Parser nie mógł rozpoznać (błąd składni): {\displaystyle będzie dowolnym automatem. \textbf{Monoidem przejść}\index{monoid przejść} automatu } {A} $nazywamymonoid$

{M}({A})= _Szablon:A(A^{*}) S^{S}.

Parser nie mógł rozpoznać (nieznana funkcja „\enddefin”): {\displaystyle \enddefin Następujace wnioski są konsekwencjami rozważań przeprowadzonych powyżej. \begincorol \vspace{-5truemm}\\ # Monoid przejść automatu } {A} $jestpodmonoidemmonoidu$ S^S Parser nie mógł rozpoznać (błąd składni): {\displaystyle i zbiór } _Szablon:A(a):a A Parser nie mógł rozpoznać (błąd składni): {\displaystyle jest zbiorem generatorów tego monoidu. }

{M}({A})= _Szablon:A(a):a A ^{*}

Parser nie mógł rozpoznać (błąd składni): {\displaystyle Wynika to z faktu, że } _Szablon:A Parser nie mógł rozpoznać (błąd składni): {\displaystyle jest epimorfizmem i z twierdzenia~[[##tw:z|Uzupelnic tw:z|]]. # Monoid przejść automatu skończonego jest skończony. # Monoid przejść automatu } {A} $jestizomorficznyzmonoidemilorazowym$A^{*}/_{Ker_{ _Szablon:A}} Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Jest to wniosek z twierdzenia o rozkładzie epimorfizmu, które w tym przypadku ilustruje poniższy diagram. rys3.5 \endcorol {{cwiczenie|[Uzupelnij]|| Określimy monoid przejść dla automatu z przykładu [[##ex.3.1.1|Uzupelnic ex.3.1.1|]]. Wypisujemy kolejne funkcje } _Szablon:A(w) $dla$w a,b^{*} Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Zauważmy, że ze względu na występujące w tabelce powtórzenia będace wynikiem równości, np. } _Szablon:A(b^2)= _Szablon:A(b), Parser nie mógł rozpoznać (błąd składni): {\displaystyle nie ma potrzeby określać funkcji } _Szablon:A(b^{n}) $dla$n 3 Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Podobna obserwacja ma miejsce w innych przypadkach, co sprawia, że tabelka zawiera skończoną liczbę różnych funkcji. \vspace{0.3cm} {\centering \begintabular {|c||c|c|c|} \hline & } s_{0} Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } s_{1} Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } s_{2} Parser nie mógł rozpoznać (błąd składni): {\displaystyle \\ \hline \hline } _Szablon:A(1) Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } s_{0} Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } s_{1} Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } s_{2} Parser nie mógł rozpoznać (błąd składni): {\displaystyle \\ \hline } _Szablon:A(a) Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } s_{1} Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } s_{2} Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } s_{2} Parser nie mógł rozpoznać (błąd składni): {\displaystyle \\ \hline } _Szablon:A(b) Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } s_{0} Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } s_{0} Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } s_{0} Parser nie mógł rozpoznać (błąd składni): {\displaystyle \\ \hline } _Szablon:A(a^{2}) Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } s_{2} Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } s_{2} Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } s_{2} Parser nie mógł rozpoznać (błąd składni): {\displaystyle \\ \hline } _Szablon:A(ab) Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } s_{0} Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } s_{0} Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } s_{2} Parser nie mógł rozpoznać (błąd składni): {\displaystyle \\ \hline } _Szablon:A(ba) Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } s_{1} Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } s_{1} Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } s_{1} Parser nie mógł rozpoznać (błąd składni): {\displaystyle \\ \hline } _Szablon:A(b^{2}) Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } s_{0} Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } s_{0} Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } s_{0} Parser nie mógł rozpoznać (błąd składni): {\displaystyle \\ \hline } _Szablon:A(aba) Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } s_{1} Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } s_{1} Parser nie mógł rozpoznać (błąd składni): {\displaystyle & } s_{2} Parser nie mógł rozpoznać (błąd składni): {\displaystyle \\ \hline ...& ...& ...& ...\\ \hline \endtabular \par} \vspace{0.3cm} }

M({A})= _Szablon:A(1), _Szablon:A(a), _Szablon:A(b),

_Szablon:A(a^2), _Szablon:A(b), _Szablon:A(ba), _Szablon:A(aba)

.

Parser nie mógł rozpoznać (błąd składni): {\displaystyle }} Poniżej zamieszczamy algorytm obliczający monoid przejść dla automatu skończenie stanowego. \beginalgorithm \caption{\textsc{WyznaczMonoidPrzejść} - wyznacza monoid przejść dla automatu} \beginalgorithmic [1] \STATE Wejście: } {A}=(S, A, f, s_0, T)Parser nie mógł rozpoznać (nieznana funkcja „\STATE”): {\displaystyle - automat \STATE Wyjście: } MParser nie mógł rozpoznać (błąd składni): {\displaystyle - monoid przejść dla } {A}Parser nie mógł rozpoznać (nieznana funkcja „\STATE”): {\displaystyle \STATE } L $;$ LParser nie mógł rozpoznać (błąd składni): {\displaystyle jest listą \STATE } M Parser nie mógł rozpoznać (nieznana funkcja „\FOR”): {\displaystyle ; \FOR{} a A 1Parser nie mógł rozpoznać (nieznana funkcja „\STATE”): {\displaystyle } \STATE \textbf{insert}} (L, _Szablon:A(a))$;gdzie$_Szablon:A(a)(s)=f(s, a)Parser nie mógł rozpoznać (błąd składni): {\displaystyle dla każdego } s SParser nie mógł rozpoznać (nieznana funkcja „\ENDFOR”): {\displaystyle \ENDFOR \WHILE{} L = Parser nie mógł rozpoznać (nieznana funkcja „\STATE”): {\displaystyle ;} \STATE } _Szablon:A(w) first(L)Parser nie mógł rozpoznać (nieznana funkcja „\STATE”): {\displaystyle ; \STATE } M M _Szablon:A(w)Parser nie mógł rozpoznać (nieznana funkcja „\FOR”): {\displaystyle ; \FOR{} a AParser nie mógł rozpoznać (nieznana funkcja „\STATE”): {\displaystyle } \STATE } s S'_Szablon:A(wa)(s)=f(_Szablon:A(w)(s),a)Parser nie mógł rozpoznać (nieznana funkcja „\IF”): {\displaystyle ; \IF{} '_Szablon:A(wa) L MParser nie mógł rozpoznać (nieznana funkcja „\STATE”): {\displaystyle } \STATE \textbf{insert}} (L, '_Szablon:A(wa))Parser nie mógł rozpoznać (nieznana funkcja „\ENDIF”): {\displaystyle ; \ENDIF \ENDFOR \ENDWHILE \RETURN } MParser nie mógł rozpoznać (nieznana funkcja „\endalgorithmic”): {\displaystyle ; \endalgorithmic \endalgorithm \eject Procedura \textbf{insert}} (L, x)Parser nie mógł rozpoznać (błąd składni): {\displaystyle wkłada na koniec listy } L$element$x$.Funkcja\text{<mrow data-mjx-texclass="ORD">first</mrow>}$(L)Parser nie mógł rozpoznać (błąd składni): {\displaystyle wyjmuje pierwszy element znajdujący się na liście } LParser nie mógł rozpoznać (błąd składni): {\displaystyle i zwraca go. Algorytm działa w następujący sposób: najpierw na listę } LParser nie mógł rozpoznać (błąd składni): {\displaystyle wkładane są elementy monoidu przejść } _Szablon:A(a)Parser nie mógł rozpoznać (błąd składni): {\displaystyle dla każdej litery } a A 1Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Te funkcje można obliczyć bezpośrednio z tabelki reprezentującej funkcję przejścia automatu } {A}Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Następnie z listy po kolei ściągane są poszczególne funkcje } _Szablon:A(w)Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Każda z nich dodawana jest do zbioru } MParser nie mógł rozpoznać (błąd składni): {\displaystyle , a następnie algorytm sprawdza dla każdej litery } a A$,czyfunkcja$_Szablon:A(wa)Parser nie mógł rozpoznać (błąd składni): {\displaystyle istnieje już na liście } L$lubwzbiorze$MParser nie mógł rozpoznać (błąd składni): {\displaystyle . Jeśli nie, to funkcja ta dodawana jest do listy. Procedura powyższa trwa do czasu, gdy lista } LParser nie mógł rozpoznać (błąd składni): {\displaystyle zostanie pusta. Wtedy wszystkie elementy monoidu przejść znajdą się w zbiorze } MParser nie mógł rozpoznać (błąd składni): {\displaystyle . Przeanalizujmy działanie algorytmu dla automatu z przykładu [[##ex.3.1.1|Uzupelnic ex.3.1.1|]]. Na początku na listę } LParser nie mógł rozpoznać (błąd składni): {\displaystyle włożone zostaną funkcje } _Szablon:A(1)$,$_Szablon:A(a)$oraz$_Szablon:A(b)Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Z listy zdejmujemy funkcję } _Szablon:A(1)Parser nie mógł rozpoznać (błąd składni): {\displaystyle i dodajemy ją do zbioru } MParser nie mógł rozpoznać (błąd składni): {\displaystyle . Ponieważ } a A_Szablon:A(1a)=_Szablon:A(a)$,afunkcje$_Szablon:A(a)$oraz$_Szablon:A(b)Parser nie mógł rozpoznać (błąd składni): {\displaystyle znajdują się już na liście, zatem nie dodajemy ich do } L$.Bierzemykolejnyelementlisty,$_Szablon:A(a)$,dodajemygodo$M$iobliczamyfunkcje$_Szablon:A(aa)$oraz$_Szablon:A(ab)Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Ponieważ } _Szablon:A(aa)Parser nie mógł rozpoznać (błąd składni): {\displaystyle nie jest tożsama z żadną funkcją ze zbioru } L MParser nie mógł rozpoznać (błąd składni): {\displaystyle , dodajemy ją do listy. Funkcja } _Szablon:A(ab)Parser nie mógł rozpoznać (błąd składni): {\displaystyle również nie jest równa żadnej z funkcji należących do zbioru } L MParser nie mógł rozpoznać (błąd składni): {\displaystyle , zatem wstawiamy ją na koniec listy. Na liście } LParser nie mógł rozpoznać (błąd składni): {\displaystyle mamy zatem teraz następujące elementy: } _Szablon:A(b)$,$_Szablon:A(a^2)$oraz$_Szablon:A(ab)Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Zdejmujemy z listy funkcję } _Szablon:A(b)Parser nie mógł rozpoznać (błąd składni): {\displaystyle , dodajemy ją do } M$iobliczamy$_Szablon:A(ba)$oraz$_Szablon:A(bb)Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Pierwsza z tych funkcji jest nowa, tzn. nie jest tożsama z żadną funkcją ze zbioru } L MParser nie mógł rozpoznać (błąd składni): {\displaystyle więc dodajemy ją na koniec listy. Druga z nich równa jest funkcji } _Szablon:A(b)Parser nie mógł rozpoznać (błąd składni): {\displaystyle , więc nie dodajemy jej do listy. W tym momencie zbiór } MParser nie mógł rozpoznać (błąd składni): {\displaystyle zawiera następujące elementy: } _Szablon:A(1)$,$_Szablon:A(a)$,$_Szablon:A(b)$,natomiastlistazawieraelementy$_Szablon:A(a^2)$,$_Szablon:A(ab)$,$_Szablon:A(ba)$.Zdejmujemyz$LParser nie mógł rozpoznać (błąd składni): {\displaystyle funkcję } _Szablon:A(a^2)$,dodajemyjado$MParser nie mógł rozpoznać (błąd składni): {\displaystyle i ponieważ } _Szablon:A(a^2a)=_Szablon:A(a^2)$i$_Szablon:A(a^2b)=_Szablon:A(b)$nicniedodajemydo$LParser nie mógł rozpoznać (błąd składni): {\displaystyle . Zdejmujemy teraz z listy funkcję } _Szablon:A(ab)Parser nie mógł rozpoznać (błąd składni): {\displaystyle , dodajemy ją do } MParser nie mógł rozpoznać (błąd składni): {\displaystyle i ponieważ } _Szablon:A(aba)Parser nie mógł rozpoznać (błąd składni): {\displaystyle nie należy do } L MParser nie mógł rozpoznać (błąd składni): {\displaystyle dodajemy ją do listy. } _Szablon:A(abb)=_Szablon:A(b)Parser nie mógł rozpoznać (błąd składni): {\displaystyle , więc tej funkcji nie dodajemy do } L$.Z$LParser nie mógł rozpoznać (błąd składni): {\displaystyle ściągamy } _Szablon:A(ba)Parser nie mógł rozpoznać (błąd składni): {\displaystyle , dodajemy ją do } MParser nie mógł rozpoznać (błąd składni): {\displaystyle i widzimy, że } _Szablon:A(baa)=_Szablon:A(a^2)$oraz$_Szablon:A(bab)=_Szablon:A(b)Parser nie mógł rozpoznać (błąd składni): {\displaystyle , więc nic nie dodajemy do } LParser nie mógł rozpoznać (błąd składni): {\displaystyle . Na liście pozostała funkcja } _Szablon:A(aba)Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Ściągamy ją z listy i dodajemy do } MParser nie mógł rozpoznać (błąd składni): {\displaystyle . Widzimy, że } _Szablon:A(abaa)=_Szablon:A(a^2)$i$_Szablon:A(abab)=_Szablon:A(b)$,zatemnicniedodajemydolisty$LParser nie mógł rozpoznać (błąd składni): {\displaystyle . Lista jest w tym momencie pusta i działanie algorytmu zakończyło się. Ostatecznie mamy }

M({A})= _Szablon:A(1),_Szablon:A(a),

_Szablon:A(b),_Szablon:A(a^2),_Szablon:A(ab),

_Szablon:A(ba),_Szablon:A(aba).

Parser nie mógł rozpoznać (błąd składni): {\displaystyle Co zgadza się z wynikiem otrzymanym w przykładzie. Twierdzenie poniższe zbiera dotychczas uzyskane charakteryzacje języków rozpoznawanych. \begintheor Niech } L A^* Parser nie mógł rozpoznać (błąd składni): {\displaystyle będzie dowolnym językiem. Równoważne są następujące warunki: # Język } L Parser nie mógł rozpoznać (błąd składni): {\displaystyle jest rozpoznawalny, # Język } L Parser nie mógł rozpoznać (błąd składni): {\displaystyle jest sumą wybranych klas równoważności pewnej prawej kongruen\-cji na } A^* Parser nie mógł rozpoznać (błąd składni): {\displaystyle o skończonym indeksie: }

L = _{w L}[w]_.

Parser nie mógł rozpoznać (błąd składni): {\displaystyle # Język } L Parser nie mógł rozpoznać (błąd składni): {\displaystyle jest sumą wybranych klas równoważności pewnej kongruencji na } A^* Parser nie mógł rozpoznać (błąd składni): {\displaystyle o skończonym indeksie: }

L = _{w L}[w]_.

Parser nie mógł rozpoznać (błąd składni): {\displaystyle # Istnie\-je skończony monoid } M Parser nie mógł rozpoznać (błąd składni): {\displaystyle i istnie\-je epimorfizm }  : A^* MParser nie mógł rozpoznać (błąd składni): {\displaystyle taki, że }

L = ^{-1}( (L)).

Parser nie mógł rozpoznać (nieznana funkcja „\endtheor”): {\displaystyle \endtheor \beginprf Dowód równoważności czterech powyższych warunków przeprowa\-dzi\-my zgodnie z następującym schematem: }

Uzupelnic tg|Uzupelnic tf|Uzupelnic te|Uzupelnic td| Uzupelnic tg|

Parser nie mógł rozpoznać (błąd składni): {\displaystyle [[##tg|Uzupelnic tg|]] [[##tf|Uzupelnic tf|]] Dany jest homomorfizm }

: A^* M,

$gdzie$MParser nie mógł rozpoznać (błąd składni): {\displaystyle jest skończonym monoidem.\\ Określamy relację na } A^*Parser nie mógł rozpoznać (błąd składni): {\displaystyle , przyjmując dla dowolnych } u, v A^*

u v (u) = (v).

Parser nie mógł rozpoznać (błąd składni): {\displaystyle Tak określona relacja jest kongruencją. Natomiast jej skończony indeks wynika z faktu, że monoid } M Parser nie mógł rozpoznać (błąd składni): {\displaystyle jest skończony. Pokażemy teraz, że: }

L = _{w L}[w]_ .

Parser nie mógł rozpoznać (błąd składni): {\displaystyle Inkluzja jest oczywista.\\ Inkluzja w przeciwną stronę (} L _{w L}[w]_,Parser nie mógł rozpoznać (błąd składni): {\displaystyle ) oznacza, że każda klasa równoważności relacji albo cała zawiera się w języku } LParser nie mógł rozpoznać (błąd składni): {\displaystyle , albo cała zawiera się w uzupełnieniu języka } LParser nie mógł rozpoznać (błąd składni): {\displaystyle .\\ Załóżmy, że } u [w]_$dlapewnego$ w L. Parser nie mógł rozpoznać (błąd składni): {\displaystyle Oznacza to, że }

u w (u) = (w) (L) u ^{-1}( (u)) ^{-1}( (L)) = L.

Parser nie mógł rozpoznać (błąd składni): {\displaystyle Implikuje to ostatecznie, że } u LParser nie mógł rozpoznać (błąd składni): {\displaystyle . [[##tf|Uzupelnic tf|]] [[##te|Uzupelnic te|]] Każda kongruencja jest prawą kongruencją. [[##te|Uzupelnic te|]] [[##td|Uzupelnic td|]] Niech będzie prawą kongruencją o skończonym indeksie na } A^* Parser nie mógł rozpoznać (błąd składni): {\displaystyle taką, że }

L = _{w L}[w]_ .

$Automat${A}_{ } = (A^*/,f^*,[1]_,T),Parser nie mógł rozpoznać (błąd składni): {\displaystyle dla którego }

f^*([w]_,u) =[wu]_ , T = [w]_  : w L

Parser nie mógł rozpoznać (błąd składni): {\displaystyle akceptuje język } LParser nie mógł rozpoznać (błąd składni): {\displaystyle . [[##td|Uzupelnic td|]] [[##tg|Uzupelnic tg|]] Niech język } L=L({A}) $,gdzie${A} = (S,f,s_0,T)Parser nie mógł rozpoznać (błąd składni): {\displaystyle .\\ Określamy odwzorowanie }

:A^{*} A^{*}/_{Ker _Szablon:A},

Parser nie mógł rozpoznać (błąd składni): {\displaystyle przyjmując dla każdego } v A^{*}

(v)=[v]_{Ker _Szablon:A}.

$Jesttoodwzorowaniekanonicznemonoidu$ A^* Parser nie mógł rozpoznać (błąd składni): {\displaystyle na monoid ilorazowy, a więc jest to epimorfizm.\\ } A^{*}/_{Ker _Szablon:A} Parser nie mógł rozpoznać (błąd składni): {\displaystyle jest monoidem skończonym, ponieważ } S Parser nie mógł rozpoznać (błąd składni): {\displaystyle jest zbiorem skończonym. Dla dowodu równości } L = ^{-1}( (L))Parser nie mógł rozpoznać (błąd składni): {\displaystyle wystarczy udowodnić inkluzję } L ^{-1}( (L))$.(Inkluzja$ L ^{-1}( (L))Parser nie mógł rozpoznać (błąd składni): {\displaystyle wynika z~definicji przeciwobrazu.) \\ Niech } u ^{-1}( (L)) .Parser nie mógł rozpoznać (błąd składni): {\displaystyle Oznacz to, że }

{c}

(u) (L) v L : (u)= (v) v L : [u]_{_{Ker _Szablon:A}}=[v]_{_{Ker _Szablon:A}}
v L : _Szablon:A(u)= _Szablon:A(v) , v L : s S f(s,u)=f(s,v)

Parser nie mógł rozpoznać (błąd składni): {\displaystyle W szczególności }

f(s_0,u) = f(s_0,v) T,

$czyli$u L.Parser nie mógł rozpoznać (nieznana funkcja „\begincenter”): {\displaystyle \begincenter \endcenter \endprf}