Test GR2

$\varphi$	$\psi$	$\psi \Rightarrow \varphi$	$(\varphi \Rightarrow (\psi \Rightarrow \varphi ))$
0	0	1	1
0	1	0	1
1	0	1	1
1	1	1	1

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left| x \right|\ = \left\{ \begin{array}{rll} x & \text{ gdy }, x\geq 0 \\ -x & \text{ w przeciwnym przypadku}. \end{array}}

Parser nie mógł rozpoznać (błąd składni): {\displaystyle w_3 &\rightarrow bv_3v_2w_3v_1v_3v_3v_2\ |\ aw_3v_1v_3v_3v_2\ |\ bv_3v_2v_1v_3v_3v_2 \\ \begin{array}{lll} & & |\ av_1v_3v_3v_2\ |\ bv_3v_3v_2 \end{array}}

oraz

Parser nie mógł rozpoznać (błąd składni): {\displaystyle w_3 &\rightarrow bv_3v_2w_3v_1v_3v_3v_2w_3\ |\ aw_3v_1v_3v_3v_2w_3\ |\ bv_3v_2v_1v_3v_3v_2w_3 \\ \begin{array}{lll} & & |\ av_1v_3v_3v_2w_3\ |\ bv_3v_3v_2w_3 \end{array}}

Ostatecznie, gramatyka w postaci Greibach ma postać:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle v_1 &\rightarrow bv_3v_2w_3v_1v_3\ |\ aw_3v_1v_3\ |\ bv_3v_2v_1v_3\ |\ av_1v_3\ |\ bv_3 \\ v_2 &\rightarrow bv_3v_2w_3v_1\ |\ aw_3v_1\ |\ bv_3v_2v_1\ |\ av_1\ |\ b \\ v_3 &\rightarrow bv_3v_2w_3\ |\ aw_3\ |\ bv_3v_2\ |\ a \\ w_3 &\rightarrow bv_3v_2w_3v_1v_3v_3v_2\ |\ aw_3v_1v_3v_3v_2\ |\ bv_3v_2v_1v_3v_3v_2 \\ \begin{array}{lll} & & |\ av_1v_3v_3v_2\ |\ bv_3v_3v_2 bv_3v_2w_3v_1v_3v_3v_2w_3 \\ & & |\ aw_3v_1v_3v_3v_2w_3\ |\ bv_3v_2v_1v_3v_3v_2w_3\ \\ & & |\ av_1v_3v_3v_2w_3\ |\ bv_3v_3v_2w_3 \end{array}}

$\begin{array}{cccc}Krok& dodanedo{S}^{\prime }& okreslenie{f}^{\prime }& dodanedo{T}^{\prime }\\ 0& \{q_0\}& & \mathrm{\varnothing }\\ 1& \{q_0,q_3\}& f^{\prime }(\{q_0\},a)=\{q_0,q_3\}& \mathrm{\varnothing }\\ & \{q_0,q_1\}& f^{\prime }(\{q_0\},b)=\{q_0,q_1\}& \\ 2& \{q_0,q_3,q_4\}& f^{\prime }(\{q_0,q_3\},a)=\{q_0,q_3,q_4\}& \{q_0,q_3,q_4\}\\ & & f^{\prime }(\{q_0,q_3\},b)=\{q_0,q_1\}& \\ & & f^{\prime }(\{q_0,q_1\},a)=\{q_0,q_3\}& \\ & \{q_0,q_1,q_2\}& f^{\prime }(\{q_0,q_1\},b)=\{q_0,q_1,q_2\}& \{q_0,q_1,q_2\}\\ 3& & f^{\prime }(\{q_0,q_3,q_4\},a)=\{q_0,q_3,q_4\}& \\ & \{q_0,q_1,q_4\}& f^{\prime }(\{q_0,q_3,q_4\},b)=\{q_0,q_1,q_4\}& \{q_0,q_1,q_4\}\\ & \{q_0,q_2,q_3\}& f^{\prime }(\{q_0,q_1,q_2\},a)=\{q_0,q_2,q_3\}& \{q_0,q_2,q_3\}\\ & & f^{\prime }(\{q_0,q_1,q_2\},b)=\{q_0,q_1,q_2\}& \\ 4& & f^{\prime }(\{q_0,q_1,q_4\},a)=\{q_0,q_3,q_4\}& \\ & \{q_0,q_1,q_2,q_4\},& f^{\prime }(\{q_0,q_1,q_4\},b)=\{q_0,q_1,q_2,q_4\}& \{q_0,q_1,q_2,q_4\}\\ & \{q_0,q_2,q_3,q_4\}& f^{\prime }(\{q_0,q_2,q_3\},a)=\{q_0,q_2,q_3,q_4\}& \{q_0,q_2,q_3,q_4\}\\ & & f^{\prime }(\{q_0,q_2,q_3\},b)=\{q_0,q_1,q_2\}& \\ 5& & f^{\prime }(\{q_0,q_1,q_2,q_4\},a)=\{q_0,q_2,q_3,q_4\}& \\ & & f^{\prime }(\{q_0,q_1,q_2,q_4\},b)=\{q_0,q_1,q_2,q_4\}& \\ & & f^{\prime }(\{q_0,q_2,q_3,q_4\},a)=\{q_0,q_2,q_3,q_4\}& \\ & & f^{\prime }(\{q_0,q_2,q_3,q_4\},b)=\{q_0,q_1,q_2,q_4\}& \end{array}$

