Re: Do all state transition functions require state transition matrixes?

Peter Olcott wrote:
> Is there a more generic means to implement a state transition function than a
> state transition matrix? What would be the term for defining such a generic
> means of state transition?

In the comp.compilers archive, you may still find the "regex" software
I put there in 1992 and 1993 (the 4 software items in it as DFA, NFA
for doing conversions to finite automata; REX which implements a
superset of GREP; and FSC, a "finite state classifier"). What
distinguishes it from other regular expression software is that it
makes explicit use of the underlying algebra to actually calculate
automata from its corresponding regular expression.

The automata are represented as a series of equations with the
interpretations:
q = 1 + ... <-> q is a final state
q = ... + xq' + ... <-> q has a transition on
x to q'.

Since the system is linear, you *could* arrange such a system in matrix
form
Q = F + X Q
with F being the column vector containing the 0's and 1's that mark
which states are final; and X being the transition matrix. But, since
it's usually a sparse matrix, you could more simply arrange it so that
you have a set of algebraic expressions; defining a general structured
type for algebraic expressions. That's what the DFA and NFA software
demos in the regex archive do. Then each state q may be is associated
with the expression representing the right-hand side of its equation.

In DFA and NFA, states *are* expressions, themselves, so all that the
software is doing is linking up expressions to other equivalent
expressions, while carrying out the process of algebraically reducing a
given expression to a linear form [1 +] xq + xq + ...

Since the transition relation is a subset H of Q x X x Q you could also
implement the set H as a hash-table.

NFA and DFA, for instance, would take the expression a*(ba*)* and
reduce it to the form
a*(ba*)* = (ba*)* + a a*(ba*)* = (1 + (ba*)(ba*)*) + a
a*(ba*)*
which yields the linear relation
a*(ba*)* = 1 + a (a*(ba*)*) + b (a*(ba*)*).
Correspondingly you have the 1-state automaton
q0 = 1 + a q0 + b q0
with the state q0 being regarded as one and the same as the expression
a*(ba*)*, itself.

.