Automata

Finite State machine : history definition Model example

Feb 22, 2016

7798

History of Finite State machine:

The finite state machine becomes a branch of computer science illustrates its wide range of applications. The first person who considers the conc ept of a finite state machine included a team of biologists, psychologists, mathematicians, engineers and some of the first computer scientists. The members of this team shared their common interest that based on to model the human thought process, whether in the brain or in a computer. The two neurophysiologists Warren McCulloch and Walter Pitts were the first to present a description of finite automata in 1943. Their research paper, entitled, “A Logical Calculus Immanent in Nervous Activity”, made significant contributions to the study of neural network theory, theory of automata, the theory of computation and cybernetics. Later this research G.H. Mealy and E.F. Moore two computer scientists generalized the theory to much more powerful machines in separate research papers, published in 1955-56.

Definition of finite state machine:

An automaton in which the state set {Q} contains only a finite number of elements is called a finite-state machine (FSM), it is famous name is Finite Automata (FA). FSMs are conceived as an abstract machine that can be in one of a finite number of states. The FSMs is in only one state at a time; the state it is in at any given time is called the current state. At each unit of time an FSM can change its state and switches to potentially another state when current state of FSM took inputs form alphabets ∑ and triggering event or condition; this process called transition. An individual FSM is defined by a list of its finite states, finite input alphabets ∑ and the triggering condition for each successful transition. FSMs can also be used to accept strings. A string is recognized or accepted by an FSMs if the last state entered by the machine on that input string is a final state. The language recognized (or accepted) by an FSM is the set of strings accepted by it.

Formal Definition of finite-state Machine:

A finite-state machine M is defined by seven-tuple are as follows;
M = (Q, Σ, δ, Ψ, λ, q₀,F),
Where, each tuple have its specification and meaning.

Q: It represents the non-empty set of finite states. All the finite number of states which is the part of FSMs M comes under Q.
Σ: It presents the non-empty finite set of the input alphabet.
δ : It represents the state transition function. The state transition function takes the current state from Q and an input alphabet from Σ and returns the new set of output alphabets and the next state. Therefore, it can be seen as a function which maps an ordered sequence of input alphabets into a corresponding sequence, or set, of output events.
Q × Σ → Q is the next-state function.
Ψ: It presents the finite set of is the output alphabet.
λ : It represent the output function. Its mathematically denotes as;
Q → Ψ.
q₀: It is the initial state (which may be fixed or variable depends on machine behavior).
F: It is the set of final states (F ⊆ Q).

If the FSM is given input letter a when in state q, it enters state δ(q, a). While in state q it produces the output letter λ(q).

Finite state machine model:

The next-state and output functions of an FSM are represented by δ and λ respectively in graphically representation of FSM model. We visualize these functions taking a state value from a memory and an input value from an external input and producing next-state and output values. Next-state values are stored in the memory and output values are released to the external world. From this representation an actual machine can be constructed. Once circuits are constructed for δ and λ, we need only add memory units and a clock to construct a sequential circuit that emulates an FSM.

Example of FSM:

Suppose we want to write a program to recognize the word “automata” in an input program. Logically, your program will look something like this:

cin >> char
while (char != “a”) cin >> char
if (cin >> char != “u”) go to step 1
if (cin >> char != “t”) go to step 1
if (cin >> char != “o”) go to step 1
if (cin >> char != “m”) go to step 1
if (cin >> char != “a”) go to step 1
if (cin >> char != “t”) go to step 1
if (cin >> char != “a”) go to step 1
done

We can explain each step in this program as follows:

Initialization
Looking for “a”
Recognized “a”, looking for “u”
Recognized “au”, looking for “t”
Recognized “aut”, looking for “o”
Recognized “auto”, looking for “m”
Recognized “autom”, looking for “a”
Recognized “automa”, looking for “t”
Recognized “automat”, looking for “a”
Recognized “automata”

Each step in the program corresponds to a different place in the recognition process.