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?
What does the term Finite stands for in Finite State Machines?
terminology;automata;finite automata
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).updatenote 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)