Test GR2: Różnice pomiędzy wersjami

Wersja z 17:46, 26 sie 2006

\begin{array}{ccccc} (s_{0}, ♯) \mapsto (s_{A}, ♯, 0) & (s_{0}, 0) \mapsto (r_{0}, ♯, 1) & (s_{0}, 1) \mapsto (r_{1}, ♯, 1) \\ (r_{0}, ♯) \mapsto (s_{R}, ♯, 0) & (r_{0}, 0) \mapsto ({r_{0}}^{'}, 0, 1) & (r_{0}, 1) \mapsto ({r_{0}}^{'}, 1, 1) \\ ({r_{0}}^{'}, ♯) \mapsto (q_{0}, ♯, - 1) & ({r_{0}}^{'}, 0) \mapsto ({r_{0}}^{'}, 0, 1) & ({r_{0}}^{'}, 1) \mapsto ({r_{0}}^{'}, 1, 1) \\ (q_{0}, 0) \mapsto (l, ♯, - 1) & (q_{0}, 1) \mapsto (s_{R}, ♯, - 1) \\ (r_{1}, ♯) \mapsto (s_{R}, ♯, 0) & (r_{1}, 0) \mapsto ({r_{1}}^{'}, 0, 1) & (r_{1}, 1) \mapsto ({r_{1}}^{'}, 1, 1) \\ ({r_{1}}^{'}, ♯) \mapsto (q_{1}, ♯, - 1) & ({r_{1}}^{'}, 0) \mapsto ({r_{1}}^{'}, 0, 1) & ({r_{1}}^{'}, 1) \mapsto ({r_{1}}^{'}, 1, 1) \\ (q_{1}, 0) \mapsto (s_{R}, ♯, 0) & (q_{1}, 1) \mapsto (l, ♯, - 1) \\ (l, ♯) \mapsto (s_{0}, ♯, 1) & (l, 0) \mapsto (l, 0, - 1) & (l, 1) \mapsto (l, 1, - 1) \\ (s_{R}, ♯) \mapsto (s_{R}, ♯, 0) \\ (s_{A}, ♯) \mapsto (s_{A}, ♯, 0) \end{array}

\begin{array}{ccccc} (s_{0}, ♯) \mapsto (s_{R}, ♯, 0) & (s_{1}, ♢) \mapsto (s 1, ♢, 1) \\ (s_{0}, 0) \mapsto (s_{1}, ♣, 1) & (s_{1}, 0) \mapsto (s_{2}, ♢, 1) \\ (s_{1}, ♯) \mapsto (s_{A}, ♯, 0) \\ (s_{2}, ♢) \mapsto (s_{2}, ♢, 1) & (s_{3}, 0) \mapsto (s_{2}, ♢, 1) \\ (s_{2}, ♯) \mapsto (s_{4}, ♯, - 1) & (s_{3}, ♢) \mapsto (s_{3}, ♢, 1) \\ (s_{2}, 0) \mapsto (s_{3}, 0, 1) & (s_{3}, ♯) \mapsto (s_{R}, ♯, 0) \\ (s_{4}, 0) \mapsto (s_{4}, 0, - 1) \\ (s_{4}, ♢) \mapsto (s_{4}, ♢, - 1) \\ (s_{4}, ♣) \mapsto (s_{2}, ♣, 1) \\ (s_{A}, ♯) \mapsto (s_{A}, ♯, 0) & (s_{R}, ♯) \mapsto (s_{R}, ♯, 0) \end{array}

\begin{array}{ccccc} s_{0} & s_{1} & s_{2} \\ τ_{𝒜} (1) & s_{0} & s_{1} & s_{2} \\ τ_{𝒜} (a) & s_{1} & s_{2} & s_{2} \\ τ_{𝒜} (b) & s_{0} & s_{0} & s_{0} \\ τ_{𝒜} (a^{2}) & s_{2} & s_{2} & s_{2} \\ τ_{𝒜} (a b) & s_{0} & s_{0} & s_{2} \\ τ_{𝒜} (b a) & s_{1} & s_{1} & s_{1} \\ τ_{𝒜} (b^{2}) & s_{0} & s_{0} & s_{0} \\ τ_{𝒜} (a b a) & s_{1} & s_{1} & s_{2} \\ . . . & . . . & . . . & . . . \end{array}

\begin{array}{ccccc} f & s_{0} & s_{1} & s_{2} & s_{3} \\ a & s_{1} & s_{2} & s_{0} & s_{2} \\ b & s_{3} & s_{2} & s_{2} & s_{2} \end{array}

