1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
|
\begin{comment}
\begin{code}
{-# LANGUAGE ScopedTypeVariables
#-}
{-|
Description: Deterministic finite state transducers
-}
module Control.DFST
( DFST(..)
, runDFST, runDFST'
, toFST
) where
import Data.Map.Lazy (Map, (!?))
import qualified Data.Map.Lazy as Map
import Data.Set (Set)
import qualified Data.Set as Set
import Data.Sequence (Seq(..))
import qualified Data.Sequence as Seq
import Data.Monoid
import Numeric.Natural
import Control.Monad
import Control.Monad.State
import Control.FST (FST(FST))
import qualified Control.FST as FST
\end{code}
\end{comment}
\begin{defn}[deterministic finite state transducer]
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ände einelementig ist.
Zusätzlich ändern wir die Darstellung indem wir $\epsilon$-Transitionen kontrahieren.
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.
\end{defn}
\begin{code}
data DFST state input output = DFST
{ stInitial :: state
, stTransition :: Map (state, input) (state, Seq output)
, stAccept :: Set state
}
\end{code}
Die in der Definition von DFSTs beschriebene Umwandlung lässt sich umkehren, sich also jeder DFST auch als FST auffassen.
Hierfür trennen wir Transitionen $A \overset{(\sigma, \delta^\ast)}{\rightarrow} B$ mit Eingabe $\sigma$ und Ausgabe-Wort $\delta^\ast = \delta_1 \delta_2 \ldots \delta_n$ in eine Serie von Transitionen $A \overset{(\sigma, \delta_1)}{\rightarrow} A_1 \overset{(\epsilon, \delta_2)}{\rightarrow} \ldots \overset{(\epsilon, \delta_n)}{\rightarrow} B$ auf.
\begin{code}
toFST :: forall state input output. (Ord state, Ord input, Ord output) => DFST state input output -> FST (state, Maybe (input, Natural)) input output
-- ^ View a DFST as a FST splitting apart non-singleton outputs into a series of epsilon-transitions
\end{code}
\begin{comment}
\begin{code}
toFST DFST{..} = flip execState initialFST $ forM_ (Map.toList stTransition) handleTransition
where
initialFST = FST
{ stInitial = Set.singleton (stInitial, Nothing)
, stTransition = Map.empty
, stAccept = Set.map (, Nothing) stAccept
}
addTransition :: forall state input output. (Ord state, Ord input, Ord output) => (state, Maybe input) -> (state, Maybe output) -> State (FST state input output) ()
addTransition k v = modify $ \f@FST{ stTransition } -> f { FST.stTransition = Map.insertWith Set.union k (Set.singleton v) stTransition }
handleTransition :: ((state, input), (state, Seq output)) -> State (FST (state, Maybe (input, Natural)) input output) ()
handleTransition ((st, inS), (st', outs)) = handleTransition' (st, Nothing) (Just inS) outs (st', Nothing)
handleTransition' :: (state, Maybe (input, Natural)) -> Maybe input -> Seq output -> (state, Maybe (input, Natural)) -> State (FST (state, Maybe (input, Natural)) input output) ()
handleTransition' from inS Empty to = addTransition (from, inS) (to, Nothing)
handleTransition' from inS (outS :<| Empty) to = addTransition (from, inS) (to, Just outS)
handleTransition' from@(st, chain) inS (outS :<| oo) to = do
let next
| Just (inS', i) <- chain = (st, Just (inS', succ i))
| Just inS' <- inS = (st, Just (inS', 0 ))
-- Both calls to `handleTransition'` (one in `handleTransition`, the other below) satisfy one of the above cases
addTransition (from, inS) (next, Just outS)
handleTransition' next Nothing oo to
\end{code}
\end{comment}
Das Ausführen eines DFST auf eine gegebene Eingabe ist komplett analog zum Ausführen eines FST.
Unsere Implementierung nutzt die restriktivere Struktur aus unserer Definition von DFSTs um den Determinismus bereits im Typsystem zu kodieren.
\begin{code}
runDFST :: forall state input output. (Ord state, Ord input) => DFST state input output -> Seq input -> Maybe (Seq output)
\end{code}
\begin{comment}
\begin{code}
runDFST dfst@DFST{..} str = do
let (str', finalState') = runDFST' dfst stInitial str Seq.empty
finalState <- finalState'
str' <$ guard (finalState `Set.member` stAccept)
runDFST' :: forall state input output. (Ord state, Ord input)
=> DFST state input output
-> state -- ^ Current state
-> Seq input -- ^ Remaining input
-> Seq output -- ^ Accumulator containing previous output
-> (Seq output, Maybe state) -- ^ Altered output, Next state
runDFST' _ st Empty acc = (acc, Just st)
runDFST' dfst@DFST{..} st (c :<| cs) acc = case stTransition !? (st, c) of
Just (st', mc') -> runDFST' dfst st' cs $ acc <> mc'
Nothing -> (acc, Nothing)
\end{code}
\end{comment}
|
