Test GR2: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycjanastępna edycja →
WizualnieWikikod
m Zastępowanie tekstu – „ \displaystyle ” na „”
m Zastępowanie tekstu – „\displaystyle ” na „”
Linia 1: Linia 1:
{| border="1" cellspacing="0"
{| border="1" cellspacing="0"
! <math>\phi</math>!! <math>\psi</math>!! <math>\psi \Rightarrow \phi</math>!! <math>\displaystyle (\phi \Rightarrow (\psi \Rightarrow \phi))</math>!!
! <math>\phi</math>!! <math>\psi</math>!! <math>\psi \Rightarrow \phi</math>!! <math>(\phi \Rightarrow (\psi \Rightarrow \phi))</math>!!
|-
|-
| &nbsp;0&nbsp;|| &nbsp;0&nbsp;|| &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|| &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
| &nbsp;0&nbsp;|| &nbsp;0&nbsp;|| &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|| &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
Linia 18: Linia 18:




<center><math>\displaystyle  w_3 &\rightarrow  bv_3v_2w_3v_1v_3v_3v_2\ |\
<center><math> w_3 &\rightarrow  bv_3v_2w_3v_1v_3v_3v_2\ |\
aw_3v_1v_3v_3v_2\ |\ bv_3v_2v_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
\begin{array}{lll} & & |\ av_1v_3v_3v_2\ |\ bv_3v_3v_2
Linia 25: Linia 25:
oraz
oraz


<center><math>\displaystyle  w_3 &\rightarrow  bv_3v_2w_3v_1v_3v_3v_2w_3\ |\
<center><math> 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 \\
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
\begin{array}{lll} & & |\ av_1v_3v_3v_2w_3\ |\ bv_3v_3v_2w_3
Linia 47: Linia 47:




<center><math>\displaystyle \begin{array} {c|c|c|c|c|} Krok & dodane\quad do\quad S' & okreslenie\quad f' & dodane\quad do\quad T'\\
<center><math>\begin{array} {c|c|c|c|c|} Krok & dodane\quad do\quad S' & okreslenie\quad f' & dodane\quad do\quad T'\\
\hline 0 & \{q_0\} &  & \emptyset\\
\hline 0 & \{q_0\} &  & \emptyset\\
\hline 1 & \{q_0,q_3\} & f'(\{q_0\},a)=\{q_0,q_3\} & \emptyset\\
\hline 1 & \{q_0,q_3\} & f'(\{q_0\},a)=\{q_0,q_3\} & \emptyset\\
Linia 72: Linia 72:




<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)\\
<center><math>\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 (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 (r_0',\sharp)\mapsto (q_0,\sharp,-1) & (r_0',0)\mapsto (r_0',0,1) & (r_0',1)\mapsto (r_0',1,1)\\
Linia 90: Linia 90:




<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)\\
<center><math>\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)\\
\hline (s_0,0)\mapsto(s_1,\clubsuit,1) & (s_1,0) \mapsto(s_2,\diamondsuit,1)\\
\hline  & (s_1,\sharp)\mapsto(s_A,\sharp,0)\\
\hline  & (s_1,\sharp)\mapsto(s_A,\sharp,0)\\
Linia 109: Linia 109:




<center><math>\displaystyle \begin{array} {c|c|c|c|c|}  & s_0 & s_1 & s_2\\
<center><math>\begin{array} {c|c|c|c|c|}  & s_0 & s_1 & s_2\\
\hline \tau _{\mathcal{A}}(1) & s_0 & s_1 & s_2\\
\hline \tau _{\mathcal{A}}(1) & s_0 & s_1 & s_2\\
\hline \tau _{\mathcal{A}}(a) & s_1 & s_2 & s_2\\
\hline \tau _{\mathcal{A}}(a) & s_1 & s_2 & s_2\\
Linia 122: Linia 122:




<center><math>\displaystyle \begin{array} {c|c|c|c|c|} f & s_0 & s_1 & s_2 & s_3\\
<center><math>\begin{array} {c|c|c|c|c|} f & s_0 & s_1 & s_2 & s_3\\
\hline a & s_1 & s_2 & s_0 & s_2\\
\hline a & s_1 & s_2 & s_0 & s_2\\
\hline b & s_3 & s_2 & s_2 & s_2\\
\hline b & s_3 & s_2 & s_2 & s_2\\
Linia 131: Linia 131:
wykorzystujący stabilizujący się ciąg relacji|algorytm minimalizacji automatu wykorzystujący stabilizujący się ciąg relacji|
wykorzystujący stabilizujący się ciąg relacji|algorytm minimalizacji automatu wykorzystujący stabilizujący się ciąg relacji|


   1  Wejście: <math>\displaystyle \mathcal{A}=(S, A, f, s_0, T)</math> - automat taki, że <math>\displaystyle L=L(\mathcal{A})</math>.
   1  Wejście: <math>\mathcal{A}=(S, A, f, s_0, T)</math> - automat taki, że <math>L=L(\mathcal{A})</math>.
   2  Wyjście: automat minimalny <math>\displaystyle \mathcal{A}'=(S',A',f', s_0',
   2  Wyjście: automat minimalny <math>\mathcal{A}'=(S',A',f', s_0',
T')</math> dla <math>\displaystyle \mathcal{A}</math>.
T')</math> dla <math>\mathcal{A}</math>.
   3  <math>\displaystyle \overline{\rho}_1\displaystyle \leftarrow\displaystyle \approx_{\mathcal{A}}</math>;
   3  <math>\overline{\rho}_1\leftarrow\approx_{\mathcal{A}}</math>;
   4  <math>\displaystyle i \leftarrow 1</math>;
   4  <math>i \leftarrow 1</math>;
   5  '''repeat'''
   5  '''repeat'''
   6    <math>\displaystyle \slash \slash</math> oblicz <math>\displaystyle \overline{\rho}_i</math>: <math>\displaystyle s_1  
   6    <math>\slash \slash</math> oblicz <math>\overline{\rho}_i</math>: <math>s_1  
\overline{\rho}_i s_2 \Leftrightarrow (s_1 \overline{\rho}_{i-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}  
s_2) \wedge (\forall a \in A\ f(s_1, a) \overline{\rho}_{i-1}  
f(s_2,a))</math>;
f(s_2,a))</math>;
   7    <math>\displaystyle i \leftarrow i+1</math>;
   7    <math>i \leftarrow i+1</math>;
   8    '''empty'''<math>\displaystyle (\overline{\rho}_i)</math>  
   8    '''empty'''<math>(\overline{\rho}_i)</math>  
   9    '''for''' '''each''' <math>\displaystyle (s_1,s_2)\in S\times S</math> '''do'''
   9    '''for''' '''each''' <math>(s_1,s_2)\in S\times S</math> '''do'''
   10      flag<math>\displaystyle \leftarrow</math>'''true''';
   10      flag<math>\leftarrow</math>'''true''';
   11      '''for''' '''each''' <math>\displaystyle a\in A</math>  
   11      '''for''' '''each''' <math>a\in A</math>  
   12        '''if''' '''not''' <math>\displaystyle f(s_1, a) \overline{\rho}_{i-1} f(s_2,a)</math> '''then'''
   12        '''if''' '''not''' <math>f(s_1, a) \overline{\rho}_{i-1} f(s_2,a)</math> '''then'''
   13          flag<math>\displaystyle \leftarrow</math>'''false''';
   13          flag<math>\leftarrow</math>'''false''';
   14        '''end''' '''if'''
   14        '''end''' '''if'''
   15      '''end''' '''for'''
   15      '''end''' '''for'''
   16      '''if''' flag<nowiki>=</nowiki>'''true''' '''and''' <math>\displaystyle s_1 \overline{\rho}_{i-1} s_2</math> '''then'''
   16      '''if''' flag<nowiki>=</nowiki>'''true''' '''and''' <math>s_1 \overline{\rho}_{i-1} s_2</math> '''then'''
   17        <math>\displaystyle \overline{\rho}_{i} \leftarrow \overline{\rho}_{i} \cup \{(s_1,s_2)\}</math>;
   17        <math>\overline{\rho}_{i} \leftarrow \overline{\rho}_{i} \cup \{(s_1,s_2)\}</math>;
   18      '''end''' '''if'''
   18      '''end''' '''if'''
   19    '''end''' '''for'''
   19    '''end''' '''for'''
   20  '''until''' <math>\displaystyle \overline{\rho}_i = \overline{\rho}_{i-1}</math>
   20  '''until''' <math>\overline{\rho}_i = \overline{\rho}_{i-1}</math>
   21  <math>\displaystyle S' \leftarrow S \slash \overline{\rho}_i</math>;
   21  <math>S' \leftarrow S \slash \overline{\rho}_i</math>;
   22  '''for''' '''each''' <math>\displaystyle [s]_{\overline{\rho}_i} \in S \slash \overline{\rho}_i</math> '''do'''
   22  '''for''' '''each''' <math>[s]_{\overline{\rho}_i} \in S \slash \overline{\rho}_i</math> '''do'''
   23    '''for''' '''each''' <math>\displaystyle a \in A</math> '''do'''
   23    '''for''' '''each''' <math>a \in A</math> '''do'''
   24      <math>\displaystyle f'([s]_{\overline{\rho}_i},a) \leftarrow
   24      <math>f'([s]_{\overline{\rho}_i},a) \leftarrow
