what are finite-state automaton, pushdown automaton and linear-bound automaton?

Question

(in programming language..)

Answer 1

I was hoping somebody else would answer this, but here goes...

A finite state machine (FSM) or finite state automaton (plural: automata) is a model of behavior composed of a finite number of states, transitions between those states, and actions. A state stores information about the past, i.e. it reflects the input changes from the system start to the present moment. A transition indicates a state change and is described by a condition that would need to be fulfilled to enable the transition. An action is a description of an activity that is to be performed at a given moment. There are several action types:

Entry action:
- which is performed when entering the state
Exit action:
- which is performed when exiting the state
Input action:
- which is performed depending on present state and input conditions
Transition action:
- which is performed when performing a certain transition

The concept of the FSM is at the center of theory of computing, as it begins with the basic processes by which finite bits of properly encoded information could theoretically be handled intelligently by a machine.

Pushdown automata differ from normal finite state machines in two ways:

1. They can use the top of the stack to decide which transition to take.
2. They can manipulate the stack as part of performing a transition.

Answer 2

(b^*)^* = b^* NFA can be a unmarried state S with outgoing transition merely on b and optimal to itself. S is an accepting state and the starting up up state too. it truly is transition function ought to include a unmarried get admission to: Delta(S,b) = {S}. settle for on State S.