Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Well, I should have posted this question before Why NFA is called Non-deterministic?. Anyways now this is pondering in my mind.
Why people who came up with this automaton theory restricted the input format of it as a read-only, symbol-stream tape.
Is it not so that if we provide random accessible input tape (as in case of many computer programs) to the automaton it will be more powerful? (however it is purely my intuition having no standard proofs)
Yes, there are things you could do to finite automata to make them more powerful. However, "with great power(er) comes great(er) responsibility."
Finite automata aren't very powerful but the languages they express – the regular languages – form a natural and important class. Furthermore, for a fixed automaton, you can decide in linear time (with respect to the input) and constant working space whether it accepts or rejects any particular string. This is true even if the automaton is nondeterministic.
OK, but lots of important languages can't be decided by finite automata. Important examples include anything that involves bracket matching, including the syntax of any sane programming language. How might you try to make automata more powerful and what would the cost be?
Suppose we allow the machine to scan both left and right along its input. This gives a two-way automaton. Well, it turns out that two-way automata (deterministic or nondeterministic) still only accept regular languages – the same as ordinary automata. The two-way automaton might require fewer states and you can still determine whether it accepts a given input in linear time. But now there's the possibility that the automaton can loop forever, so you need to check for that, which requires a logarithmic amount of working space, instead of constant. (Since the number of steps before termination is bounded by some linear function of the length of the input, you can detect looping by counting steps and halting if the computation runs too long. The counter needs a logarithmic number of bits.)
Suppose you allow the automaton to move backwards and forwards as well as overwrite its input, but not to use any more space than the input takes up. This does make the machine more powerful (for example, you can now detect well-matched bracketings by "crossing out" the brackets one by one) but it makes it even harder to determine whether the machine accepts its input and to check for infinite loops. Now, halting might take exponentially many steps, so you need a polynomial-length counter (linear is probably enough).
Suppose you allow the automaton to move backwards and forward, overwrite its input and use as much additional space as it wants. Now your automaton has become a Turing machine. It can do (we think) anything that any reasonable computer can do but there's no way of determining whether it accepts its input except for running the machine and hoping it eventually stops. This could take arbitrarily long and use arbitrarily much working space.
There are plenty of other possible additions to automata (for example, stacks) but they don't fit as neatly into the discussion above.
So, yes, you might want to make automata more powerful. But doing so brings risk and expense that you might not be prepared to tolerate, if you don't need it.
The modern definition of finite automata (deterministic and nondeterministic) appears in the foundational paper of Rabin and Scott, Finite automata and their decision problems, which also introduced nondeterminism in general. Here is what they had to say:
Turing machines are widely considered to be the abstract prototype of digital computers; workers in the field, however, have felt more and more that the notion of a Turing machine is too general to serve as an accurate model of actual computers. It is well known that even for simple calculations it is impossible to give an a priori upper bound on the amount of tape a Turing machine will need for any given computation. It is precisely this feature that renders Turing’s concept unrealistic.
In the last few years the idea of a finite automaton has appeared in the literature. These are machines having only a finite number of internal states that can be used for memory and computation. The restriction of finiteness appears to give a better approximation to the idea of a physical machine. Of course, such machines cannot do as much as Turing machines, but the advantage of being able to compute an arbitrary general recursive function is questionable, since very few of these functions come up in practical applications.
Many equivalent forms of the idea of finite automata have been published. One of the first of these was the definition of “nerve-nets” given by McCulloch and Pitts. The theory of nerve-nets has been developed by authors too numerous to mention. We have been particularly influenced, however, by the work of S. C. Kleene who proved an important theorem characterizing the possible action of such devices (this is the notion of “regular event” in Kleene’s terminology). ...
Originally, finite automata (in a very different form) were introduced as a model for neural networks in the brain (hence the name "nerve-nets"). Later on, a different motivation came up: finding a computational model which is more realistic than the much-too-strong Turing machines. Even later, regular languages were included in the Chomsky hierarchy, and it was realized that they are very useful for certain parsing tasks.
Unfortunately this history is usually skipped in introductory classes.
The name "regular language" (originally "regular event") comes from Kleene. His original RAND report "welcome[s] any suggestions as to a more descriptive term" (and mentions that it might be the same concept as McCulloch and Pitts' "prehensible"), but this comment was dropped in the journal version Representation of events in nerve nets and finite automata.
(Disclaimer: I'm not an expert on the history of computer science, so I might have gotten some of the facts wrong or presented them in a misleading way.)