[f(s,a)]_{\overline{\rho}_i}</math>;
[f(s,a)]_{\overline{\rho}_i}</math>;
   25    '''end''' '''for'''
   25    '''end''' '''for'''
   26  '''end''' '''for'''
   26  '''end''' '''for'''
   27  <math>\displaystyle s_0' \leftarrow [s_0]_{\overline{\rho}_i}</math>;
   27  <math>s_0' \leftarrow [s_0]_{\overline{\rho}_i}</math>;
   28  <math>\displaystyle T' \leftarrow \{[t]_{\overline{\rho}_i}:\ t \in T\}</math>;
   28  <math>T' \leftarrow \{[t]_{\overline{\rho}_i}:\ t \in T\}</math>;
   29  '''return''' <math>\displaystyle \mathcal{A}'=(S', A, f', s_0', T')</math>;
   29  '''return''' <math>\mathcal{A}'=(S', A, f', s_0', T')</math>;


}}
}}
Linia 175: Linia 175:
|  
|  
||  
||  
<math>\displaystyle s_{0}  </math>  ||  
<math>s_{0}  </math>  ||  
<math>\displaystyle s_{1}  </math>  ||  
<math>s_{1}  </math>  ||  
<math>\displaystyle s_{2}  </math>  
<math>s_{2}  </math>  
|-
|-
|  
|  


