Finite Automata(FA) is the simplest machine to recognize patterns. The finite Automata or finite state machine is an abstract machine that has five elements or tuples. It has a set of states and rules for moving from one state to another but it depends upon the applied input symbol. Basically, it is an abstract model of a digital computer. The following figure shows some essential features of general automation.
The above figure shows the following features of automata:
1. Input
2. Output
3. States of automata
4. State relation
5. Output relation
A Finite Automata consists of the following :
Q : Finite set of states.
Σ : set of Input Symbols.
q : Initial state.
F : set of Final States.
δ : Transition Function.
Formal specification of machine is
{ Q, Σ, q, F, δ }
FA is characterized into two types:
1) Deterministic Finite Automata (DFA) — DFA refers to deterministic finite automata. Deterministic refers to the uniqueness of the computation. In the DFA, the machine goes to one state only for a particular input character. DFA does not accept the null move.
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.
Graphical Representation of a DFA
A DFA is represented by digraphs called state diagram.
· The vertices represent the states.
· The arcs labeled with an input alphabet show the transitions.
· The initial state is denoted by an empty single incoming arc.
· The final state is indicated by double circles.
Example
Let a deterministic finite automaton be →
· Q = {a, b, c},
· ∑ = {0, 1},
· q0 = {a},
· F = {c}, and
Transition function δ as shown by the following table −
Its graphical representation would be as follows −
Application of DFA ( Deterministic Finite Automata):
As DFA have a rich background in terms of the mathematical theory underlying their development it has wide application that we are used our daily life directly or indirectly, some of them are as follows;
· Protocol analysis
· Text parsing,
· Video game character behavior,
· Security analysis,
· CPU control units,
· Natural language processing
· Speech recognition, etc.
2) Non-deterministic Finite Automata(NFA)
NFA stands for non-deterministic finite automata. It is used to transmit any number of states for a particular input. It can accept the null move.
NFA is similar to DFA except following additional features:
1. Null (or ε) move is allowed i.e., it can move forward without reading symbols.
2. 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.
Graphical Representation of an NDFA: (same as DFA)
An NDFA is represented by digraphs called state diagram.
· The vertices represent the states.
· The arcs labeled with an input alphabet show the transitions.
· The initial state is denoted by an empty single incoming arc.
· The final state is indicated by double circles.
Example
Let a non-deterministic finite automaton be →
· Q = {a, b, c}
· ∑ = {0, 1}
· q0 = {a}
· F = {c}
The transition function δ as shown below −
Its graphical representation would be as follows −
DFA vs NDFA
The following table lists the differences between DFA and NDFA.
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.
1. Both NFA and DFA have the same power and each NFA can be translated into a DFA.
2. There can be multiple final states in both DFA and NFA.
3. NFA is more of a theoretical concept.
4. DFA is used in Lexical Analysis in Compiler.
Application of DFA:
As we know that NFAs and DFAs are equivalent, so if a language is recognized by an NFA then it is also recognized by a DFA and vice versa. The establishment of such equivalence is important highly applicable in various cases as follows;
· Construction of an NFA to recognize a given language is sometimes much easier than constructing a DFA for that language.
· NFAs used to reduce the complexity of the mathematical work required to establish many important properties in the theory of computation.
· NFAs is highly applicable to prove closure properties of regular languages in much easier way compare to DFAs.
Blog By -
Vishwajeet Mote
Akansha Pokale
Somnath More
Amit Puranik
References -
https://er.yuvayana.org/nfa-nondeterministic-finite-automata-definition-example
application/#:~:text=Application%20of%20DFA%3A&text=Construction%20of%20an%20NFA%20to,in%20the%20theory%20of%20computation.
https://www.tutorialspoint.com/automata_theory/non_deterministic_finite_automaton.htm
https://www.geeksforgeeks.org/introduction-of-finite-automata/#:~:text=Finite%20Automata(FA)%20is%20the,upon%20the%20applied%20input%20symbol.
https://www.javatpoint.com/finite-automata
https://www.tutorialspoint.com/automata_theory/deterministic_finite_automaton.htm