Analiza matematyczna 1/Wykład 1: Zbiory liczbowe

Twierdzenie 3.2.

Niech $L\subset A^{*}$ będzie dowolnym językiem. 1. Dla dowolnego języka $L\in {ℛ}{ℰ}{𝒞}(A^{*})$ monoid przejść automatu minimalnego ${{𝒜}}_L$ jest izomorficzny z monoidem syntaktycznym $M(L)$ języka $L$, czyli $M({{𝒜}}_L)\sim M(L).$ 2. (tw. J.Myhill'a) Język $L\subset A^{*}$ jest rozpoznawalny wtedy i tylko wtedy, gdy $M(L)$ jest monoidem skończonym.

Dowód

Dla dowodu punktu 1 wykażemy, że $P_L=Ke{r}_{{\tau }_{{{𝒜}}_L}},$ gdzie zgodnie z definicją dla dowolnych $w,u\in A^{*}$ ${\tau }_{{{𝒜}}_L}(w)([u{]}_{P_L^r})=f^{*}([u{]}_{P_L^r},w)=[uw{]}_{P_L^r}.$ $\begin{array}{c}(u,w)\in Ke{r}_{{\tau }_{{{𝒜}}_L}}\iff \mathrm{\forall }v\in A^{*}{\tau }_{{{𝒜}}_L}(u)([v{]}_{P_L^r})={\tau }_{{{𝒜}}_L}(w)([v{]}_{P_L^r})\iff [vu{]}_{P_L^r}=[vw{]}_{P_L^r}\iff \\ \iff \mathrm{\forall }v,z\in A^{*}vuz\in L\iff vwz\in L\iff [u{]}_{P_L}=[w{]}_{P_L}\iff (u,v)\in P_L.\\ \end{array}$ Korzystamy teraz z twierdzenia o rozkładzie epimorfizmu, które w tym przypadku ma postać: RYSUNEK ja-lekcja4-w-rys1.pdf czyli $M({{𝒜}}_L)\sim M(L)$. Dla dowodu punktu 2 załóżmy, że język $L$ jest rozpoznawalny. Zatem $L=\bigcup _{w\in L}[w{]}_{\rho },$ gdzie $\rho$ jest kongruencją o skończonym indeksie. Z twierdzenia (patrz Twierdzenie 2.1.) wnioskujemy, że $\rho \subseteq P_L.$ Oznacza to, że indeks relacji $P_L$ jest niewiększy od indeksu $\rho ,$ a co za tym idzie, $M(L)=A^{*}/P_L$ jest monoidem skończonym. Dla dowodu implikacji w stronę przeciwną rozważmy epimorfizm kanoniczny $k:A^{*}⟶A^{*}/P_L=M(L).$ Pokażemy, że spełnia on warunki z punktu 4. twierdzenia 1.2 (patrz twierdzenie 1.2.). $M(L)$ jest skończony, więc pozostaje do wykazania równość $L=k^{-1}(k(L)).$ W tym celu wystarczy oczywiście udowodnić inkluzję $k^{-1}(k(L))\subseteq L$. $\begin{array}{c}v\in k^{-1}(k(L))\Rightarrow k(v)\in k(L)\Rightarrow \mathrm{\exists }u\in L:k(v)=k(u)\in k(L)\iff \\ \iff \mathrm{\exists }u\in L:[v{]}_{P_L}=[u{]}_{P_L}\iff \mathrm{\exists }u\in L:v\in L\iff u\in L.\\ \end{array}$ Czyli $v\in L$ i $L=k^{-1}(k(L))$. i tutaj twierdzenie jsadhfouvnhter zsdkjrvnhr SFj v