2
$\begingroup$

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)

$\endgroup$
  • 4
    $\begingroup$ Yes. A finite automaton which can move left and right on its tape and can overwrite a symbol on the tape is known as a Turing machine and is indeed strictly more powerful. $\endgroup$ – Rick Decker Sep 7 '17 at 14:29
  • 2
    $\begingroup$ I suggest reading Rabin's original paper. The goal was to come up with a model more realistic (weaker) than the Turing machine model. $\endgroup$ – Yuval Filmus Sep 7 '17 at 14:31
  • $\begingroup$ @RickDecker, if tape has finite size, which languages does it recognize? $\endgroup$ – rus9384 Sep 7 '17 at 14:31
  • 1
    $\begingroup$ @rus9384 If the tape has a finite size, the set of possible "states" (combining the state and the tape content) is finite. And thus it is also a finite automaton. It is no more powerful and recognize only regular languages. $\endgroup$ – Lamine Sep 7 '17 at 14:41
  • $\begingroup$ @Lamine, then can it be smaller, then classical DFA? Like NFA is usually smaller than DFA. $\endgroup$ – rus9384 Sep 7 '17 at 14:46
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. By this do you mean the famous Halting problem the Alan Turing said. $\endgroup$ – Madhusoodan P Sep 8 '17 at 16:18
  • $\begingroup$ But which of these is computer? It is clear, that computer has memory, but also it is clear that it has constant amount of it. $\endgroup$ – rus9384 Sep 8 '17 at 17:02
  • $\begingroup$ @MadhusoodanP Yes, that's the halting problem. $\endgroup$ – David Richerby Sep 9 '17 at 18:27
5
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ I don't think the history is all that relevant. It's also misleading - it suggests that these things were invented purely out of intellectual curiosity and do not represent things used in reality, while the opposite is true: finite state machines and regular languages abound in computing, they are used in all sorts of applications, and theoretical knowledge of their powers and limitations has very practical applications. $\endgroup$ – reinierpost Sep 7 '17 at 15:19
  • $\begingroup$ I'm not sure the historical record agrees with you. Perhaps finite state machines were reinvented and reinvented many times, but the intellectual tradition in theoretical computer science originates, it seems, in the work of Rabin and Scott. $\endgroup$ – Yuval Filmus Sep 7 '17 at 15:21
  • $\begingroup$ ... or McCullogh and Pitts. I just think there's plenty of present-day use to complement that historical record. $\endgroup$ – reinierpost Sep 7 '17 at 15:29
  • 1
    $\begingroup$ The question asks about "the people who came up with this automaton theory". These are the people mentioned in my post. $\endgroup$ – Yuval Filmus Sep 7 '17 at 15:31
  • 1
    $\begingroup$ Well, Mealy machine is older than given paper. $\endgroup$ – rus9384 Sep 7 '17 at 15:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.