Test GR2: Różnice pomiędzy wersjami
m Zastępowanie tekstu - "\aligned" na "\begin{align}" |
m Zastępowanie tekstu - "\begincases" na "\begin{cases}" |
||
| Linia 470: | Linia 470: | ||
<center><math>g(C)=\ | <center><math>g(C)=\begin{cases} C\cup \{f(C')\} C \endcases | ||
</math></center> | </math></center> | ||
Wersja z 22:54, 9 cze 2020
| 0 | 0 | 1 | 1 | |
| 0 | 1 | 0 | 1 | |
| 1 | 0 | 1 | 1 | |
| 1 | 1 | 1 | 1 |
oraz
Ostatecznie, gramatyka w postaci Greibach ma postać:
Algorytm Minimalizuj2 - algorytm minimalizacji automatu wykorzystujący stabilizujący się ciąg relacji
1 Wejście: - automat taki, że .
2 Wyjście: automat minimalny dla .
3 ;
4 ;
5 repeat
6 Parser nie mógł rozpoznać (nieznana funkcja „\slash”): {\displaystyle \displaystyle \slash \slash}
oblicz : ;
7 ;
8 empty
9 for each do
10 flagtrue;
11 for each
12 if not then
13 flagfalse;
14 end if
15 end for
16 if flag=true and then
17 ;
18 end if
19 end for
20 until
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 do
24 ;
25 end for
26 end for
27 ;
28 ;
29 return ;
|
|| || | |
|
|| || || | |
|
|| || || | |
|
|| || || | |
|
|| || || | |
|
|| || || | |
|
|| || || | |
|
|| || || | |
|
|| || || | |
|
... || ... || ... || ... | |
alalalalaa
alala
| Złożoność czasowa | Złożoność pamięciowa | |
|---|---|---|
| Maszyna dodająca | ||
| Maszyna rozpoznająca |
| 0 | 1 | ... | ... | |
|---|---|---|---|---|
| Cell1 | Cell2 |
| 0 | 1 | ||
|---|---|---|---|
| 0 | 1 | 1 | |
| 1 | 0 | 1 |
| 0 | 1 | |
| 1 | 0 |
| 0 | 1 | ||
|---|---|---|---|
| 0 | 0 | 0 | |
| 1 | 0 | 1 |
| 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}} | ||||
|---|---|---|---|---|---|---|
| 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})} | ||||
|---|---|---|---|---|---|---|---|
| 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 |
||||||
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | ||
| 1 | 0 | 0 | 0 | 1 | ||
| 2 | 0 | 0 | 1 | 0 | ||
| 3 | 0 | 0 | 1 | 1 | Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{p}} | |
| 4 | 0 | 1 | 0 | 0 | ||
| 5 | 0 | 1 | 0 | 1 | Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textnormal{q}} | |
| 6 | 0 | 1 | 1 | 0 | ||
| 7 | 0 | 1 | 1 | 1 | ||
| 8 | 1 | 0 | 0 | 0 | ||
| 9 | 1 | 0 | 0 | 1 | ||
| 10 | 1 | 0 | 1 | 0 | ||
| 11 | 1 | 0 | 1 | 1 | ||
| 12 | 1 | 1 | 0 | 0 | ||
| 13 | 1 | 1 | 0 | 1 | ||
| 14 | 1 | 1 | 1 | 0 | ||
| 15 | 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}} | ||||
|---|---|---|---|---|---|---|
| 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}} | |
|---|---|---|---|
| 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}} | |
|---|---|---|---|
| 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 |
Nagroda Goedla
Zobacz Nagroda Goedla]]
Nagroda Turinga
Zobacz Nagroda Turinga
Nagroda Knutha
Zobacz Nagroda Knutha
Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle g(C)=\left\{\begin{align} C\cup \{f(C')\}\\C\end{align} \right}
Parser nie mógł rozpoznać (błąd składni): {\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\{\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}
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 i
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 i