# What does the term "Finite" stands for in Finite State Machines?

Do we consider Pushdown Automata, Turing Machines in Finite State Machines?
If we don't, then what does the term "Finite" stands for in Finite state machines, as PDAs & TMs are also defined to have Finite Number of States?

• The term "finite state machine" is usually used to say that the number of possible configurations of the machine is finite. With this definition, TMs and PDAs are not finite state machines, while regular automata (DFAs) are finite state. However, sometimes it just means that the number of states is finite, in which case TMs and PDAs also have a finite "control". Jan 7 '16 at 15:34
• @Shaull Could you please explain what a configuaration means? Is it Instantaneous Description (ID) of Machine at any particular instance of time?
– Romy
Jan 7 '16 at 17:27
• I'm not familiar with the ID terminology, but yes: for a PDA, a configuration is given by the current state and the contents of the stack. For a TM, a configuration is the current state, the contents of the tape, and the location of the read-write head. For a DFA, a configuration is just the state. Jan 7 '16 at 17:43
• @Shaull okay.I have one more doubt, contents of the stack means the complete stack right, not just the top of the stack?
– Romy
Jan 7 '16 at 18:14
• yes, you need the entire contents of the stack to know what to do from here on (rather than just the next step). Jan 7 '16 at 18:28

The number of states is finite in finite state machines (aka regular laguages).

In contrast, in a push-down machine (PDA) the number of states is potentialy infinite (more correctly unbounded, leaving out stack size limitations), but the machine itself does not bound the number of states (that is why a stack is used) (aka context-free languages)

To put it in another way, a finite state machine can store all its needed state (in the general sense, including transition rules, current symbol etc..) only in fixed finite storage, unlike push-down machine (or other automaton) which cannot do that.

A PDA, for example, by its design and definition, does not determine a fixed size needed for all its state (it is unbounded, aka infinite in this respect)

And to clear up the confusion, PDAs (and other automata) may have finite number of transition rules but not finite number of (potential) states (also refered as configurations) (see above).

update

note that a PDA does not necesarily need infinite storage, for example any given PDA can at any given time only need finite storage and even during its whole operation its storage size does not exceed an upper limit. However this is not fixed before-hand by the machine itself (like for FSMs) and thus is formaly unbounded. In fact for PDAs the storage size is determined by the input size itself and is a linear function of the length of the input (which are part of automata refered as LBAs, linear-bounded-automata, in which one end is always fixed, the bottom of the stack)

• You may want to use "configuration" instead of "state" here; the latter is used for finite sets all over the Chomsy hierarchy.
– Raphael
Jan 8 '16 at 11:32
• It may differ on your context; I'm used to saying that all those machines have finitely many (control) locations, but possibly infinitely many states (which are then e.g. tuples (location, stack contents)). Jan 8 '16 at 12:38
• @Raphael i prefer to use "state" (so FSM is correct as term) instead of configuration and transition rules, symbols etc for other parameters, but that is optional Jan 8 '16 at 12:50
• @KlausDraeger yes ok, in the final analysis finite refers to specific things , now the terminology (and aliases of that) can vary (and indeed do vary, sometimes not optimaly) Jan 8 '16 at 12:51
• I've never heard of read "control locations" before now. Btw, in some definitions an FSM configuration is technically not finite since it includes (the rest of) the input word.
– Raphael
Jan 8 '16 at 17:12