Test GR2: Różnice pomiędzy wersjami

Wersja z 14:50, 5 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

@@ Linia 138: / Linia 138: @@
 |-
 | 1|| 1|| 1|| 1|| 1|| 1|| 1
+|}
+{| border="1"
+! <math>\textnormal{p}</math>!! <math>\textnormal{q}</math>!! <math>\textnormal{r}</math>!!<math>\circ (p, q, r)</math>
+|-
+| 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
+|}
+{| border="1"
+! <math>\textnormal{p}</math>!! <math>\textnormal{q}</math>!! <math>\textnormal{r}</math>!!<math>f_{p \rightarrow _(q \rightarrow r)}</math>
+|-
+| 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
 |}

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