fsm
index
/home/riley/src/cmd/misc/fsmpython/fsm.py

This module provides access to the AT&T FSM Library. It
defines a Python type, FsmType, that represents weighted finite-state
machines. Two types of machines are supported: ACCEPTORS and TRANSDUCERS.  
Each state of an FSM is indexed by an integer (as in fsm(3)). Each arc 
is represented as a tuple '(ilabel, olabel, cost, nextstate)'. There 
are FSM operations that read, write, combine, minimize, and search
weighted finite-state machines (FSMs).  In general, operations that
return FSMs are defined as functions, while the other FSM operations
are methods defined for the Fsm type.  Most FSM functions can operate
in three different modes - CONSTRUCTIVE, DESTRUCTIVE, and DELAYED,
specified by the optional argument MODE with argument values of
'n[orm]' (default), 'des[truct]', and 'del[ay]', respectively (the
text in square brackets is optional). See fsm(3) for an explanation of
the mode argument. Also see fsm(3) for a fuller description of the
functions and methods below. All fsm(3), fsmaccess(3), and fsmclass(3)
functions are available from Python.  Since it is possible to build
ill-formed FSMs with fsmaccess(3) operations, it is recommended that
you use verify() to check newly constructed/modified FSMs before
applying the fsm(3) operations since, for efficiency, the latter do
not check their inputs for correctness and could result in fatal
errors on ill-formed input.

 
Classes
            
__builtin__.object
FSMArcsIter
FSMStatesIter
Fsm
 
FSMArcsIterType = class FSMArcsIter(__builtin__.object)
      An FSMArcsIter is an iterator over an FSM state.
 
Methods:
 
next() -> arc
Return next FSM arc. Terminated with 'noarc'.
 
reset() -> None
Reset iterator to initial condition.
 
seekpos(n) -> int
Position iterator at N-th arc.
 
seekeps() -> int
Position iterator at first epsilon arc.
 
seeknoneps() -> int
Position iterator at first non-epsilon arc.
 
seeklabel(lab) -> int
Position iterator at first arc matching label LAB.
 
   Methods defined here:
__iter__(...)
x.__iter__() <==> iter(x)
next(...)
x.next() -> the next value, or raise StopIteration

Data and non-method functions defined here:
__doc__ = 'An FSMArcsIter is an iterator over an FSM state....osition iterator at first arc matching label LAB.'
str(object) -> string
 
Return a nice string representation of the object.
If the argument is a string, the return value is the same object.

Methods inherited from __builtin__.object:
__delattr__(...)
x.__delattr__('name') <==> del x.name
__getattribute__(...)
x.__getattribute__('name') <==> x.name
__hash__(...)
x.__hash__() <==> hash(x)
__init__(...)
x.__init__(...) initializes x; see x.__class__.__doc__ for signature
__reduce__(...)
helper for pickle
__repr__(...)
x.__repr__() <==> repr(x)
__setattr__(...)
x.__setattr__('name', value) <==> x.name = value
__str__(...)
x.__str__() <==> str(x)

Data and non-method functions inherited from __builtin__.object:
__class__ = <type 'type'>
the object's class
__new__ = <built-in method __new__ of type object>
T.__new__(S, ...) -> a new object with type S, a subtype of T
 
FSMStatesIterType = class FSMStatesIter(__builtin__.object)
      An FSMStatesIter is an iterator over an Fsm.
 
Methods:
 
next() -> int
Return next FSM state ID. Terminated with 'nostate'.
 
   Methods defined here:
__iter__(...)
x.__iter__() <==> iter(x)
next(...)
x.next() -> the next value, or raise StopIteration

Data and non-method functions defined here:
__doc__ = "An FSMStatesIter is an iterator over an Fsm.\n\nMe...urn next FSM state ID. Terminated with 'nostate'."
str(object) -> string
 
Return a nice string representation of the object.
If the argument is a string, the return value is the same object.

Methods inherited from __builtin__.object:
__delattr__(...)
x.__delattr__('name') <==> del x.name
__getattribute__(...)
x.__getattribute__('name') <==> x.name
__hash__(...)
x.__hash__() <==> hash(x)
__init__(...)
x.__init__(...) initializes x; see x.__class__.__doc__ for signature
__reduce__(...)
helper for pickle
__repr__(...)
x.__repr__() <==> repr(x)
__setattr__(...)
x.__setattr__('name', value) <==> x.name = value
__str__(...)
x.__str__() <==> str(x)

