Copyright © 1996 Xerox Corporation.
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.
Copyright © The Document Company - Xerox 1997
. All rights reserved.
Written by André Kempe and Lauri Karttunen. Last modified on
Jan. 12, 1998
.