Test GR2: Różnice pomiędzy wersjami

Wersja z 14:32, 15 sie 2006

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

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

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

$p$	$\neg p$
0	1
1	0

$\land$	0	1
0	0	0
1	0	1

$\lor$	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}}	$\neg (p \land q)$	$\neg p$	$\neg q$	$\neg p \lor \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 \land r)$	$(q \land \neg r)$	$(p \land r) \lor (q \land \neg r)$	$(p \land q) \Rightarrow ((p \land r) \lor (q \land \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	$\land$
2	0	0	1	0	$\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	$\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	$X O R$
7	0	1	1	1	$\lor$
8	1	0	0	0	$N O R$
9	1	0	0	1	$\Leftrightarrow$
10	1	0	1	0	$\neg q$
11	1	0	1	1	$q \Rightarrow p$
12	1	1	0	0	$\neg p$
13	1	1	0	1	$p \Rightarrow q$
14	1	1	1	0	$N A N D$
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{σ} (f (t_{0}, . ., t_{n})) = I (f) (\hat{σ} (t_{0}), . ., \hat{σ} (t_{n}))$

X^{*} = {1} \cup X \cup X^{2} \cup . . . \cup X^{n} \cup \dots = ⋃_{i = 0}^{\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ę

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}

@@ Linia 1: / Linia 1: @@
-{|width=100% border="0" cellpadding="5" cellspacing="20"
-|- style="background-color:#abcdef;"
-| <span style="font-variant:small-caps">Dla zainteresowanych 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
-<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.
-|}
-{|width=100% border="0" cellpadding="5" cellspacing="20"
-|- style="background-color:#abcdef;"
-| <span style="font-variant:small-caps">Dowód</span>
-|-
-| 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>
-<center><math>\tau _{\mathcal{A}_{L}}(w)([u]_{P^{r}_{L}})=f^{*}([u]_{P^{r}_{L}},w)=[uw]_{P^{r}_{L}}.</math></center>
-<center><math>\begin{array} {c}
-(u,w)\in Ker_{\tau _{\mathcal{A}_{L}}}\Leftrightarrow \forall v\in A^*\;\;
-\tau _{\mathcal{A}_{L}}(u)([v]_{P^{r}_{L}})=\tau _{\mathcal{A}_{L}}(w)([v]_{P^{r}_{L}})\Leftrightarrow
-[vu]_{P^{r}_{L}}=[vw]_{P^{r}_{L}}\Leftrightarrow\\
-\Leftrightarrow \forall v,z \in A^*\;\;vuz\in L\Leftrightarrow vwz\in L \Leftrightarrow[u]_{P_{L}}=[w]_{P_{L}}
-\Leftrightarrow (u,v) \in P_L.\\
-\end{array} </math></center>
-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
-|}
-{{twierdzenie|3.2.||
-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
-<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.
-}}
-{{dowod|||
-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>
-<center><math>\tau _{\mathcal{A}_{L}}(w)([u]_{P^{r}_{L}})=f^{*}([u]_{P^{r}_{L}},w)=[uw]_{P^{r}_{L}}.</math></center>
-<center><math>\begin{array} {c}
-(u,w)\in Ker_{\tau _{\mathcal{A}_{L}}}\Leftrightarrow \forall v\in A^*\;\;
-\tau _{\mathcal{A}_{L}}(u)([v]_{P^{r}_{L}})=\tau _{\mathcal{A}_{L}}(w)([v]_{P^{r}_{L}})\Leftrightarrow
-[vu]_{P^{r}_{L}}=[vw]_{P^{r}_{L}}\Leftrightarrow\\
-\Leftrightarrow \forall v,z \in A^*\;\;vuz\in L\Leftrightarrow vwz\in L \Leftrightarrow[u]_{P_{L}}=[w]_{P_{L}}
-\Leftrightarrow (u,v) \in P_L.\\
-\end{array} </math></center>
-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>.
-}}
 {| border="1" cellspacing="0"
 ! !! Złożoność czasowa !! Złożoność pamięciowa

Test GR2: Różnice pomiędzy wersjami

Wersja z 14:32, 15 sie 2006

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia

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 \land r)$	$(q \land \neg r)$	$(p \land r) \lor (q \land \neg r)$	$(p \land q) \Rightarrow ((p \land r) \lor (q \land \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

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 \land r)$	$(q \land \neg r)$	$(p \land r) \lor (q \land \neg r)$	$(p \land q) \Rightarrow ((p \land r) \lor (q \land \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

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 \land r)$	$(q \land \neg r)$	$(p \land r) \lor (q \land \neg r)$	$(p \land q) \Rightarrow ((p \land r) \lor (q \land \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