>
> >Ignorance has been defeated though. FSM means finite state machine, the most
> >simple computing device or automaton. A full description may be found in
> >Gazdar & Mellish, Natural Language Processing in PROLOG/LISP/PoPLog.
>
> I've always heard these referred to as "finite state automata" or FSAs, also
> known as Turing machines, since it was the British mathemtician Alan Turing who
> first defined the notion. When I looked upo "finite state" in the British
> National Corpus, I found 19 occurrences, in 5 different texts, all of which
> except two occurred in the phrase "finite state grammar" (the other two being
> "finite state machine"). A search using the web metacrawler got me 49
> occurrences of the phrase "finite state" on web pages around the globe, which
> broke down as follows:
>
Sorry, but a finite state automaton (or machine) is definitely not the
same thing as a Turing machine. Both concepts belong to automata
theory but they are used to refer to specific kinds of automata which
happen to be at the opposite end of the spectrum in terms of formal
power. The Turing machine is the less restricted kind of automata,
capable in principle of describing any kind of language, whatever its
properties. Finite state automata, on the other hand, are the most
restricted kind of automata: they do not even have enough formal power
to describe a language including any sentence made up of N occurrences
of "a" followed by the same number N of "b"'s. The interest of highly
restricted kinds of automata such as FSA's derives from the fact that
they make computation (e.g. parsing) much easier.
Automata theory is closely related with "formal grammar theory". The
various kinds of automaton can be put in direct correspondence with
corresponding types of grammars in the "Chomsky hierarchy". For
example, Turing machines are equivalent to general phrase structure
grammars, pushdown automata are equivalent to context-free grammars
and FSA's are equivalent to regular grammars (or equivalently to
regular expressions).
There exists an enormous amount of literature on these topics. A
classic reference is:
Hopcroft J. & Ullman J.; Introduction to Automata Theory, Languages
and Computation, Addison-Wesley, 1979.
If you can search corpora made up of recent literature in formal and
computational linguistics, you will notice that the terms "finite
state automaton (or machine)" and "finite state transducer" appear
increasingly often. This is because novel and linguistically
interesting ways have recently been found to make good use of these
computationally tractable tools.
-- Pierre Isabelle tel: (514) 973-5801 CITI, 1575 Chomedey Blvd, fax: (514) 973-5757 Laval, Quebec, Canada H7V 2X2 e-mail: isabelle@citi.doc.ca