<math>\displaystyle \tau _{\mathcal{A}}(1)  </math>  ||  
<math>\tau _{\mathcal{A}}(1)  </math>  ||  
<math>\displaystyle s_{0}  </math>  ||  
<math>s_{0}  </math>  ||  
<math>\displaystyle s_{1}  </math>  ||  
<math>s_{1}  </math>  ||  
<math>\displaystyle s_{2}  </math>  
<math>s_{2}  </math>  
|-
|-
|  
|  
<math>\displaystyle \tau _{\mathcal{A}}(a)  </math>  ||  
<math>\tau _{\mathcal{A}}(a)  </math>  ||  
<math>\displaystyle s_{1}  </math>  ||  
<math>s_{1}  </math>  ||  
<math>\displaystyle s_{2}  </math>  ||  
<math>s_{2}  </math>  ||  
<math>\displaystyle s_{2}  </math>  
<math>s_{2}  </math>  
|-
|-
|  
|  
<math>\displaystyle \tau _{\mathcal{A}}(b)  </math>  ||  
<math>\tau _{\mathcal{A}}(b)  </math>  ||  
<math>\displaystyle s_{0}  </math>  ||  
<math>s_{0}  </math>  ||  
<math>\displaystyle s_{0}  </math>  ||  
<math>s_{0}  </math>  ||  
<math>\displaystyle s_{0}  </math>  
<math>s_{0}  </math>  
|-
|-
|  
|  
<math>\displaystyle \tau _{\mathcal{A}}(a^{2})  </math>  ||  
<math>\tau _{\mathcal{A}}(a^{2})  </math>  ||  
<math>\displaystyle s_{2}  </math>  ||  
<math>s_{2}  </math>  ||  
<math>\displaystyle s_{2}  </math>  ||  
<math>s_{2}  </math>  ||  
<math>\displaystyle s_{2}  </math>  
<math>s_{2}  </math>  
|-
|-
|  
|  
<math>\displaystyle \tau _{\mathcal{A}}(ab)  </math>  ||  
<math>\tau _{\mathcal{A}}(ab)  </math>  ||  
<math>\displaystyle s_{0}  </math>  ||  
<math>s_{0}  </math>  ||  
<math>\displaystyle s_{0}  </math>  ||  
<math>s_{0}  </math>  ||  
<math>\displaystyle s_{2}  </math>  
<math>s_{2}  </math>  
|-
|-
|  
|  
<math>\displaystyle \tau _{\mathcal{A}}(ba)  </math>  ||  
<math>\tau _{\mathcal{A}}(ba)  </math>  ||  
<math>\displaystyle s_{1}  </math>  ||  
<math>s_{1}  </math>  ||  
<math>\displaystyle s_{1}  </math>  ||  
<math>s_{1}  </math>  ||  
<math>\displaystyle s_{1}  </math>   
<math>s_{1}  </math>   
|-
|-
|  
|  
<math>\displaystyle \tau _{\mathcal{A}}(b^{2})  </math>  ||  
<math>\tau _{\mathcal{A}}(b^{2})  </math>  ||  
<math>\displaystyle s_{0}  </math>  ||  
<math>s_{0}  </math>  ||  
<math>\displaystyle s_{0}  </math>  ||  
<math>s_{0}  </math>  ||  
<math>\displaystyle s_{0}  </math>  
<math>s_{0}  </math>  
|-
|-
|  
|  
<math>\displaystyle \tau _{\mathcal{A}}(aba)  </math>  ||  
<math>\tau _{\mathcal{A}}(aba)  </math>  ||  
<math>\displaystyle s_{1}  </math>  ||  
<math>s_{1}  </math>  ||  
<math>\displaystyle s_{1}  </math>  ||  
<math>s_{1}  </math>  ||  
<math>\displaystyle s_{2}  </math>  
<math>s_{2}  </math>  
|-
|-
|  
|  
Linia 241: Linia 241:
<math>  
<math>  
\begin{array}{lll}
\begin{array}{lll}
\displaystyle \text{b) } \lim_{x\rightarrow 2^+} (x-2)e^{\frac{1}{x-2}}&=&\lim_{x\rightarrow
\text{b) } \lim_{x\rightarrow 2^+} (x-2)e^{\frac{1}{x-2}}&=&\lim_{x\rightarrow
2^+} \frac{e^{\frac{1}{x-2}}}{(x-2)^{-1}}\begin{array} {c}\left[\frac{\infty}{\infty}\right]\\=\\H\end{array}  
2^+} \frac{e^{\frac{1}{x-2}}}{(x-2)^{-1}}\begin{array} {c}\left[\frac{\infty}{\infty}\right]\\=\\H\end{array}  
\lim_{x\rightarrow 2^+}
\lim_{x\rightarrow 2^+}

