Class Transducer

Sequential Transducer, i.e., a letter-to-letter function.

Inputs

P = {p1, p2,...} is the set of input ports. An input port p takes values in a set Vp. Set Vp is called the "type" of input port p. A "valuation" is an assignment of values to the input ports in P.

We call "inputs" the set of pairs:

 {(p_i, Vp_i),...}

of input ports p_i and their corresponding types Vp_i.

A guard is a predicate (bool-valued) used as sub-label for a transition. A guard is defined by a set and evaluated using set membership. So given an input port value p=x, then if:

 x \in guard_set

then the guard is True, otherwise it is False.

The "inputs" are defined by an OrderedDict:

 {'p1':explicit, 'p2':check, 'p3':None, ...}

where:

• explicit: is an iterable representation of Vp, possible only for discrete Vp. If 'p1' is explicitly typed, then guards are evaluated directly:

   input_port_value == guard_value ?
  

• check: is a class with methods:
  • __contains__(x) : check if guard value given to input port 'p1' is in the set of possible values Vp.
  • __call__(guard_set, input_port_value) : check if input_port_value \in guard_set This allows symbolic type definitions.

    For example, input_port_value might be assigned int values, but the guard_set be defined by a symbolic expression as the str: 'x<=5'.

    Then the user is responsible for providing the appropriate method to the Mealy Machine, using the custom check class described here.

    Note that we could provide a rudimentary library for the basic types of checks, e.g., for the above simple symbolic case, where using function eval() is sufficient.

• None: signifies that no type is currently defined for this input port, so input type checking and guard evaluation are disabled.

  This can be used to skip type definitions when they are not needed by the user.

  However, since Machines are in general the output of synthesis, it follows that they are constructed by code, so the benefits of typedefs will be considerable compared to the required coding effort.

Guards annotate transitions:

 Guards: States x States ---> Input_Predicates

Outputs

Similarly defined to inputs, but:

• for Mealy Machines they annotate transitions
• for Moore Machines they annotate states

State Variables

Similarly defined to inputs, they annotate states, for both Mealy and Moore machines:

 States ---> State_Variables

Update Function

The transition relation:

• for Mealy Machines:

   States x Input_Valuations ---> Output_Valuations x States
  
   Note that in the range Output_Valuations are ordered before States
   to emphasize that an output_valuation is produced
   during the transition, NOT at the next state.
  
   The data structure representation of the update function is
   by storage of the Guards function and definition of Guard
   evaluation for each input port via the OrderedDict discussed above.
  

• for Moore Machines:

   States x Input_Valuations ---> States
   States ---> Output_valuations
  

Note

A transducer may operate on either finite or infinite words, i.e., it is not equipped with interpretation semantics on the words, so it does not "care" about word length. It continues as long as its input is fed with letters.

For Machines, each state label consists of (possibly multiple) sublabels, each of which is either a variable, or, only for Moore machines, may be an output.

See Also

FSM, MealyMachine, MooreMachine

Initialize a graph with edges, name, graph attributes.

Parameters
----------
data : input graph
    Data to initialize graph.  If data=None (default) an empty
    graph is created.  The data can be an edge list, or any
    NetworkX graph object.  If the corresponding optional Python
    packages are installed the data can also be a NumPy matrix
    or 2d ndarray, a SciPy sparse matrix, or a PyGraphviz graph.
name : string, optional (default='')
    An optional name for the graph.
attr : keyword arguments, optional (default= no attributes)
    Attributes to add to graph as key=value pairs.

See Also
--------
convert

Examples
--------
>>> G = nx.Graph()   # or DiGraph, MultiGraph, MultiDiGraph, etc
>>> G = nx.Graph(name='my graph')
>>> e = [(1,2),(2,3),(3,4)] # list of edges
>>> G = nx.Graph(e)

Arbitrary graph attribute pairs (key=value) may be assigned

>>> G=nx.Graph(e, day="Friday")
>>> G.graph
{'day': 'Friday'}