Hardware Reference
In-Depth Information
Chapter 6
Implementation of Automata Manipulations
In the following, we use the term transition to refer to a directed arc of an STG,
which enables the movement of an automaton from the current state to the next
state. The transition predicate indicates when the transition is enabled. A transition
predicate is an arbitrary Boolean function in terms of the inputs. In some cases,
this function is just a minterm. In this case, to avoid confusion, we will refer to a
minterm transition.
A number of practical applications require representation and manipulation of
finite automata and FSMs. Depending on an application, these objects can be
specified as:
1. Sequential logic circuits
2. Transition relations
3. Explicit state transition graphs (STGs)
In the first case, logic circuits are typically represented as directed acyclic graphs
with nodes corresponding to logic gates or latches. In the second case, the
transition relations are often represented using binary decision diagrams (BDDs)
in a monolithic or partitioned form (conjunction of transition relations). A transition
relation for an automaton is the set of (current state, next state, predicate) tuples
describing the arcs of the automaton. In the third case, an STG specifying an
automaton or FSM is represented using one of the three methods described below.
The implementation of several procedures for manipulating STGs is outlined in the
following subsections.
Languages used in solving language equations are represented as finite automata.
Operations on languages are implemented as operations over finite automata. Basic
procedures for efficient manipulation of automata assume their specification as
STGs. This is the reason that representing and manipulating STGs is of particular
importance for implementing the theory developed in this topic.
First, we introduce several approaches to representing STGs in a software im-
plementation and motivate the use of one of them, called the hybrid representation,
which we believe is the most efficient in general.
Search WWH ::
Custom Search