Deterministic and Nondeterministic Finite State Transducers (FST, NFST) are defined in FST.hs. FST are just an implementation of Finite State Transducers as defined in Homework 1 (problem 2d). Recall the definition if FST as a 5-tuple (Q, Σ , Γ , δ, s) where the transition function has type δ: Q → Σ → Q × Γ * . This translates to the data type
type FST st = ([st], [Char], [Char], st->Char->(st,String), st)We also define a function evalFST that on input an FST T and an input string w, produces the output string fT(w):
evalFST :: FST st -> [Char] -> [Char]
evalFST fst "" = ""
evalFST (qs, sigma, gamma, delta, s) (a:w) =
let (q,u) = delta s a
v = evalFST (qs, sigma, gamma, delta, q) w
in u ++ vHere ++ is the string concatenation operation. For illustration purposes, we have used a different style of definition than the one used for evalDFA, where instead of using an auxiliary function δ * , we make a recursive call to with a different input automaton with modified start state. As an exercise, rewrite the definition of evalFST using standard mathematical notation. (The mathematical definition is almost identical to the code.)
NFST are definied similarly, with the only difference that the transition function may output a set of possible pairs (represented as usual as a list):
type NFST st = ([st], [Char], [Char], st->Char->[(st,[Char])], st)You can read the mathematical definition of NFST, and the proof that they are closed under function composition, from the lecture notes posted on the course webpage. You can think of FST as a special case of NFST that does not use nondeterminism. This formalized by the function
fst2nfst :: FST st -> NFST st
fst2nfst (qs, sigma, gamma, delta, s) =
let delta1 q a =[delta q a]
in (qs, sigma, gamma, delta1, s)Can you follow the code? Can you give the mathematical definition of the transformation corresponding to this program?
In the homework assignment we use NFST to model a noisy communication channel to transmit binary strings, which may occasionally flip the transmitted bits, subject to the constraint that errors are not too frequent: any two errors are at least 3 symbols apart. Notice how nondeterministim can be used to model all possible behaviors of the channel. Your task in the homework is to model the communication channel as an NFST, and design an encoder and decoder programs that can be used to reliably transmit messages over the channel. Write your channel, encoder and decoder programs in JFLAP selecting "Mealy machine" from the main menu. This is the JFLAP type corresponding to (N)FST as used in this course. Make sure that your diagrams match the mathematical definition (and haskell types) we are using, and you don't employ any extra features supported by JFLAP. (E.g., JFLAP may allow for transitions on input ε, which are not allowed by our definition.) Also, make sure that your encoder and decoder diagrams are FST, i.e., they are deterministic.
Once you have designed your encoder, decoder and channel (N)FST, you are asked to combine them using the composition operation defined in the lecture notes lecture notes. As a help, we have also implemented the combination procedure as a haskell function combineNFST that on input two NFSTs, outputs the NFST corresponding to their function composition. This function is used in the program TestEncoder.hs which you may use to test your solution to problem 3.
Load this program, together with the FST.hs and the latest version of JFF.hs. (We have added functions readFST, readNFST and writeNFST to import and export transducers between haskell and jflap.) You may want to look at the TestEncoder.hs program, to see how these functions are used. The test program reads the FSTs and NFST from your files "encode.jff", "channel.jff" and "decode.jff", and combines them using the function composeNFST. The NFST corresponding to the composition of the three functions is written to the file "nfst.jff". If your solution is correct, the resulting nfst should compute the identity function: if a string w is encoded, transmitted (over the noisy channel) and then decoded, the final output should be equal to the original string w. Run the test program on your jflap files, and then open the output file "nfst.jff" in JFLAP. The result is likely to contain a large number of irrelevant states, e.g., states that cannot be reached by the start state of the NFST. You can delete all such useless states without altering the behavior of the automaton. You may still not be able to run the result because JFLAP does not currently support nondeterministic FSTs. But the result should be simple enough that you can check it computes the identity function simply by inspection.
In problem 4, you are asked to define a function composeFST analogous to the composeNFST already defined in FST.hs, but for deterministic transducers. Use the template HW3p4.hs as a starting point, and complete the definition of the function composeFST. (Notice, you need to fill out both the "..." in the return type of the function, and the actual function definition.)
In problem 5, you are asked to prove that the composition of an FST and a DFA, is a DFA. Use the template HW3p5.hs as a starting point, and complete the definition of the function composeFstDfa. (Notice, you need to fill out both the "..." in the return type of the function, and the actual function definition.)