Analiza matematyczna 1/Wykład 1: Zbiory liczbowe: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Nie podano opisu zmian |
Nie podano opisu zmian |
||
| Linia 1: | Linia 1: | ||
{| | {{uwaga|[dla zainteresowanych]|| | ||
Następne twierdzenie charakteryzuje monoid przejść automatu minimalnego i podaje kolejny warunek równoważny na to, żeby język był rozpoznawany przez automat. | |||
<span style="font-variant:small-caps">Twierdzenie 3.2.</span> | |||
Niech <math>L\subset A^{*} </math> będzie dowolnym językiem. | |||
: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 | :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> | <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. | :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> | |||
Dla dowodu punktu 1 wykażemy, że | |||
<center><math>P_{L}=Ker_{\tau | <center><math>P_{L}=Ker_{\tau | ||
| Linia 56: | Linia 55: | ||
</math></center> | </math></center> | ||
Czyli <math>v\in L</math> i <math>\; L = k^{-1}(k(L))</math>. | Czyli <math>v\in L</math> i <math>\; L = k^{-1}(k(L))</math>. | ||
i tutaj twierdzenie jsadhfouvnhter zsdkjrvnhr SFj v | i tutaj twierdzenie jsadhfouvnhter zsdkjrvnhr SFj v}} | ||
Wersja z 08:47, 16 sie 2006
Uwaga [dla zainteresowanych]
{{{3}}}
