27 Oct 1999 14:07:50 -0400

Related articles |
---|

infinite state machines karthik@cdotd.ernet.in (1999-10-21) |

Re: infinite state machines jfflorio@acm.org (J. Florio) (1999-10-21) |

Re: infinite state machines qjackson@wave.home.com (Quinn Tyler Jackson) (1999-10-21) |

Re: infinite state machines bourguet@my-deja.com (1999-10-27) |

Re: infinite state machines chstapfer@bluewin.ch (Christian Stapfer) (1999-10-27) |

Re: infinite state machines mac@coos.dartmouth.edu (1999-10-27) |

Re: infinite state machines scorp@btinternet.com (1999-10-28) |

From: | "Christian Stapfer" <chstapfer@bluewin.ch> |

Newsgroups: | comp.compilers |

Date: | 27 Oct 1999 14:07:50 -0400 |

Organization: | Swisscom AG, the blue window |

References: | 99-10-104 |

Keywords: | DFA |

<karthik@cdotd.ernet.in> wrote in article: 99-10-104@comp.compilers...

*> If we have finite state machines, is it possible to have 'infinite'*

*> state machines.*

Depending on what one is willing to count as part of the "state" of a

machine, infinite state machines are very useful CONCEPTUAL models,

and not at all esoteric, as you seem to assume.

*> One web site just mentioned that 'infinite state machines*

*> are conceivable but not practical'.*

For the conceptual model of an automaton to be useful to us FINITE

human beings it must be specifiable with a FINITE amount of

information. If you just extend the model of a finite state machine

in a simple-minded way by allowing an infinite number of states, you

get an INFINITE specification for such an automaton: not very useful

for us humans.

But, as I said, as CONCEPTUAL models, some cleverly constrained types

of infinite state machines are neither exotic nor useless. Perhaps the

most important "infinite state" machine that is used in compiler

design theory is the pushdown machine: it has an infinite number of

states, because its stack component can be in an infinite number of

different states. By factoring the pushdown machine into a stack

(that can store an infinite number of symbols) and a finite state

control that bases its operation not only on its current state, and

the current input symbol but also on the symbol currently on the top

of the stack, you get a neat, compact, finite SPECIFICATION; even

though, that machine, if REALIZED in practice, would require an

infinite number of states. Which (probably) is not possible in this

world. (The number of particles in the universe is finite, as far as

we know.)

To sum up: Infinite state machines of various sorts are frequently

used idealizations that are very handy as CONCEPTUAL models but they

can only be approximated by finite state machines in practice. I hope

you realize that this situation is not exotic at all: applications of

mathematics in science and technology are full of similar

idealizations. For example, it would be extremely difficult for us to

reason, as we do, for example in calculus, if we refused to accept

idealizations such as irrational and transcendent numbers (the numbers

pi and e come to mind immediately, I suppose). Christian

P.S: Of course, any introductory book on automata theory would answer

your question, at least implicitly. They just do not normally belabor

the point, as I did here.

"A man who could give a convincing account of mathematical reality

would have solved very many of the most difficult problems of

metaphysics. If he could include physical reality in his account,

he would have solved them all."

- G.H. Hardy: 'A Mathematician's Apology'

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.