AT&T Labs - Research
AT&T  

Frequently Asked Questions (FAQ)

New users are encouraged to read fsm(1) and fsm(5) first and experiment with some small examples. We list below the answers to common questions/problems users have when first using these tools:

  1. What are the final costs for?

    The final costs are the weighted generalization of final and non-final states. A state's final cost is the cost of exiting the automaton at that state (see fsm(5)). A state is considered final iff its final cost is cheaper than WORSTCOST (see fsmcost(3)), otherwise it is non-final.

  2. Why is there no operation to see if a string represented as FSA1 is accepted by an acceptor FSA2?

    This is equivalent to seeing if their intersection is non-empty.

  3. How can I test if an acceptor/transducer corresponds to the empty language/transduction?

    This is equivalent to checking if the output of fsmconnect has no states. This can be tested using fsmconnect -t, which returns exit status 1 if its output has no states.

  4. Why is there no operation for converting an acceptor into the corresponding transducer (i.e., the identity transducer restricted to the strings in the acceptor)?

    It is not needed; the FSM library automatically intreprets any acceptor argument as the corresponding transducer where appropriate.

  5. Why is there no operation to transduce acceptor FSA by transducer FST?

    This is equivalent to composing FSA with FST and then projecting on to the output side.

  6. I built an acceptor/tranducer, but it does not accept/transduce anything!

    Did you forget to specify the final states?

  7. I can build acceptors fine, but my transducers don't compile correctly!

    Did you forget the ``-t'' flag to fsmcompile, which is needed for transducers?

  8. I can't print out FSMs with their symbolic labels after calling certain operations on them!

    Did you include a symbol for label 0, the epilson label, in your symbols file? Certain operations, such as fsmconcat, fsmunion, and fsmclosure can add epsilons to machines that may not have previously contained them.

  9. My determinization never terminates/runs out of memory!

    Not all FSMs are determinizable; in such cases, determinization will run until resources are exhausted. Sufficient (but not necessary) conditions for an FSM to be determinizable are that it is acyclic or, for acceptors, that it is costless.