$\begin{array}{ccc}(s_0,\mathrm{♯})\mapsto (s_A,\mathrm{♯},0)& (s_0,0)\mapsto (r_0,\mathrm{♯},1)& (s_0,1)\mapsto (r_1,\mathrm{♯},1)\\ (r_0,\mathrm{♯})\mapsto (s_R,\mathrm{♯},0)& (r_0,0)\mapsto ({r_0}^{\prime },0,1)& (r_0,1)\mapsto ({r_0}^{\prime },1,1)\\ ({r_0}^{\prime },\mathrm{♯})\mapsto (q_0,\mathrm{♯},-1)& ({r_0}^{\prime },0)\mapsto ({r_0}^{\prime },0,1)& ({r_0}^{\prime },1)\mapsto ({r_0}^{\prime },1,1)\\ & (q_0,0)\mapsto (l,\mathrm{♯},-1)& (q_0,1)\mapsto (s_R,\mathrm{♯},-1)\\ (r_1,\mathrm{♯})\mapsto (s_R,\mathrm{♯},0)& (r_1,0)\mapsto ({r_1}^{\prime },0,1)& (r_1,1)\mapsto ({r_1}^{\prime },1,1)\\ ({r_1}^{\prime },\mathrm{♯})\mapsto (q_1,\mathrm{♯},-1)& ({r_1}^{\prime },0)\mapsto ({r_1}^{\prime },0,1)& ({r_1}^{\prime },1)\mapsto ({r_1}^{\prime },1,1)\\ & (q_1,0)\mapsto (s_R,\mathrm{♯},0)& (q_1,1)\mapsto (l,\mathrm{♯},-1)\\ (l,\mathrm{♯})\mapsto (s_0,\mathrm{♯},1)& (l,0)\mapsto (l,0,-1)& (l,1)\mapsto (l,1,-1)\\ (s_R,\mathrm{♯})\mapsto (s_R,\mathrm{♯},0)& & \\ (s_A,\mathrm{♯})\mapsto (s_A,\mathrm{♯},0)& & \end{array}$

$\begin{array}{cc}(s_0,\mathrm{♯})\mapsto (s_R,\mathrm{♯},0)& (s_1,\mathrm{♢})\mapsto (s1,\mathrm{♢},1)\\ (s_0,0)\mapsto (s_1,\mathrm{♣},1)& (s_1,0)\mapsto (s_2,\mathrm{♢},1)\\ & (s_1,\mathrm{♯})\mapsto (s_A,\mathrm{♯},0)\\ (s_2,\mathrm{♢})\mapsto (s_2,\mathrm{♢},1)& (s_3,0)\mapsto (s_2,\mathrm{♢},1)\\ (s_2,\mathrm{♯})\mapsto (s_4,\mathrm{♯},-1)& (s_3,\mathrm{♢})\mapsto (s_3,\mathrm{♢},1)\\ (s_2,0)\mapsto (s_3,0,1)& (s_3,\mathrm{♯})\mapsto (s_R,\mathrm{♯},0)\\ (s_4,0)\mapsto (s_4,0,-1)& \\ (s_4,\mathrm{♢})\mapsto (s_4,\mathrm{♢},-1)& \\ (s_4,\mathrm{♣})\mapsto (s_2,\mathrm{♣},1)& \\ (s_A,\mathrm{♯})\mapsto (s_A,\mathrm{♯},0)& (s_R,\mathrm{♯})\mapsto (s_R,\mathrm{♯},0)\end{array}$

