Test GR2

Dla zainteresowanych 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

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))$.

	Złożoność czasowa	Złożoność pamięciowa
Maszyna dodająca	$f(0)=1$ $f(1)=3$ $f(n)=n+3;n\ge 2$	$f(0)=2$ $f(1)=3$ $f(n)=n+1;n\ge 2$
Maszyna rozpoznająca $w{w}^{\leftarrow }$	$f(n)=6+8+\dots +(n+3)+2;n=2k+1$ $f(n)=5+7+\dots +(n+3)+1;n=2k$	$f(n)=n+1$

$\Rightarrow$	0	1	...	...
Cell1	Cell2

$\Rightarrow$	0	1
0	1	1
1	0	1

$p$	$\mathrm{\neg }p$
0	1
1	0

$\wedge$	0	1
0	0	0
1	0	1

$\vee$	0	1
0	0	1
1	1	1

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{p}}	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{q}}	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{p} \wedge \textnormal{q}}	$\mathrm{\neg }(p\wedge q)$	$\mathrm{\neg }p$	$\mathrm{\neg }q$	$\mathrm{\neg }p\vee \mathrm{\neg }q$
0	0	0	1	1	1	1
0	1	0	1	1	0	1
1	0	0	1	0	1	1
1	1	1	0	0	0	0

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{p}}	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{q}}	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{r}}	Parser nie mógł rozpoznać (błąd składni): {\displaystyle (\textnormal{p} \wedge \textnormal{q})}	$(p\wedge r)$	$(q\wedge \mathrm{\neg }r)$	$(p\wedge r)\vee (q\wedge \mathrm{\neg }r)$	$(p\wedge q)\Rightarrow ((p\wedge r)\vee (q\wedge \mathrm{\neg }r))$
0	0	0	0	0	0	0	1
0	0	1	0	0	0	0	1
0	1	0	0	0	1	1	1
0	1	1	0	0	0	0	1
1	0	0	0	0	0	0	1
1	0	1	0	1	0	1	1
1	1	0	1	0	1	1	1
1	1	1	1	1	0	1	1

Numer funkcji	$p=0$ $q=0$	$p=0$ $q=1$	$p=1$ $q=0$	$p=1$ $q=1$
0	0	0	0	0		$F$
1	0	0	0	1		$\wedge$
2	0	0	1	0		$\mathrm{\neg }(p\Rightarrow q)$
3	0	0	1	1		Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{p}}
4	0	1	0	0		$\mathrm{\neg }(q\Rightarrow p)$
5	0	1	0	1		Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{q}}
6	0	1	1	0		$XOR$
7	0	1	1	1		$\vee$
8	1	0	0	0		$NOR$
9	1	0	0	1		$\iff$
10	1	0	1	0		$\mathrm{\neg }q$
11	1	0	1	1		$q\Rightarrow p$
12	1	1	0	0		$\mathrm{\neg }p$
13	1	1	0	1		$p\Rightarrow q$
14	1	1	1	0		$NAND$
15	1	1	1	1		$T$

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{p}}	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{q}}	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{r}}	$(p\leftrightarrow q)$	$(p\leftrightarrow q)\leftrightarrow r$	$(q\leftrightarrow r)$	$p\leftrightarrow (q\leftrightarrow r)$
0	0	0	1	0	1	0
0	0	1	1	1	0	1
0	1	0	0	1	0	1
0	1	1	0	0	1	0
1	0	0	0	1	1	1
1	0	1	0	0	0	0
1	1	0	1	0	0	0
1	1	1	1	1	1	1

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{p}}	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{q}}	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{r}}	$\circ (p,q,r)$
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	1

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{p}}	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{q}}	Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{r}}	$f_{p{\to }_{(}q\to r)}$
0	0	0	1
0	0	1	1
0	1	0	1
0	1	1	1
1	0	0	1
1	0	1	1
1	1	0	0
1	1	1	1

$\Rightarrow$	0	1	2
0	2	2	2
1	0	2	2
2	0	1	2

$\hat{\sigma }(f(t_0,..,t_n))=I(f)(\hat{\sigma }(t_0),..,\hat{\sigma }(t_n))$

$X^{*}=\{1\}\cup X\cup X^2\cup ...\cup X^n\cup \dots =\bigcup _{i=0}^{\mathrm{\infty }}{X}^i$

John Arthur Todd (1908-1994)
Zobacz biografię

Donald Ervin Knuth (1938-)
Zobacz biografię

Plik:Nagroda.jpeg

Nagroda Turinga
Zobacz Nagroda Turinga

Kurt Goedel (1906-1978)
Zobacz biografię

Noam Avram Chomsky (1928-)
Zobacz biografię

Stephen Cole Kleene (1909-1994)
Zobacz biografię

Axel Thue (1863-1922)
Zobacz biografię

Alonso Church (1903-1995)
Zobacz biografię

Sheila Greibach (1939-)
Zobacz biografię

Emil Leon Post (1897-1954)
Zobacz biografię

---

Pafnutij Lwowicz Czebyszew (1821-1894)
Zobacz biografię

Andriej Nikołajewicz Kołmogorow (1903-1987)
Zobacz biografię

Andriej Markow (1856-1922)
Zobacz biografię

Jakob Bernoulli (1654-1705)
Zobacz biografię

Félix Édouard Justin Émile Borel (1871-1956)
Zobacz biografię

Carl Friedrich Gauss (1777-1855)
Zobacz biografię

Henri Léon Lebesgue (1875-1941)
Zobacz biografię

Siméon Denis Poisson (1781-1840)
Zobacz biografię

Nagroda Goedla
Zobacz Nagroda Goedla]]

Nagroda Turinga
Zobacz Nagroda Turinga

Nagroda Knutha
Zobacz Nagroda Knutha

Parser nie mógł rozpoznać (nieznana funkcja „\begincases”): {\displaystyle g(C)=\begincases C\cup \{f(C')\} C \endcases }

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle g(C)=\left\{\aligned C\cup \{f(C')\}\\C\endaligned \right}

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle c\forall d\; c\in C \land d\in C \land c\sqsubseteq d\implies c\sqsubseteq' d, (C,\sqsubseteq) \preccurlyeq (C',\sqsubseteq') \iff C\subset C' \land \left\{\aligned \forall c \forall d\; &(c\in C\land d\in C) \implies (c\sqsubseteq d \iff c\sqsubseteq' d) \textrm{ oraz }\\ \forall c \forall d\; &(c\in C\land d\in C'\setminus C) \implies c\sqsubseteq' d \endaligned \right}