Data and non-method functions inherited from __builtin__.object:
__class__ = <type 'type'>
the object's class
__new__ = <built-in method __new__ of type object>
T.__new__(S, ...) -> a new object with type S, a subtype of T
 
FsmType = class Fsm(__builtin__.object)
      An Fsm represents a weighted finite-state machine.
 
Methods:
 
type() -> string
Return FSM type.
 
semiring() -> string
Return FSM semiring.
 
numstates() -> int
Return number of states.
 
start()-> int
Return start state.
 
final(state) -> float
Return final cost of STATE.
 
potential(state) -> float
Return potential of STATE.
 
numarcs(state) -> int
Return number of arcs leaving STATE.
 
numinputeps(state) -> int
Return number of input epsilons leaving STATE.
 
numoutputeps(state) -> int
Return number of output epsilons leaving STATE.
 
statesopen() -> iterator
Return an FSM states iterator.
 
arcs(state) -> arcslist
Return arcs leaving STATE.
 
arcsopen(state) -> iterator
Return an FSM arcss iterator for STATE.
 
props() -> (haveprops, specprops)
Return FSM property flags.
 
settype(type) -> None
Set FSM type.
TYPE is a string, one of: 'a[ccep]' or 't[rans]'.
 
setsemiring(type) -> None
Set FSM semiring.
Available semirings: 'boolean', 'log', 'real', 'trivial', and 'tropical'.
 
setstart(state)-> None
Set start state to STATE.
 
setfinal(state, cost) -> None
Set final cost of STATE to COST.
 
setpotential(state, cost) -> None
Set potential of STATE to COST.
 
addstates(n) -> None
Add n states.
 
deletestates(stateslist) -> None
Delete states in STATESLIST.
 
setarcs(state, arcslist) -> None
Set arcs for STATE to ARCSLIST
 
addarcs(state, arcslist) -> None
Add arcs in ARCSLIST to STATE
 
setprops(haveprops, specprops)
Set FSM property FLAGS.
Permitted HAVEPROPS and SETPROPS are (a disjunction of) 'prop_*' data
variables defined in the enviroment (see help(fsm)).
 
dump(filename) -> None
Dump to a file.
 
write(fileobject) -> None
Write to an open file object.
 
test(props) -> haveprops
Test for various properties.
Permitted PROPS are (a disjunction of) 'prop_*' data variables
defined in the enviroment (see help(fsm)).
 
verify() -> None
Verifies well-formed FSM.
 
   Methods defined here:
__iter__(...)
x.__iter__() <==> iter(x)

Data and non-method functions defined here:
__doc__ = 'An Fsm represents a weighted finite-state machin...sm)).\n\nverify() -> None\nVerifies well-formed FSM.'
str(object) -> string
 
Return a nice string representation of the object.
If the argument is a string, the return value is the same object.

Methods inherited from __builtin__.object:
__delattr__(...)
x.__delattr__('name') <==> del x.name
__getattribute__(...)
x.__getattribute__('name') <==> x.name
__hash__(...)
x.__hash__() <==> hash(x)
__init__(...)
x.__init__(...) initializes x; see x.__class__.__doc__ for signature
__reduce__(...)
helper for pickle
__repr__(...)
x.__repr__() <==> repr(x)
__setattr__(...)
x.__setattr__('name', value) <==> x.name = value
__str__(...)
x.__str__() <==> str(x)

Data and non-method functions inherited from __builtin__.object:
__class__ = <type 'type'>
the object's class
__new__ = <built-in method __new__ of type object>
T.__new__(S, ...) -> a new object with type S, a subtype of T
 
Functions
            
arcsort(...)
arcsort(fsm[, compar[, mode]]) -> fsm
 
Sort transitions leaving a state according to COMPAR type.
COMPAR is a string, one of: 'i[label]' (default), 'o[label]', or 'c[ost]'.
arcsum(...)
arcsum(fsm[, mode]) -> fsm
 
Combine same-labeled arcs between the same source and destination
states.
arith(...)
arith(fsm, flags[, mult[, add[, state[, lab[, mode]]]]]) -> fsm
 