Wersja z 08:57, 28 sie 2023

ϕ ψ ψ⇒ϕ (ϕ⇒(ψ⇒ϕ))
 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}}



KrokdodanedoS′okreslenief′dodanedoT′0{q0}∅1{q0,q3}f′({q0},a)={q0,q3}∅{q0,q1}f′({q0},b)={q0,q1}2{q0,q3,q4}f′({q0,q3},a)={q0,q3,q4}{q0,q3,q4}f′({q0,q3},b)={q0,q1}f′({q0,q1},a)={q0,q3}{q0,q1,q2}f′({q0,q1},b)={q0,q1,q2}{q0,q1,q2}3f′({q0,q3,q4},a)={q0,q3,q4}{q0,q1,q4}f′({q0,q3,q4},b)={q0,q1,q4}{q0,q1,q4}{q0,q2,q3}f′({q0,q1,q2},a)={q0,q2,q3}{q0,q2,q3}f′({q0,q1,q2},b)={q0,q1,q2}4f′({q0,q1,q4},a)={q0,q3,q4}{q0,q1,q2,q4},f′({q0,q1,q4},b)={q0,q1,q2,q4}{q0,q1,q2,q4}{q0,q2,q3,q4}f′({q0,q2,q3},a)={q0,q2,q3,q4}{q0,q2,q3,q4}f′({q0,q2,q3},b)={q0,q1,q2}5f′({q0,q1,q2,q4},a)={q0,q2,q3,q4}f′({q0,q1,q2,q4},b)={q0,q1,q2,q4}f′({q0,q2,q3,q4},a)={q0,q2,q3,q4}f′({q0,q2,q3,q4},b)={q0,q1,q2,q4}