$\begin{array}{cccc}& s_0& s_1& s_2\\ {\tau }_{{𝒜}}(1)& s_0& s_1& s_2\\ {\tau }_{{𝒜}}(a)& s_1& s_2& s_2\\ {\tau }_{{𝒜}}(b)& s_0& s_0& s_0\\ {\tau }_{{𝒜}}(a^2)& s_2& s_2& s_2\\ {\tau }_{{𝒜}}(ab)& s_0& s_0& s_2\\ {\tau }_{{𝒜}}(ba)& s_1& s_1& s_1\\ {\tau }_{{𝒜}}(b^2)& s_0& s_0& s_0\\ {\tau }_{{𝒜}}(aba)& 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 ${{𝒜}}^{\prime }=(S^{\prime },A^{\prime },f^{\prime },{s_0}^{\prime },T^{\prime })$ dla ${𝒜}$.
  3  ${\bar{\rho }}_1\leftarrow {\approx }_{{𝒜}}$;
  4  $i\leftarrow 1$;
  5  repeat
  6    Parser nie mógł rozpoznać (nieznana funkcja „\slash”): {\displaystyle \slash \slash}
 oblicz ${\bar{\rho }}_i$: $s_1{\bar{\rho }}_i{s}_2\iff (s_1{\bar{\rho }}_{i-1}{s}_2)\wedge (\mathrm{\forall }a\in Af(s_1,a){\bar{\rho }}_{i-1}f(s_2,a))$;
  7    $i\leftarrow i+1$;
  8    empty$({\bar{\rho }}_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){\bar{\rho }}_{i-1}f(s_2,a)$ then
 13          flag$\leftarrow$false;
 14        end if
 15      end for
 16      if flag=true and $s_1{\bar{\rho }}_{i-1}{s}_2$ then
 17        ${\bar{\rho }}_i\leftarrow {\bar{\rho }}_i\cup \{(s_1,s_2)\}$;
 18      end if
 19    end for
 20  until ${\bar{\rho }}_i={\bar{\rho }}_{i-1}$
 21  Parser nie mógł rozpoznać (nieznana funkcja „\slash”): {\displaystyle S' \leftarrow S \slash \overline{\rho}_i}
;
 22  for each Parser nie mógł rozpoznać (nieznana funkcja „\slash”): {\displaystyle [s]_{\overline{\rho}_i} \in S \slash \overline{\rho}_i}
 do
 23    for each $a\in A$ do
 24      $f^{\prime }([s{]}_{{\bar{\rho }}_i},a)\leftarrow [f(s,a){]}_{{\bar{\rho }}_i}$;
 25    end for
 26  end for
 27  ${s_0}^{\prime }\leftarrow [s_0{]}_{{\bar{\rho }}_i}$;
 28  $T^{\prime }\leftarrow \{[t{]}_{{\bar{\rho }}_i}:t\in T\}$;
 29  return ${{𝒜}}^{\prime }=(S^{\prime },A,f^{\prime },{s_0}^{\prime },T^{\prime })$;

Uzupelnij tytul

	$s_0$ || $s_1$ || $s_2$
${\tau }_{{𝒜}}(1)$ || $s_0$ || $s_1$ || $s_2$
${\tau }_{{𝒜}}(a)$ || $s_1$ || $s_2$ || $s_2$
${\tau }_{{𝒜}}(b)$ || $s_0$ || $s_0$ || $s_0$
${\tau }_{{𝒜}}(a^2)$ || $s_2$ || $s_2$ || $s_2$
${\tau }_{{𝒜}}(ab)$ || $s_0$ || $s_0$ || $s_2$
${\tau }_{{𝒜}}(ba)$ || $s_1$ || $s_1$ || $s_1$
${\tau }_{{𝒜}}(b^2)$ || $s_0$ || $s_0$ || $s_0$
${\tau }_{{𝒜}}(aba)$ || $s_1$ || $s_1$ || $s_2$
... || ... || ... || ...

$\begin{array}{lll}\text{b) }\underset{x\to 2^{+}}{\lim }(x-2)e^{\frac{1}{x-2}}& =& \underset{x\to 2^{+}}{\lim }\frac{e^{\frac{1}{x-2}}}{(x-2{)}^{-1}}\begin{array}{c}\left[\frac{\mathrm{\infty }}{\mathrm{\infty }}\right]\\ =\\ H\end{array}\underset{x\to 2^{+}}{\lim }\frac{-(x-2{)}^{-2}{e}^{\frac{1}{x-2}}}{-(x-2{)}^{-2}}=\\ & =& \underset{x\to 2^{+}}{\lim }{e}^{\frac{1}{x-2}}=+\mathrm{\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\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

$\text{p}$	$\text{q}$	$\text{p}\wedge \text{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

$\text{p}$	$\text{q}$	$\text{r}$	$(\text{p}\wedge \text{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		$\text{p}$
4	0	1	0	0		$\mathrm{\neg }(q\Rightarrow p)$
5	0	1	0	1		$\text{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$

$\text{p}$	$\text{q}$	$\text{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

$\text{p}$	$\text{q}$	$\text{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

$\text{p}$	$\text{q}$	$\text{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$

---

Nagroda Goedla
Zobacz Nagroda Goedla]]

Nagroda Turinga
Zobacz Nagroda Turinga

Nagroda Knutha
Zobacz Nagroda Knutha

$g(C)=\{\begin{array}{l}C\cup \{f(C^{\prime })\}C\end{array}$

Parser nie mógł rozpoznać (błąd składni): {\displaystyle g(C)=\left\{\begin{align} C\cup \{f(C')\}\\C\end{align} \right}

Parser nie mógł rozpoznać (błąd składni): {\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\{\begin{align} \forall c \forall d\; &(c\in C\land d\in C) \implies (c\sqsubseteq d \iff c\sqsubseteq' d) \text{ oraz }\\ \forall c \forall d\; &(c\in C\land d\in C'\setminus C) \implies c\sqsubseteq' d \end{align} \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 \mathbb{\mathbb{N}}$

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