Perform arithmetic operations on an FSM's costs.
Permitted FLAGS are (a disjunction of) 'arith_*' data variables
defined in the enviroment (see help(fsm)).
bestpath(...)
bestpath(fsm[, nbest[, cthresh[, nthresh[, uniq[, qtype]]]]]) -> fsm
 
Find nbest (default: 1) lowest cost paths through an FSM.
cache(...)
cache(fsm, [class[, size]]) -> fsm
 
Cache the expansion of FSM in an FSMClass CLASS
cache Fsm (default 'basic').
closure(...)
closure(fsm[, pos[, mode]]) -> fsm
 
Kleene closure of FSM.
compose(...)
compose(fsm1, fsm2[, mode[, filter]]]) -> fsm
 
Compose two FSMs.
concat(...)
concat(fsm1, fsm2[, mode]) -> fsm
 
Concatenate two FSMs.
connect(...)
connect(fsm[, mode]) -> fsm
 
Keep only accessable and co-accessiable states.
convert(...)
convert(fsm[, class[, smr]]) -> fsm
 
Convert an FSM to FSMClass CLASS and semiring SMR.
 
Available classes:  'basic' (default), 'const', 'const_indexed',
'const_input_indexed', 'const_output_indexed', 'epsilon', 'fsm1',
'grouped', 'indexed', 'input_epsilon', 'input_grouped',
'input_indexed', 'output_epsilon', 'output_grouped',
'output_indexed', and 'prune'.
 
Available semirings: 'boolean', 'log', 'real', 'trivial',
and 'tropical' (default).
copy(...)
copy(fsm[, class]) -> fsm
 
Copy an FSM as FSMClass CLASS.
 
Available classes:  'basic' (default), 'const', 'const_indexed',
'const_input_indexed', 'const_output_indexed', 'epsilon', 'fsm1',
'grouped', 'indexed', 'input_epsilon', 'input_grouped',
'input_indexed', 'output_epsilon', 'output_grouped',
'output_indexed', and 'prune'.
create(...)
create(type, [class[, smr]]) -> fsm
 
Create an empty FSM of type TYPE, class CLASS and semiring SMR.
 
TYPE is a string, one of: 'a[ccep]' or 't[rans]'.
 
Available classes:  'basic' (default), 'const', 'const_indexed',
'const_input_indexed', 'const_output_indexed', 'epsilon', 'fsm1',
'grouped', 'indexed', 'input_epsilon', 'input_grouped',
'input_indexed', 'output_epsilon', 'output_grouped',
'output_indexed', and 'prune'.
 
Available semirings: 'boolean', 'log', 'real', 'trivial',
and 'tropical' (default).
decode(...)
decode(fsm, keyfsm, props[, mode]) -> (fsm, keyfsm)
 
Decode costs/output labels encoded in input labels on transitions of FSM.
 
KEYFSM is a key FSM returned from the encoding of FSM.
Permitted PROPS are (a disjunction of) 'encode_*' data variables
defined in the enviroment (see help(fsm)).
determinize(...)
determinize(fsm[, mode[, label[, cthresh[, nthresh[, delta]]]]]) -> fsm
 
Determinize an FSM.
difference(...)
difference(fsm1, fsm2[, mode[, filter]]]) -> fsm
 
Difference of two FSMs.
encode(...)
encode(fsm, keyfsm, props[, mode]) -> (fsm, keyfsm)
 
Encode costs/output labels into input labels on transitions of FSM.
 
KEYFSM is either 'None' or a key FSM returned from a previous encode.
Permitted PROPS are (a disjunction of) 'encode_*' data variables
defined in the enviroment (see help(fsm)).
epsnormlize(...)
epsnormalize(fsm[, mode[, cthresh[, nthresh[, delta]]]]) -> fsm
 
Epsilon normalize an FSM.
equiv(...)
equiv(fsm1, fsm2[, delta]) -> fsm
 
Test equivalance of two FSMs.
force(...)
force(fsm) -> fsm
 
Force full expansion of a cached FSM.
intersect(...)
intersect(fsm1, fsm2[, mode[, filter]]]) -> fsm
 
Intersect two FSMs.
invert(...)
invert(fsm[, mode]) -> fsm
 
Reverse input and output labels on transitions on an FSM.
load(...)
load(filename) -> fsm
 
Load an FSM from a file.
minimize(...)
minimize(fsm[, mode[, delta]]) -> fsm
 
