Test GR2: Różnice pomiędzy wersjami

Wersja z 09:36, 24 sie 2006

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$  
 10      flag $\leftarrow$ true;
 11      for each  $a \in A$  
 12        if not  $f (s_{1}, a) {\overline{ρ}}_{i - 1} f (s_{2}, a)$  
 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 2: / Linia 2: @@
 wykorzystujący stabilizujący się ciąg relacji|algorytm minimalizacji automatu wykorzystujący stabilizujący się ciąg relacji|
-  Wejście: <math>\displaystyle \mathcal{A}=(S, A, f, s_0, T)</math> -- automat taki, że
+  Wejście: <math>\displaystyle \mathcal{A}=(S, A, f, s_0, T)</math> - automat taki, że <math>\displaystyle L=L(\mathcal{A})</math>.
-<math>\displaystyle L=L(\mathcal{A})</math>.
   Wyjście: automat minimalny <math>\displaystyle \mathcal{A}'=(S',A',f', s_0',
 T')</math> dla <math>\displaystyle \mathcal{A}</math>.
@@ Linia 9: / Linia 8: @@
   <math>\displaystyle i \leftarrow 1</math>;
   '''repeat'''
-<math>\displaystyle \slash \slash</math> oblicz <math>\displaystyle \overline{\rho}_i</math>: <math>\displaystyle s_1
+   <math>\displaystyle \slash \slash</math> oblicz <math>\displaystyle \overline{\rho}_i</math>: <math>\displaystyle s_1
 \overline{\rho}_i s_2 \Leftrightarrow (s_1 \overline{\rho}_{i-1}
 s_2) \wedge (\forall a \in A\ f(s_1, a) \overline{\rho}_{i-1}
 f(s_2,a))</math>;
+   <math>\displaystyle i \leftarrow i+1</math>;
-<math>\displaystyle i \leftarrow i+1</math>;
+   '''empty'''<math>\displaystyle (\overline{\rho}_i)</math>
-'''empty'''<math>\displaystyle (\overline{\rho}_i)</math>
+   '''for''' '''each''' <math>\displaystyle (s_1,s_2)\in S\times S</math>
-'''for''' '''each''' <math>\displaystyle (s_1,s_2)\in S\times S</math>
+     flag<math>\displaystyle \leftarrow</math>'''true''';
-flag<math>\displaystyle \leftarrow</math>'''true''';
+     '''for''' '''each''' <math>\displaystyle a\in A</math>
-'''for''' '''each''' <math>\displaystyle a\in A</math>
+       '''if''' '''not''' <math>\displaystyle f(s_1, a) \overline{\rho}_{i-1} f(s_2,a)</math>
-'''if''' '''not''' <math>\displaystyle f(s_1, a) \overline{\rho}_{i-1} f(s_2,a)</math>
+         flag<math>\displaystyle \leftarrow</math>'''false''';
-flag<math>\displaystyle \leftarrow</math>'''false''';
+       '''end''' '''if'''
-'''end''' '''if'''
+     '''end''' '''for'''
-'''end''' '''for'''
+     '''if''' flag<nowiki>=</nowiki>'''true''' '''and''' <math>\displaystyle s_1 \overline{\rho}_{i-1} s_2</math> '''then'''
-'''if''' flag<nowiki>=</nowiki>'''true''' '''and''' <math>\displaystyle s_1 \overline{\rho}_{i-1} s_2</math> '''then'''
+       <math>\displaystyle \overline{\rho}_{i} \leftarrow \overline{\rho}_{i} \cup \{(s_1,s_2)\}</math>;
-<math>\displaystyle \overline{\rho}_{i} \leftarrow \overline{\rho}_{i} \cup \{(s_1,s_2)\}</math>;
+     '''end''' '''if'''
-'''end''' '''if'''
+   '''end''' '''for'''
-'''end''' '''for'''
   '''until''' <math>\displaystyle \overline{\rho}_i = \overline{\rho}_{i-1}</math>}
   <math>\displaystyle S' \leftarrow S \slash \overline{\rho}_i</math>;
   '''for''' '''each''' <math>\displaystyle [s]_{\overline{\rho}_i} \in S \slash \overline{\rho}_i</math> '''do'''
-'''for''' '''each''' <math>\displaystyle a \in A</math> '''do'''
+   '''for''' '''each''' <math>\displaystyle a \in A</math> '''do'''
-<math>\displaystyle f'([s]_{\overline{\rho}_i},a) \leftarrow
+     <math>\displaystyle f'([s]_{\overline{\rho}_i},a) \leftarrow
 [f(s,a)]_{\overline{\rho}_i}</math>;
-'''end''' '''for'''
+   '''end''' '''for'''
   '''end''' '''for'''
   <math>\displaystyle s_0' \leftarrow [s_0]_{\overline{\rho}_i}</math>;

	$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 09:36, 24 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