(s0,♯)↦(sA,♯,0)(s0,0)↦(r0,♯,1)(s0,1)↦(r1,♯,1)(r0,♯)↦(sR,♯,0)(r0,0)↦(r0′,0,1)(r0,1)↦(r0′,1,1)(r0′,♯)↦(q0,♯,−1)(r0′,0)↦(r0′,0,1)(r0′,1)↦(r0′,1,1)(q0,0)↦(l,♯,−1)(q0,1)↦(sR,♯,−1)(r1,♯)↦(sR,♯,0)(r1,0)↦(r1′,0,1)(r1,1)↦(r1′,1,1)(r1′,♯)↦(q1,♯,−1)(r1′,0)↦(r1′,0,1)(r1′,1)↦(r1′,1,1)(q1,0)↦(sR,♯,0)(q1,1)↦(l,♯,−1)(l,♯)↦(s0,♯,1)(l,0)↦(l,0,−1)(l,1)↦(l,1,−1)(sR,♯)↦(sR,♯,0)(sA,♯)↦(sA,♯,0)




(s0,♯)↦(sR,♯,0)(s1,♢)↦(s1,♢,1)(s0,0)↦(s1,♣,1)(s1,0)↦(s2,♢,1)(s1,♯)↦(sA,♯,0)(s2,♢)↦(s2,♢,1)(s3,0)↦(s2,♢,1)(s2,♯)↦(s4,♯,−1)(s3,♢)↦(s3,♢,1)(s2,0)↦(s3,0,1)(s3,♯)↦(sR,♯,0)(s4,0)↦(s4,0,−1)(s4,♢)↦(s4,♢,−1)(s4,♣)↦(s2,♣,1)(sA,♯)↦(sA,♯,0)(sR,♯)↦(sR,♯,0)





s0s1s2τ𝒜(1)s0s1s2τ𝒜(a)s1s2s2τ𝒜(b)s0s0s0τ𝒜(a2)s2s2s2τ𝒜(ab)s0s0s2τ𝒜(ba)s1s1s1τ𝒜(b2)s0s0s0τ𝒜(aba)s1s1s2............


