|
|
| Linia 4: |
Linia 4: |
| <span style="font-variant:small-caps">Twierdzenie 3.2.</span> | | <span style="font-variant:small-caps">Twierdzenie 3.2.</span> |
| | | |
| Niech <math>L\subset A^{*} </math> będzie dowolnym językiem. | | Niech <math>L\subset A^{*} </math> |
| :1. Dla dowolnego języka <math>L\in \mathcal{REC}(A^{*}) </math> monoid przejść automatu minimalnego <math>\mathcal{A}_{L} </math> jest izomorficzny z monoidem syntaktycznym <math> M(L) </math> języka <math>L</math>, czyli
| |
| <center><math>M(\mathcal{A}_{L})\sim M(L). </math></center>
| |
| :2. (tw. J.Myhill'a) Język <math>\; L \subset A^* \;</math> jest rozpoznawalny wtedy i tylko wtedy, gdy <math>\; M(L) \;</math> jest monoidem skończonym.
| |
|
| |
|
| <span style="font-variant:small-caps">Dowód</span> | | <span style="font-variant:small-caps">Dowód</span> |
|
| |
|
| Dla dowodu punktu 1 wykażemy, że | | Dla dowodu punktu 1 wykażemy, że |
|
| |
| <center><math>P_{L}=Ker_{\tau_{\mathcal{A}_{L}}}, </math></center>
| |
|
| |
| gdzie zgodnie z definicją dla dowolnych <math>w,u\in A^{*} </math>
| |
|
| |
|
| |
| Korzystamy teraz z twierdzenia o rozkładzie epimorfizmu, które w tym przypadku
| |
| ma postać: <br>
| |
|
| |
| '''RYSUNEK ja-lekcja4-w-rys1.pdf'''<br>
| |
|
| |
| czyli <math>M(\mathcal{A}_{L})\sim M(L) </math>. <br>
| |
| Dla dowodu punktu 2 załóżmy, że język <math>\; L \;</math> jest rozpoznawalny.
| |
| Zatem
| |
| <center><math>L = \bigcup_{w \in L} [w]_\rho ,</math></center> gdzie <math>\; \rho \;</math> jest kongruencją o skończonym indeksie.
| |
| Z twierdzenia (patrz [[#twierdzenie_2_1|Twierdzenie 2.1.]]) wnioskujemy, że <math>\rho \subseteq P_L .</math> Oznacza to, że indeks relacji <math>\; P_L \;</math> jest niewiększy od indeksu <math>\; \rho, \;</math> a co za tym idzie, <math>\; M(L) = A^*/P_L \;</math> jest monoidem skończonym.
| |
|
| |
| Dla dowodu implikacji w stronę przeciwną rozważmy epimorfizm
| |
| kanoniczny <center><math>k : A^* \longrightarrow A^*/P_L = M(L).</math></center> Pokażemy, że
| |
| spełnia on warunki z punktu 4. twierdzenia 1.2 (patrz [[Języki, automaty i obliczenia/Wykład 3: Automat skończenie stanowy#twierdzenie_1_2|twierdzenie 1.2.]]). <math>M(L)
| |
| \;</math> jest skończony, więc pozostaje do wykazania
| |
| równość
| |
| <center><math>\; L = k^{-1}(k(L)). \;</math></center> W tym celu wystarczy oczywiście udowodnić inkluzję
| |
| <math>\; k^{-1}(k(L)) \subseteq L</math>. <br>
| |
|
| |
| <center><math>\begin{array} {c}
| |
| v \in k^{-1}(k(L))\Rightarrow k(v) \in k(L)\Rightarrow\exists u \in L:k(v) = k(u) \in k(L)\Leftrightarrow\\
| |
| \Leftrightarrow \exists u \in L:[v]_{P_L} = [u]_{P_L}\Leftrightarrow\exists u \in L:v \in L\Leftrightarrow u\in L.\\
| |
| \end{array}
| |
| </math></center>
| |
| Czyli <math>v\in L</math> i <math>\; L = k^{-1}(k(L))</math>.
| |
| i tutaj twierdzenie jsadhfouvnhter zsdkjrvnhr SFj v
| |
| }} | | }} |
Uwaga [dla zainteresowanych]
{{{3}}}
