An Introduction to Finite Automata

Finite Automata

• Finite automata are used to recognize patterns.
• It takes the string of symbols as input and changes its state accordingly. When the desired symbol is found, then the transition occurs.
• At the time of transition, the automata can either move to the next state or stay in the same state.
• Finite automata have two states, Accept state or Reject state. When the input string is processed successfully, and the automata reached its final state, then it will accept.

Formal Definition of FA

A finite automaton is a collection of 5-tuple (Q, ∑, δ, q0, F), where:

• Q: finite set of states  
• ∑: finite set of the input symbol  
• q0: initial state   
• F:  final state  
• δ: Transition function  

Finite Automata Model:

Finite automata can be represented by input tape and finite control.

Input tape: It is a linear tape having some number of cells. Each input symbol is placed in each cell.

Finite control: The finite control decides the next state on receiving particular input from input tape. The tape reader reads the cells one by one from left to right, and at a time only one input symbol is read.

Finite Automata Construction :

Let L(r) be a regular language recognized by some finite automata (FA).

• States : States of FA are represented by circles. State names are written inside circles.

• Start state : The state from where the automata starts, is known as the start state. Start state has an arrow pointed towards it.

• Intermediate states : All intermediate states have at least two arrows; one pointing to and another pointing out from them.

• Final state : If the input string is successfully parsed, the automata is expected to be in this state. Final state is represented by double circles. It may have any odd number of arrows pointing to it and even number of arrows pointing out from it. The number of odd arrows are one greater than even, i.e. odd = even+1.

• Transition : The transition from one state to another state happens when a desired symbol in the input is found. Upon transition, automata can either move to the next state or stay in the same state. Movement from one state to another is shown as a directed arrow, where the arrows points to the destination state. If automata stays on the same state, an arrow pointing from a state to itself is drawn.

Example : We assume FA accepts any three digit binary value ending in digit 1. FA = {Q(q0, qf), Σ(0,1), q0, qf, δ}

FA is characterized into two types: 

1) Deterministic Finite Automata (DFA) –

DFA consists of 5 tuples {Q, Σ, q, F, δ}. 
Q : set of all states.
Σ : set of input symbols. ( Symbols which machine takes as input )
q : Initial state. ( Starting state of a machine )
F : set of final state.
δ : Transition Function, defined as δ : Q X Σ --> Q.

In a DFA, for a particular input character, the machine goes to one state only. A transition function is defined on every state for every input symbol. Also in DFA null (or ε) move is not allowed, i.e., DFA cannot change state without any input character. 
For example, below DFA with Σ = {0, 1} accepts all strings ending with 0.
Figure: DFA with  Σ = {0, 1}

One important thing to note is, there can be many possible DFAs for a pattern. A DFA with a minimum number of states is generally preferred. 
2) Nondeterministic Finite Automata(NFA) 
NFA is similar to DFA except following additional features: 
Null (or ε) move is allowed i.e., it can move forward without reading symbols. 
Ability to transmit to any number of states for a particular input. 
However, these above features don’t add any power to NFA. If we compare both in terms of power, both are equivalent. 
Due to the above additional features, NFA has a different transition function, the rest is the same as DFA. 
δ: Transition Function
δ:  Q X (Σ U ε ) --> 2 ^ Q. 
As you can see in the transition function is for any input including null (or ε), NFA can go to any state number of states. 
For example, below is an NFA for the above problem. 
 
NFA
One important thing to note is, in NFA, if any path for an input string leads to a final state, then the input string is accepted. For example, in the above NFA, there are multiple paths for the input string “00”. Since one of the paths leads to a final state, “00” is accepted by the above NFA. 
Some Important Points: 
Justification: 
Since all the tuples in DFA and NFA are the same except for one of the tuples, which is Transition Function (δ) 
In case of DFA
δ : Q X Σ --> Q
In case of NFA
δ : Q X Σ --> 2Q
Now if you observe you’ll find out Q X Σ –> Q is part of Q X Σ –> 2Q.
On the RHS side, Q is the subset of 2Q which indicates Q is contained in 2Q or Q is a part of 2Q, however, the reverse isn’t true. So mathematically, we can conclude that every DFA is NFA but not vice-versa. Yet there is a way to convert an NFA to DFA, so there exists an equivalent DFA for every NFA. 
 
Both NFA and DFA have the same power and each NFA can be translated into a DFA. 
There can be multiple final states in both DFA and NFA. 
NFA is more of a theoretical concept. 
DFA is used in Lexical Analysis in Compiler. 
Applications of Finite Automata :

Applications of finite automata include string matching algorithms, network protocols and lexical analyzers

1] String Processing :

Consider finding all occurrences of a short string(pattern string) within a long string (text string).
This can be done by processing the text through\a DFA: the DFA for all strings that end with the
pattern string. Each time the accept state isreached, the current position in the text is output.