Infinite State Machines are used everywhere in CS.

From: karthik@cdotd.ernet.in (karthik@cdotd.ernet.in)
>Hi,
> If we have finite state machines, is it possible to have 'infinite'
>state machines.


Of course. That's what all computational models are in general!


Apart from finite state automata/transducers; all automata/transducer
models are infinite state machines; as is described below in detail on
a case by case basis.


Push down automata/transducers; turing machines/transducers are all
infinite state machines where


                (a) the state set Q factors in particular ways
                (b) "selection rules" are imposed on the transition relation
                (c) The transition relation respects certain "symmetry" conditions.


The actual specification of (a), (b) and (c) determines which class of
machine or automata models comprise the particular specialization of
the infinite state machine.


A state machine A = (Q,I,F,M,H) consists of:


                Q: A [possibly infinite] set of states
                I, F: Subsets of Q comprising the initial and final states
                M: The word algebra
                H, subset of Q x M x Q: The transition relation


Transitions in H are denoted as arcs labelled by words:


                                (q,w,r) in H <=> q -- w --> r


and you can write q -> wr to denote this transition.


The language L(A) accepted by A defined as the subset of M:


                        L(A) = { w in M: q ->* w r for some q in I, r in F }


where ->* is the path closure of -> defined recursively by:


                      q ->^0 1 q (1 denotes empty word)
                      q ->^{n+1} vwr if q ->^n vs; s -> wr for some state s
                      q ->* vr if q ->^n vr for some n = 0,1,2,...


A word algebra M is any algebraic system with a product satisfying
the properties
                                (ab)c = a(bc); a1 = a = 1a


with 1 denoting the 'empty word' and products denoting 'word concatenation'.
[This is called a monoid]. The languages recognised by automata are
subsets of monoids. This can be generalized further by replacing


"subset of monoid" by "element of a quantale"


since subsets of a monoid form a quantale.


[Definitions of these items and some details on the 'algebraic approach'
can be found in www.csd.uwm.edu/~whopkins. This is undergoing another
round of revision and reconstruction].


The usual specializations are:


(A) AUTOMATON:
        If the word algebra M = X*, for some set X; then the machine is an
        AUTOMATON with input alphabet X.
(B) TRANSDUCER:
        If M = X* x Y*, then it's a TRANSDUCER with input alphabet X, output
        alphabet Y.
(C) DETERMINISTIC:
        If M = X* x Y* (including as a special case M = X*, when Y = {1}),
        a deterministic transition is one where
                    for each q in Q, v in X*, there is at most one transition
                    of the form:
                                              q -> v w r: w in Y*, r in Q


For transducers you can also define the 'translation set'


                  For v in X*: A[v] = { w in Y*: (v,w) is in L(A) }


which contains the set of all outputs corresponding to a given input. For
a deterministic transducer, A[v] is either empty or contains one word only.


The specializations to machine class are:


(D) FINITE STATE Automaton/Machine:
        Q is finite.
        The usual restriction of I = {s}, s = start state; is not essential.
        The usual restriction of transitions to the form
                            q -> x r, x in X (for automata)
                            q -> xwr, x in X, w in Y* (for machines)
        are also inessential.


(E) PUSH DOWN Automaton/Transducer:
        Q = Q0 x S*, Q0 is finite, S = "stack alphabet" Transitions
        The forms of transitions for H are restricted ('selection rules')
        to the forms:
                              (q,As) -> v (r,AB); A, B in S*, s in S
                              (q,1) -> v (r,B); B in S*; 1 denotes empty word in S*
        and the SYMMETRY requirement is imposed on H:
          if (q,As) -> v (r,AB) then (q,A's) -> v (r, A'B) for all words A' in S*


        Initial states are of the form (q,1); and final states are of the
        form (r,1) when the 'empty stack' condition is imposed. A 2nd
        variant allows arbitrary stack words in the final state; so any
        state in Q0 x S* can be final. Then the symmetry requirement is
        extended:
                          If (r,A) is final then (r,A') is final for all words A' in S*.


The symmetry conditions and selection rules mean you can specify the
transition relation and initial and final state sets in the forms:


                                (q,s,v,B,r) for (q,As) -> v (r,AB)
                                (q,1,v,B,r) for (q,1) -> v (r,B)
                                Initial states: all q for which (q,1) is initial
                                Final states: all r for which (r,B) is final
so then
                  H subset of Q x (S+{1}) x M x S* x Q
                  I,F subsets of Q


(F) TURING MACHINES
        Q = Q0 x S* x S*, Q0 is finite, S = 'symbol set'
        M = {1} (no actual I/O word algebra)
        H is restricted to the forms:
                  (q,L,sR) -> (r,L,tR) -- null motions
                  (q,Ls,R) -> (r,L,tR) -- left motions
                  (q,L,sR) -> (r,Lt,R) -- right motions
        where L, R are in S*; s, t are in S. The same kind of symmetry
        requirements
        The symmetry requirements are
          (q,L,sR) -> (r,L,tR) <==> (q,L',sR') -> (r,L',tR') for all L',R' in S*
          etc.
        Start states are of the form (q,1,R) [i.e. start on the left end of tape]
        Final states are of the form (r,L,1) [i.e. finish on right end of tape]
        The restriction to (r,L,1) is not essential.
        Same symmetry requirements
                (q,1,R) start state <--> (q,1,R') start state for all R' in S*
                (r,L,1) final state <--> (r,L',1) final state for all L' in S*


Turing machines are 2 stack machines.


You can make this a bona fide automaton or transducer, by adding in a
couple extra items


        * Make S a superset of X and Y
        * Restrict start and final states to the forms (q,1,1) and (r,1,1)
        * Add in transitions
                (q,1,1) -> v (q,1,v), for words v in X*; if (q,1,1) is a start state
                (r,w,1) -> w (r,1,1), for words w in Y*; if (r,1,1) is a final state


>Does anybody know of any web site or book or paper which explains something
>about this?


Well, given the above, the question is kinda moot. Infinite State Machines
are part and parcel of everything that's ever discussed! They're just
not seen clearly as such because the general definition is always
rendered in specialized form; like shown above for push down transducers.


>I tried searching in Altavista but got very little. One web site just
>mentioned that 'infinite state machines are conceivable but not practical'.
>Can somebody explain?


Their comment is supremely ironic.


But I've never seen a direct reference to ISA's as such anywhere (except
here and elsewhere in stuff I've written).

Return to the comp.compilers page.
Search the comp.compilers archives again.