20 Sep 2001 00:22:26 -0400

Related articles |
---|

Infinite State Machines are used everywhere in CS. whopkins@alpha2.csd.uwm.edu (2001-09-20) |

From: | whopkins@alpha2.csd.uwm.edu (Mark William Hopkins) |

Newsgroups: | comp.compilers |

Date: | 20 Sep 2001 00:22:26 -0400 |

Organization: | University of Wisconsin - Milwaukee, Computing Services Division |

Keywords: | theory, DFA |

Posted-Date: | 20 Sep 2001 00:22:26 EDT |

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).

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.