Re: FSA vs FSM : evidence from the bnc and the web

Jeff Adams (jeffa@kurz-ai.com)
Wed, 17 Apr 1996 12:08:04 -0400

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

I don't believe TMs are considered FSMs (or FSAs :-). I have
always assumed that "FSM" referred to "deterministic finite
state automata" (DFAs) and their nondeterministic cousins.

It is easy to show that there are languages which are described
by Turing machines (& pushdown automata, an intermediate class of
machine), which are *not* describable by DFAs. One of the simplest
examples is the language of palindromes: strings which read the
same backwards and forwards. These are easily described by
push-down automata or Turing machines, but not by any DFA.

A Turing machine *does* have a finite-state component, but
it also has an unbounded stack, so the number of states that
the machine can be in is most definitely *not* finite.

Jeff

-- 
Jeff Adams
Language Modeling Scientist
Kurzweil Applied Intelligence
http://www.kurz-ai.com/people/jeffa