DISPLAYING FINITE-STATE NETWORKS

On these pages finite-state networks are displayed as in the following example :

      4 states, 11 arcs, Circular.
      Sigma: ? a b 
      fs0:  ? -> fs0, a -> fs1, b -> fs0.
      fs1:  ? -> fs0, a -> s2, b -> fs0, <a:b> -> fs3.
      s2:   ? -> fs0, a -> s2, b -> fs0, <a:b> -> fs3.
      fs3:  (no arcs)
      

States :

The network has four states, fs0, fs1, s2 and fs3. Three of them, fs0, fs1 and fs3, are final (prefix f). The start state always has index 0. In the example the start state fs0 is also final.

Arcs :

State fs0 has three outgoing arcs. One arc is labeled with a and goes to state fs1. The other two arcs are labeled with ? and b respectively and are both cyclic, i.e. they have the same state fs0 as both the source and destination.

Labels :

The above network is a transducer representing a relation between two languages which we call the upper and the lower language. Labels can either be single symbols like a, ? and b or symbol pairs like <a:b> (lines 2 and 3). In the case of <a:b>, the symbol a belongs to the upper and the symbol b to the lower language. In a transducer, the label a actually means the identity pair <a:a>.

Sigma :

The sigma of a network is an alphabet, a list of known symbols. It includes all the symbols that appear in the network, either as such or as a component of a symbol pair. The sigma may also include symbols that are not explicitly present (see finite-state networks).

Unknown symbol :

In a displayed network the question mark ? represents unknown symbols, that is, all symbols that are not included the sigma alphabet of the network. In the above transducer example, ? denotes any identity pair that does not involve a or b. Note: ? has a different meaning in a regular expression.

Epsilon :

The label 0 (not in the example) means epsilon (the empty string).

Networks and regular expressions :

The network in this example has been compiled from a regular expression that describes the relation that is encoded by the network. Can you guess what that expression is? The answer is here.

There is another page about finite-state networks in general and a page explaining how networks accept and generate strings, and more examples.

For more detailed information please look at our pointers to finite-state literature.

We welcome your comments and suggestions.