29
causing it to write a given symbol, say “The,” then that constrains the range of symbols it could
write next: “girl,” “boy,” “man,” or “woman,” among others; but the list would be finite, since
the number of states the machine can enter is finite. If the machine writes “woman,” thus giving
us “The woman,” that limits the possible symbols which it could write next. And so on, with a
rule for stopping at some point. Such an automaton can be either probabilistic or deterministic.
(Note that in entering state 3 in Figure 1, there is a certain probability of the machine’s writing
either “X” or “S.”)
Although the number of states in a finite-state automaton is finite, there is no limit to the
number of formulae it can write. As seen in Figure 1, the machine can go from states 3 to 2 to 1
an unlimited number of times, and so there is no limit to the number of times it may repeat the
sequence SXN in writing a formula. Furthermore, once in state 3, there is no limit to the number
of times it may write “X.” This capacity for unbounded productivity may give one a certain
confidence in the ability of some sufficiently baroque finite-state grammar to produce the
sentences of a natural language. One may be tempted to surmise that such an automaton reflects
actual operations in the brain.
But there is a problem here, as shown by Chomsky (1956); no finite-state automaton can
do justice to the syntax of a natural language. Imagine a grammar capable of producing the
following series of strings: AB, AABB, AAABBB, and so on. The rule here is that any number
of As must be followed by an equal number of Bs. Other strings are ungrammatical. No finite-
state automaton can exemplify this rule. A machine would have to record how many times it had
written “A” in order to know how many times to write “B.” This would require an infinite
number of states, since there is no limit on how many times “A” can be written. A system with
only finitely many possible states could not follow this rule, since it would require the capacity to
remember an infinite number of different things. It so happens that this rule reflects the potential