diff options
author | Gregor Kleen <gkleen@yggdrasil.li> | 2019-06-07 09:08:42 +0200 |
---|---|---|
committer | Gregor Kleen <gkleen@yggdrasil.li> | 2019-06-07 09:08:42 +0200 |
commit | a29cce747f3717e32231c9a92b40be12832037b6 (patch) | |
tree | 70f399682dec8657719eae4358e87cdc24bbf42f /edit-lens/src/Control/DFST.lhs | |
parent | 9a02751c1e588a5bbb83bb7e543c26486d3079d5 (diff) | |
download | incremental-dfsts-a29cce747f3717e32231c9a92b40be12832037b6.tar incremental-dfsts-a29cce747f3717e32231c9a92b40be12832037b6.tar.gz incremental-dfsts-a29cce747f3717e32231c9a92b40be12832037b6.tar.bz2 incremental-dfsts-a29cce747f3717e32231c9a92b40be12832037b6.tar.xz incremental-dfsts-a29cce747f3717e32231c9a92b40be12832037b6.zip |
Finish for submission
Diffstat (limited to 'edit-lens/src/Control/DFST.lhs')
-rw-r--r-- | edit-lens/src/Control/DFST.lhs | 4 |
1 files changed, 2 insertions, 2 deletions
diff --git a/edit-lens/src/Control/DFST.lhs b/edit-lens/src/Control/DFST.lhs index eb838ae..48feaf9 100644 --- a/edit-lens/src/Control/DFST.lhs +++ b/edit-lens/src/Control/DFST.lhs | |||
@@ -41,7 +41,7 @@ import Text.Dot | |||
41 | \begin{defn}[deterministic finite state transducer] | 41 | \begin{defn}[deterministic finite state transducer] |
42 | Wir nennen einen FST \emph{deterministic}, wenn jedes Paar aus Ausgabezustand und Eingabesymbol maximal eine Transition zulässt, $\epsilon$-Transitionen keine Schleifen bilden und die Menge von initialen Zuständen einelementig ist. | 42 | Wir nennen einen FST \emph{deterministic}, wenn jedes Paar aus Ausgabezustand und Eingabesymbol maximal eine Transition zulässt, $\epsilon$-Transitionen keine Schleifen bilden und die Menge von initialen Zuständen einelementig ist. |
43 | 43 | ||
44 | Zusätzlich ändern wir die Darstellung indem wir $\epsilon$-Transitionen kontrahieren. | 44 | Zusätzlich ändern wir die Darstellung, indem wir $\epsilon$-Transitionen kontrahieren. |
45 | Wir erweitern hierfür die Ausgabe pro Transition von einem einzelnen Zeichen zu einem Wort beliebiger Länge und fügen, bei jeder Kontraktion einer $\epsilon$-Transition $A \rightarrow B$, die Ausgabe der Transition vorne an die Ausgabe aller Transitionen $B \rightarrow \ast$ von $B$ an. | 45 | Wir erweitern hierfür die Ausgabe pro Transition von einem einzelnen Zeichen zu einem Wort beliebiger Länge und fügen, bei jeder Kontraktion einer $\epsilon$-Transition $A \rightarrow B$, die Ausgabe der Transition vorne an die Ausgabe aller Transitionen $B \rightarrow \ast$ von $B$ an. |
46 | \end{defn} | 46 | \end{defn} |
47 | 47 | ||
@@ -92,7 +92,7 @@ toFST DFST{..} = flip execState initialFST $ forM_ (Map.toList stTransition) han | |||
92 | \end{comment} | 92 | \end{comment} |
93 | 93 | ||
94 | Das Ausführen eines DFST auf eine gegebene Eingabe ist komplett analog zum Ausführen eines FST. | 94 | Das Ausführen eines DFST auf eine gegebene Eingabe ist komplett analog zum Ausführen eines FST. |
95 | Unsere Implementierung nutzt die restriktivere Struktur aus unserer Definition von DFSTs um den Determinismus bereits im Typsystem zu kodieren. | 95 | Unsere Implementierung nutzt die restriktivere Struktur aus unserer Definition von DFSTs, um den Determinismus bereits im Typsystem zu kodieren. |
96 | 96 | ||
97 | \begin{code} | 97 | \begin{code} |
98 | runDFST :: forall state input output. (Ord state, Ord input) => DFST state input output -> Seq input -> Maybe (Seq output) | 98 | runDFST :: forall state input output. (Ord state, Ord input) => DFST state input output -> Seq input -> Maybe (Seq output) |