fs0s1s2s3as1s2s0s2bs3s2s2s2


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


  1  Wejście: 𝒜=(S,A,f,s0,T) - automat taki, że L=L(𝒜).
  2  Wyjście: automat minimalny 𝒜′=(S′,A′,f′,s0′,T′) dla 𝒜.
  3  ρ‾1←≈𝒜;
  4  i←1;
  5  repeat
  6    Parser nie mógł rozpoznać (nieznana funkcja „\slash”): {\displaystyle \slash \slash}
 oblicz ρ‾i: s1ρ‾is2⇔(s1ρ‾i−1s2)∧(∀a∈A f(s1,a)ρ‾i−1f(s2,a));
  7    i←i+1;
  8    empty(ρ‾i) 
  9    for each (s1,s2)∈S×S do
 10      flag←true;
 11      for each a∈A 
 12        if not f(s1,a)ρ‾i−1f(s2,a) then
 13          flag←false;
 14        end if
 15      end for
 16      if flag=true and s1ρ‾i−1s2 then
 17        ρ‾i←ρ‾i∪{(s1,s2)};
 18      end if
 19    end for
 20  until ρ‾i=ρ‾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∈A do
 24      f′([s]ρ‾i,a)←[f(s,a)]ρ‾i;
 25    end for
 26  end for
 27  s0′←[s0]ρ‾i;
 28  T′←{[t]ρ‾i: t∈T};
 29  return 𝒜′=(S′,A,f′,s0′,T′);



Uzupelnij tytul

s0 || s1 || s2

τ𝒜(1) || s0 || s1 || s2

τ𝒜(a) || s1 || s2 || s2

τ𝒜(b) || s0 || s0 || s0

τ𝒜(a2) || s2 || s2 || s2

τ𝒜(ab) || s0 || s0 || s2

τ𝒜(ba) || s1 || s1 || s1

τ𝒜(b2) || s0 || s0 || s0

τ𝒜(aba) || s1 || s1 || s2

... || ... || ... || ...


b) limx→2+(x−2)e1x−2=limx→2+e1x−2(x−2)−1[∞∞]=Hlimx→2+−(x−2)−2e1x−2−(x−2)−2==limx→2+e1x−2=+∞;


 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≥2		 f(0)=2
f(1)=3
f(n)=n+1;n≥2
Maszyna rozpoznająca ww← f(n)=6+8+…+(n+3)+2;n=2k+1
f(n)=5+7+…+(n+3)+1;n=2k		 f(n)=n+1


⇒ 0 1 ... ...
Cell1 Cell2


⇒ 0 1
 0   1   1 
 1   0   1 


p ¬p
 0   1 
 1   0 


∧ 0 1
 0   0   0 
 1   0   1 
∨ 0 1
 0   0   1 
 1   1   1 
p q p∧q ¬(p∧q) ¬p ¬q ¬p∨¬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


p q r (p∧q) (p∧r) (q∧¬r) (p∧r)∨(q∧¬r) (p∧q)⇒((p∧r)∨(q∧¬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   ∧
2 0 0 1 0   ¬(p⇒q)
3 0 0 1 1   p
4 0 1 0 0   ¬(q⇒p)
5 0 1 0 1   q
6 0 1 1 0   XOR
7 0 1 1 1   ∨
8 1 0 0 0   NOR
9 1 0 0 1   ⇔
10 1 0 1 0   ¬q
11 1 0 1 1   q⇒p
12 1 1 0 0   ¬p
13 1 1 0 1   p⇒q
14 1 1 1 0   NAND
15 1 1 1 1   T


p q r (p↔q) (p↔q)↔r (q↔r) p↔(q↔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


p q r ∘(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


p q r fp→(q→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


⇒ 0 1 2
 0   2   2   2 
 1   0   2   2 
 2   0   1   2 

σ^(f(t0,..,tn))=I(f)(σ^(t0),..,σ^(tn))


X*={1}∪X∪X2∪...∪Xn∪…=⋃i=0∞Xi





Nagroda Goedla
Zobacz Nagroda Goedla]]

Nagroda Turinga
Zobacz Nagroda Turinga

Nagroda Knutha
Zobacz Nagroda Knutha


g(C)={C∪{f(C′)}C


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∈A i 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∈A i n∈m

Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Test_GR2&oldid=79865”