1
$\begingroup$

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?

$\endgroup$
  • 5
    $\begingroup$ 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". $\endgroup$ – Shaull Jan 7 '16 at 15:34
  • $\begingroup$ @Shaull Could you please explain what a configuaration means? Is it Instantaneous Description (ID) of Machine at any particular instance of time? $\endgroup$ – Romy Jan 7 '16 at 17:27
  • $\begingroup$ 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. $\endgroup$ – Shaull Jan 7 '16 at 17:43
  • $\begingroup$ @Shaull okay.I have one more doubt, contents of the stack means the complete stack right, not just the top of the stack? $\endgroup$ – Romy Jan 7 '16 at 18:14
  • 1
    $\begingroup$ yes, you need the entire contents of the stack to know what to do from here on (rather than just the next step). $\endgroup$ – Shaull Jan 7 '16 at 18:28
5
$\begingroup$

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)

$\endgroup$
  • 2
    $\begingroup$ You may want to use "configuration" instead of "state" here; the latter is used for finite sets all over the Chomsy hierarchy. $\endgroup$ – Raphael Jan 8 '16 at 11:32
  • $\begingroup$ 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)). $\endgroup$ – Klaus Draeger Jan 8 '16 at 12:38
  • $\begingroup$ @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 $\endgroup$ – Nikos M. Jan 8 '16 at 12:50
  • $\begingroup$ @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) $\endgroup$ – Nikos M. Jan 8 '16 at 12:51
  • $\begingroup$ 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. $\endgroup$ – Raphael Jan 8 '16 at 17:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.