Algorytm Minimalizuj2 - algorytm minimalizacji automatu wykorzystujący stabilizujący się ciąg relacji

  1  Wejście:  $𝒜 = (S, A, f, s_{0}, T)$  - automat taki, że  $L = L (𝒜)$ .
  2  Wyjście: automat minimalny  $𝒜^{'} = (S^{'}, A^{'}, f^{'}, {s_{0}}^{'}, T^{'})$  dla  $𝒜$ .
  3   ${\overline{ρ}}_{1} \leftarrow \approx_{𝒜}$ ;
  4   $i \leftarrow 1$ ;
  5  repeat
  6    Parser nie mógł rozpoznać (nieznana funkcja „\slash”): {\displaystyle \displaystyle \slash \slash}
 oblicz  ${\overline{ρ}}_{i}$ :  $s_{1} {\overline{ρ}}_{i} s_{2} \Leftrightarrow (s_{1} {\overline{ρ}}_{i - 1} s_{2}) \land (\forall a \in A f (s_{1}, a) {\overline{ρ}}_{i - 1} f (s_{2}, a))$ ;
  7     $i \leftarrow i + 1$ ;
  8    empty $({\overline{ρ}}_{i})$  
  9    for each  $(s_{1}, s_{2}) \in S \times S$  do
 10      flag $\leftarrow$ true;
 11      for each  $a \in A$  
 12        if not  $f (s_{1}, a) {\overline{ρ}}_{i - 1} f (s_{2}, a)$  then
 13          flag $\leftarrow$ false;
 14        end if
 15      end for
 16      if flag=true and  $s_{1} {\overline{ρ}}_{i - 1} s_{2}$  then
 17         ${\overline{ρ}}_{i} \leftarrow {\overline{ρ}}_{i} \cup {(s_{1}, s_{2})}$ ;
 18      end if
 19    end for
 20  until  ${\overline{ρ}}_{i} = {\overline{ρ}}_{i - 1}$ 
 21  Parser nie mógł rozpoznać (nieznana funkcja „\slash”): {\displaystyle \displaystyle S' \leftarrow S \slash \overline{\rho}_i}
;
 22  for each Parser nie mógł rozpoznać (nieznana funkcja „\slash”): {\displaystyle \displaystyle [s]_{\overline{\rho}_i} \in S \slash \overline{\rho}_i}
 do
 23    for each  $a \in A$  do
 24       $f^{'} ([s]_{{\overline{ρ}}_{i}}, a) \leftarrow [f (s, a)]_{{\overline{ρ}}_{i}}$ ;
 25    end for
 26  end for
 27   ${s_{0}}^{'} \leftarrow [s_{0}]_{{\overline{ρ}}_{i}}$ ;
 28   $T^{'} \leftarrow {[t]_{{\overline{ρ}}_{i}} : t \in T}$ ;
 29  return  $𝒜^{'} = (S^{'}, A, f^{'}, {s_{0}}^{'}, T^{'})$ ;

Uzupelnij tytul
	$s_{0}$ \|\| $s_{1}$ \|\| $s_{2}$
$τ_{𝒜} (1)$ \|\| $s_{0}$ \|\| $s_{1}$ \|\| $s_{2}$
$τ_{𝒜} (a)$ \|\| $s_{1}$ \|\| $s_{2}$ \|\| $s_{2}$
$τ_{𝒜} (b)$ \|\| $s_{0}$ \|\| $s_{0}$ \|\| $s_{0}$
$τ_{𝒜} (a^{2})$ \|\| $s_{2}$ \|\| $s_{2}$ \|\| $s_{2}$
$τ_{𝒜} (a b)$ \|\| $s_{0}$ \|\| $s_{0}$ \|\| $s_{2}$
$τ_{𝒜} (b a)$ \|\| $s_{1}$ \|\| $s_{1}$ \|\| $s_{1}$
$τ_{𝒜} (b^{2})$ \|\| $s_{0}$ \|\| $s_{0}$ \|\| $s_{0}$
$τ_{𝒜} (a b a)$ \|\| $s_{1}$ \|\| $s_{1}$ \|\| $s_{2}$
... \|\| ... \|\| ... \|\| ...

$\begin{array}{lll} b) \lim_{x \to 2^{+}} (x - 2) e^{\frac{1}{x - 2}} & = & \lim_{x \to 2^{+}} \frac{e^{\frac{1}{x - 2}}}{(x - 2)^{- 1}} \begin{array}{c} [\frac{\infty}{\infty}] \\ = \\ H \end{array} \lim_{x \to 2^{+}} \frac{- (x - 2)^{- 2} e^{\frac{1}{x - 2}}}{- (x - 2)^{- 2}} = \\ = & \lim_{x \to 2^{+}} e^{\frac{1}{x - 2}} = + \infty; \end{array}$

 alalalalaa

alala

	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}

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}

$h (0, a) = f (a)$ dla każdego Parser nie mógł rozpoznać (błąd składni): {\displaystyle a \in A \\h(n', a) = g(h(n, a), n, a)} dla każdego $a \in A$ i $n \in ℕ$

$e (0, a) = f (a)$ dla każdego Parser nie mógł rozpoznać (błąd składni): {\displaystyle a \in A \\ e(g(n, a), n, a)} dla każdego $a \in A$ i $n \in m$

@@ Linia 1: / Linia 1: @@
+<center><math>\displaystyle \begin{array} {c|c|c|c|c|} (s_0,\sharp)\mapsto (s_A,\sharp,0) & (s_0,0)\mapsto (r_0,\sharp,1) & (s_0,1)\mapsto (r_1,\sharp,1)\\
+\hline (r_0,\sharp)\mapsto (s_R,\sharp,0) & (r_0,0)\mapsto (r_0',0,1) & (r_0,1)\mapsto (r_0',1,1)\\
+\hline (r_0',\sharp)\mapsto (q_0,\sharp,-1) & (r_0',0)\mapsto (r_0',0,1) & (r_0',1)\mapsto (r_0',1,1)\\
+\hline  & (q_0,0)\mapsto (l,\sharp,-1) & (q_0,1)\mapsto (s_R,\sharp,-1)\\
+\hline (r_1,\sharp)\mapsto (s_R,\sharp,0) & (r_1,0)\mapsto (r_1',0,1) & (r_1,1)\mapsto (r_1',1,1)\\
+\hline (r_1',\sharp)\mapsto (q_1,\sharp,-1) & (r_1',0)\mapsto (r_1',0,1) & (r_1',1)\mapsto (r_1',1,1)\\
+\hline  & (q_1,0)\mapsto (s_R,\sharp,0) & (q_1,1)\mapsto (l,\sharp,-1)\\
+\hline (l,\sharp)\mapsto (s_0,\sharp,1) & (l,0)\mapsto (l,0,-1) & (l,1)\mapsto (l,1,-1)\\
+\hline (s_R,\sharp)\mapsto (s_R,\sharp,0) &  & \\
+\hline (s_A,\sharp)\mapsto (s_A,\sharp,0) &  & \\
+\hline \end{array}  </math></center>
 <center><math>\displaystyle \begin{array} {c|c|c|c|c|} (s_0,\sharp)\mapsto (s_R,\sharp,0) & (s_1,\diamondsuit)\mapsto(s1,\diamondsuit,1)\\
 \hline (s_0,0)\mapsto(s_1,\clubsuit,1) & (s_1,0) \mapsto(s_2,\diamondsuit,1)\\

	$s_{0}$ \|\| $s_{1}$ \|\| $s_{2}$
$τ_{𝒜} (1)$ \|\| $s_{0}$ \|\| $s_{1}$ \|\| $s_{2}$
$τ_{𝒜} (a)$ \|\| $s_{1}$ \|\| $s_{2}$ \|\| $s_{2}$
$τ_{𝒜} (b)$ \|\| $s_{0}$ \|\| $s_{0}$ \|\| $s_{0}$
$τ_{𝒜} (a^{2})$ \|\| $s_{2}$ \|\| $s_{2}$ \|\| $s_{2}$
$τ_{𝒜} (a b)$ \|\| $s_{0}$ \|\| $s_{0}$ \|\| $s_{2}$
$τ_{𝒜} (b a)$ \|\| $s_{1}$ \|\| $s_{1}$ \|\| $s_{1}$
$τ_{𝒜} (b^{2})$ \|\| $s_{0}$ \|\| $s_{0}$ \|\| $s_{0}$
$τ_{𝒜} (a b a)$ \|\| $s_{1}$ \|\| $s_{1}$ \|\| $s_{2}$
... \|\| ... \|\| ... \|\| ...

Test GR2: Różnice pomiędzy wersjami

Wersja z 17:46, 26 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