Can anyone please explain difference between finite state machine and finite automata?

Question

Can anyone please explain with example what is the difference between finite state machine and finite automata?

Susanasusanetta

Different names for the same thing. – Hetaera

Wikipedia agrees: “finite-state machine (FSM) or finite-state automaton”. Makes me wonder whether we should merge the tags finite-state-machine and finite-automata, and fsm while we are at it. But that's a question for meta. – Dab

Answer 1

Both "Finite State Machine" FSM and "Finite Automata" (or Finite State Automata) FA means same, represents an abstract mathematical model of computation for the class of regular languages.

The word "Finite" significance the presence of the finite amount of memory in the form of the finite number of states Q (read: Finiteness of Regular Language).

Generally in formal-theory (or theory of computation), we prefer to use the word "Automata" – to emphasise that our machine is 'automatic' machine (self-moving: like our computer) — "automatic" in the sense that once you have been defined transition rules, you do not need to apply any explicit intelligent to process strings (you just need to refer transition rules at each step). Remember our ultimate aim behind defining transition machines is to automate the computational task (I think slightly different than another kind of mechanical machines whose purpose is to save energy e.g weaving machines).

By the way, automata or state-machines are a graphical representation to describe transition rules (that is comparatively easy sometimes). You can also use "Transition Tables" or "Transition function" like δ(q0, a) → q1. Basically, all uses for the same purpose just to define "Mappings".

Sideboard

Answer 2

As far as I understand, both have "states", and "actions" that make the machine move from one state to another upon an input signal. Thus the conceptual ideas are the same. There is some difference in the details.

In FSM for circuit designs the input signal is mostly assumed to be a bit (binary), whereas in finite state automata one can have a general "abstract" alphabet of input symbols.

Second, a FSM also generates an output, associated to the state reached, also binary. In automata terminology this 'extension' is called a Moore machine.

Automata however have final (or accepting) states, that signal a favourable input read. Finally, FSM are mostly deterministic, i.e., for each input in a certain state there is one next state.

In automata theory one also considers the nondeterministic variant where one might have choice in where to move.

Sunn