FSA,FSM & Turing Machines

Llu?s Padrd (padro@lsi.upc.es)
Wed, 17 Apr 1996 18:27:04 +0200

Lou Burnard wrote:

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

FSM and FSA are the same, but a Turing Machine is something else:

FSM (or FSA) are computation models able to recognize regular languages (RL),
so, they are equivalent to regular expressions (RE).

PDA (push-down automatons) are FSM that can use a stack. This enables them
to recognize context-free languages (CFL), so, they are
equivalent to contex free grammars (CFG)

TM (Turing Machines) are more sophisticated, and are able to recognize
any recognizable thing (even context-dependent languages),
so, they are equivalent to a computer program.

These computational models are closely related to Chomsky's language
hierarchy.

yours,

Lluis

--------------------------------------------------------------------------------
Lluís Padró i Cirera Tel. XX-34-3-4017988
Departament de Llenguatges i Sistemes Informàtics XX-34-3-8967751
Universitat Politècnica de Catalunya
Fax. XX-34-3-4017040
Mail Address: c/ Pau Gargallo 5 XX-34-3-8967700
08028 Barcelona
--------------------------------------------------------------------------------