Minimize a deterministic FSM.
project(...)
project(fsm[, index[, mode]]) -> fsm
 
Project an FSM onto its input (index=1, default) or output
(index=2) labels.
prune(...)
prune(fsm, [cthresh[, nthresh[, mode[, qtype]]]]) -> fsm
 
Keep paths whose cost is within CTHRESH of best path.
push(...)
push(fsm, props[, mode[, qtype[, delta]]]) -> fsm
 
Push costs/labels on an FSM.
Permitted PROPS are (a disjunction of) 'push_*' data variables
defined in the enviroment (see help(fsm)).
randgen(...)
randgen(fsm[, npaths[, uni[, fin[, len[, seed]]]]]) -> fsm
 
Generate random path through an FSM.
read(...)
read(fileobject) -> fsm
 
Read an FSM from an open file object.
reverse(...)
reverse(fsm[, mode]) -> fsm
 
Reverse transitions on an FSM.
rmepsilon(...)
rmepsilon(fsm[, mode[, cthresh[, nthresh]]]) -> fsm
 
Return an equivalent FSM with no (input/output pair)
epsilon transitions.
singleton(...)
singleton(type, ilabel, olabel, cost[, smr]) -> fsm
 
Create an FSM of type TYPE with a single transition that is
labelled with ILABEL, OLABEL, and COST in semiring SMR.
 
TYPE is a string, one of: 'a[ccep]' or 't[rans]'.
 
Available semirings: 'boolean', 'log', 'real', 'trivial',
and 'tropical' (default).
synchronize(...)
synchronize(fsm[, mode[, cthresh[, nthresh[, delta]]]]) -> fsm
 
Synchrnoize input and output labels.
testclass(...)
testclass(props) -> haveprops
 
Test for various FSMClass properties.
Permitted PROPS are (a disjunction of) 'class_prop_*' data variables
defined in the enviroment (see help(fsm)).
topsort(...)
topsort(fsm[, filter[, mode]]) -> fsm
 
Topologially sort FSM according to FILTER type.
FILTER is a string, one of: 'a[ny]' (default), 'e[ps]', or 'i[eps]'.
union(...)
union(fsm1, fsm2[, mode]) -> fsm
 
From union of two FSMs.
 
Data
             __file__ = './fsm.pyc'
__name__ = 'fsm'
arith_arc_costs = 1
arith_exp = 16
arith_final_costs = 2
arith_log = 32
arith_pos = 64
arith_potentials = 4
arith_zero_costs = 8
class_prop_addarcs = 4096
class_prop_addstates = 512
class_prop_arcreordering = 33554432
class_prop_arcspersistent = 4194304
class_prop_copy = 16384
class_prop_deletestates = 1024
class_prop_nextarcpersistent = 8388608
class_prop_numarcs = 2
class_prop_numinputeps = 4
class_prop_numoutputeps = 8
class_prop_numstates = 1
class_prop_read = 32768
class_prop_seekeps = 262144
class_prop_seekinput = 1048576
class_prop_seeklabel = 524288
class_prop_seeknoneps = 262144
class_prop_seekoutput = 2097152
class_prop_seekpos = 131072
class_prop_setarcs = 2048
class_prop_setfinal = 128
class_prop_setpotential = 256
class_prop_setprops = 8192
class_prop_setsmr = 32
class_prop_setstart = 64
class_prop_settype = 16
class_prop_statereordering = 16777216
class_prop_write = 65536
encode_csts = 1
encode_decode = 4
encode_labs = 2
inf = inf
noarc = (-1, -1, 0.0, -1)
nolabel = -1
nostate = -1
prop_acyc0 = 65536
prop_cnctd = 8
prop_csort = 4
prop_deter = 32768
prop_eacyc = 64
prop_etsrt = 512
prop_fptnl = 262144
prop_iacyc = 32
prop_igrpd = 524288
prop_ilsrt = 1
prop_iptnl = 131072
prop_itsrt = 256
prop_nocst = 8192
prop_noeps = 1024
prop_noiep = 2048
prop_noneg = 16384
prop_nooep = 4096
prop_nozro = 1048576
prop_olsrt = 2
prop_sacyc = 16
prop_tsort = 128
push_csts = 256
push_eps_labs = 1024
push_labs = 512
push_tcst_final = 64
push_tcst_initial = 32
push_tcst_remove = 128
push_to_final = 2
push_to_initial = 1