In automata theory, we all read automata as finite automata, from the very beginning. What I want to know is, why are automata finite? To be clear, what is it in an automaton that is finite - the alphabet, language, strings made with regular expressions, or what? And are there (in theory) any non-finite automata?
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ Certainly not the language or the "strings made with regular expressions"; many simple regular expressions match an infinite number of strings (but they can be recognized by a finite automaton.) $\endgroup$– alexisDec 6, 2017 at 22:48
-
$\begingroup$ I asked a question having an infinte one in mind: cs.stackexchange.com/questions/55864/… $\endgroup$– Jesus is LordDec 6, 2017 at 23:05
Add a comment
|
8 Answers
$\begingroup$
$\endgroup$
1
All automaton models you'll typically encounter are finitely represented; otherwise there would be uncountably many, which means they are not captured by Turing-complete models. Or, in CS-think, they'd be useless¹.
"Finite automata" are called finite because they only have a finite set of configurations (the input string aside). Pushdown automata, for instance, have a stack that can have arbitrary content -- there are infinitely many possible configurations.
Nota bene: Configurations of PDAs are still finitely represented! In fact, any computational model that falls inside Turing-computability has to have finitely representable configurations, otherwise TMs wouldn't be able to simulate them.
- I consciously disregard hypercomputation here for the purpose of this question.
-
$\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$– Raphael ♦Dec 7, 2017 at 13:15
$\begingroup$
$\endgroup$
7
The full name is "finite state automata". The crucial part is that the state of the automaton can be fully characterized by an element of some finite set of discrete states. This means that if the (relevant) state of the automaton involves a real-valued variable, there is an infinite number of potential states (putting aside the finiteness of floating point representations), and the automaton is not finite.
This might not ever happen in theoretical computer science, but it's not too exotic in the domain of modeling real number sequences. Hidden Markov Models can be used to model a number sequence as the output of a probabilistic system consisting of one output filter for each state of a (discrete, finite) Markov model with unobservable states. The filters compute the next real-valued output from a vector of the previous outputs ("autoregressive" model), but the underlying Markov model is finite since its transition probabilities only depend on the current Markov state.
However, this article (full text) develops a variation where the transition probabilities also depend on the real-number vector of prior outputs. The state of this system is the combination of a discrete Markov state and a tuple of real numbers ("mixed state Markov model"), hence it can be in an infinite number of different states.
In short, non-finite automata are theoretically well-defined, and occasionally even encountered.
-
1$\begingroup$ Full disclosure: I am one of the authors of the paper mentioned. I'm not sure if that's considered proper disclosure or irrelevant self-promotion... $\endgroup$– alexisDec 6, 2017 at 15:30
-
6$\begingroup$ I think it's perfectly okay to reference own work where appropriate -- if you're one of the leading experts on a topic, we're glad to have you! -- and a plain disclosure as yours is quite enough. Thanks! $\endgroup$– Raphael ♦Dec 6, 2017 at 15:46
-
$\begingroup$ Finite-state automata don't include pushdown automata, right? Is there a particular reason all the way to real-number states? I'm not sure if I'm missing something here about why this obvious example wouldn't work or if you merely just happened to pick an unusual example instead. $\endgroup$ Dec 7, 2017 at 0:23
-
1$\begingroup$ I think he's trying to ask why you didn't use a more conventional non-FSA like a pushdown automaton instead of jumping to something like real-valued state variables. $\endgroup$ Dec 7, 2017 at 3:14
-
1$\begingroup$ Well, mainly because that's the example I thought of! But also the "state" of a mixed-state Markov model consists of a fixed number of parameters, but there is still an infinite number of states (defined as current position + transition probabilities) because some of the parameters are real numbers (but affect the transitions, not just the output). In the PDA case, the non-finiteness comes from the unlimited size of the stack; but there are still only a finite number of rules, which are of finite length, so at ony one step there is only a finite number of possible bebaviors. $\endgroup$– alexisDec 7, 2017 at 11:36
$\begingroup$
$\endgroup$
6
In a finite automaton, there is quite a bit of finiteness: the number of states, the size of the underlying alphabet, and the lengths of the strings accepted by the machine.
You can certainly relax the finiteness condition on these by allowing, say, the machine to have infinitely many states but if you do, the resulting machine becomes uninteresting, in the sense that such machines can be designed to accept any languages at all.
answered Dec 6, 2017 at 13:36
-
$\begingroup$ And what if it's only the alphabet that is infinite? what if we are working with a regular expression on Natural numbers for example? is that possible? $\endgroup$– parvinDec 6, 2017 at 14:44
-
8$\begingroup$ If the automaton is finite but the alphabet is infinite, then the automaton will have a finite number of transitions out of each state. Any character not associated with one of the transitions will not be recognized by the automaton. As a result, you could replace the infinite alphabet with a finite alphabet containing only the characters appearing in the automaton's transitions, and the automaton would still accept exactly the same language. $\endgroup$– KevinDec 6, 2017 at 15:28
-
3$\begingroup$ @parvin Not really. You'd need have an infinite number of transitions between your (finite number of) states then - which you still cannot represent. If you go for predicates (like "all even inputs go from A to B, all odd inputs go from A to C"), you basically break your alphabet down into a finite number of equivalence classes. $\endgroup$– BergiDec 6, 2017 at 15:28
-
$\begingroup$ @Kevin, that depends on how you define "finite number of transitions". Consider an ordinary (finite) FSA, with the next state chosen according to any finite partition of the natural numbers: e.g., by the remainder of division by 7. Or consider a similar situation involving real numbers. The state diagram is fully finite, but it is well-defined over an infinite alphabet. $\endgroup$– alexisDec 6, 2017 at 19:59
-
$\begingroup$ @Parvin I'd say the answer is "yes" (see my previous comment). $\endgroup$– alexisDec 6, 2017 at 20:02
$\begingroup$
$\endgroup$
In fact, in automata theory (which departs a lots from the origins of Kleene, Rabin and Scott), there are many forms of automata that are not finite. This arises for several reasons.
Pushdown automata, for instance, are automata that have an infinite set of configurations (these have a finite number of states, but the reality is that these should be thought as 'infinite automata').
In the same vein, there ar other examples of infinite automata for which the state space is infinite, but with a lot of structure. For instance one considers the class of automata that have as state space a (finite dimension) vector space, and as transition functions linear maps (plus some initial an final things). These are known as weighted automata over a base field (due to Schützenberger in 61). These can be minimized and tested for equality. Other examples include register automata (these automata have a finite set of registers, and work over an infinite alphabet: these can compare letters with registers and store letters in registers), and the more modern form of nominal automata (that have the same expressiveness, but have better foundations and properties). Emptiness of such automata is decidable.
But, even for studying finite state automata, it makes sense to talk about infinite automata. Indeed, consider the category of finite state deterministic automata that accept a fixed given language L, equipped with the standard notion of automata morphism, then this category fails to have an initial and a final object. However, if you live in the category of all deterministic (say countable) automata, then there is an initial object (the automaton that has as states $A^*$, as initial state the empty word, when it reads letter $a$ in state $u$ it goes to state $ua$, and a state is accepting if it belongs to L). There is also a final object (that has as states languages!). The existence of these two objects are one way to explain at high level why deterministic automata can be minimised and is tightly linked to the Myhill-Nerode congruence.
To conclude, there are infinite automata, but the models that are first studied in a lecture are always the finite state ones.
$\begingroup$
$\endgroup$
I think the question is assuming the conclusion that there are no infinite state automata when there are, they just aren't worth bringing up.
In Automata Theory, there is a hierarchy of powers of different virtual models. The one I learned had 4 (that I remember, it has been some time), the one I found on Wikipedia has 5. The weakest in either finite state automata, and the strongest is Turing machines. There is a some concept of a level more powerful than Turing machines that is loosely called hypercomputation. Many different descriptions of virtual machines fall into one of these levels. Turing machines are especially known for numerous models all having the same level of computational power.
An infinite state automata, at least one formally defined, will fall into one of these levels. There may something a little interesting in showing how a certain rigorous definition of an infinite state automata fits into one of these levels, but other than that, it wouldn't be of much use given there are far more well studied virtual machines representing each level. It's similar to how there isn't much interest in a billion tape Turing machine, since it would be no more powerful than a single tape Turing machine but more complicated to deal with.
Now, if you happened to find an infinite state automata that wasn't equivalent to an existing level of the hierarchy, that might be interesting. But without that, infinite state automatas are already captured within the existing hierarchy, and given the added complications of dealing with infinity, we just avoid them in the same way we avoid any overly complicated Turing machine model.
$\begingroup$
$\endgroup$
The (naive) infinite version of deterministic finite state machine is too powerful. Such a thing would be capable of "memorizing" any language at all, so there is not much to be learned from considering them.
For example, over a binary alphabet, consider an automaton in the form of a complete binary tree of infinite height. Every possible string you could consider as input corresponds uniquely to a node of the tree, so you can construct a decider for any language at all simply by making the corresponding nodes accepting states.
$\begingroup$
$\endgroup$
There is such a concept as an "infinite" automata, however, they are not normally as interesting as finite automata practically to software or hardware designers. There is some research and research papers on infinite automata, but I'll give a simple (and practical example) below, and you may see why no-one talks about infinite automata except for perhaps, mathematicians, but I dare say some of them have interesting properties.
The counter:
Given some event you want to count, then the infinite automata yields the output, where for the sake of simplicity it's state directly maps to the traditional output symbol in an alphabet (giving the answer). Both state and output symbol space is infinite in this case, and is the set of natural numbers [0..infinity)
count = 0
count --- [event] ---> count + 1
Essentially this is "counting". It is however also a state machine, but it's so trivial that we say "counter".
(Note that computers may a have limit on the size of the counter, but the premise of the machine is still valid.)
Things may get more interesting with real values and complex mathematical functions, for most people, these are mathematical functions, and not state machines. The marking thing to note about a state machine, however, is that they can be in a given state, and change state based on some external input, like the counter above, and they do so over time through a sequence of inputs.
$\begingroup$
$\endgroup$
Infinite automata, that is, like finite automata but with an infinite number of states, are a particular kind of transition system. Infinite transition systems of various kinds are commonly used to describe the behaviour of discrete systems.
answered Jul 6, 2020 at 22:23