All India Council for Technical
Education
Finite Automata
o Finite automata are used to recognize patterns.
o It takes the string of symbol as input and changes its state accordingly. When the
desired symbol is found, then the transition occurs.
o At the time of transition, the automata can either move to the next state or stay
in the same state.
o 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:
1. Q: finite set of states
2. ∑: finite set of the input symbol
3. q0: initial state
4. F: final state
5. δ: 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.
5.4M
610
Difference between JDK, JRE, and JVM
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.
Application Id Page
- x/y
All India Council for Technical
Education
Types of Automata:
There are two types of finite automata:
1. DFA(deterministic finite automata)
2. NFA(non-deterministic finite automata)
1. 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.
2. 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.
Some important points about DFA and NFA:
1. Every DFA is NFA, but NFA is not DFA.
2. There can be multiple final states in both NFA and DFA.
3. DFA is used in Lexical Analysis in Compiler.
Application Id Page
- x/y
All India Council for Technical
Education
4. NFA is more of a theoretical concept
Transition Diagram
A transition diagram or state transition diagram is a directed graph which can be
constructed as follows:
o There is a node for each state in Q, which is represented by the circle.
o There is a directed edge from node q to node p labeled a if δ(q, a) = p.
o In the start state, there is an arrow with no source.
o Accepting states or final states are indicating by a double circle.
Some Notations that are used in the transition diagram:
Application Id Page
- x/y
All India Council for Technical
Education
There is a description of how a DFA operates:
5M
574
Features of Java - Javatpoint
1. In DFA, the input to the automata can be any string. Now, put a pointer to the
start state q and read the input string w from left to right and move the pointer
according to the transition function, δ. We can read one symbol at a time. If the
next symbol of string w is a and the pointer is on state p, move the pointer to
δ(p, a). When the end of the input string w is encountered, then the pointer is on
some state F.
Application Id Page
- x/y
All India Council for Technical
Education
2. The string w is said to be accepted by the DFA if r ∈ F that means the input
string is said to be rejected by DFA if r ∉ F.
string w is processed successfully and the automata reached its final state. The
Example 1:
DFA with ∑ = {0, 1} accepts all strings starting with 1.
Solution:
The finite automata can be represented using a transition graph. In the above
diagram, the machine initially is in start state q0 then on receiving input 1 the
machine changes its state to q1. From q0 on receiving 0, the machine changes
its state to q2, which is the dead state. From q1 on receiving input 0, 1 the
machine changes its state to q1, which is the final state. The possible input
strings that can be generated are 10, 11, 110, 101, 111......., that means all
string starts with 1.
Example 2:
NFA with ∑ = {0, 1} accepts all strings starting with 1.
Solution:
The NFA can be represented using a transition graph. In the above diagram, the
machine initially is in start state q0 then on receiving input 1 the machine
changes its state to q1. From q1 on receiving input 0, 1 the machine changes its
state to q1. The possible input string that can be generated is 10, 11, 110, 101,
111......, that means all string starts with 1.
Application Id Page
- x/y
All India Council for Technical
Education
Application Id Page
- x/y
