Finite Automata Without Output
NFA with and without Epsilon Transition
Constructing DFA from NFA with Epsilon Transition
Steps to convert NFA with Epsilon move to DFA: Step 1 : Take ∈ closure for the beginning state of NFA as beginning state of DFA.
Step 2 : Find the states that can be traversed from the present for each input symbol
(union of transition value and their closures for each states of NFA present in current state of DFA).
Step 3 : If any new state is found take it as current state and repeat step 2.
Step 4 : Do repeat Step 2 and Step 3 until no new state present in DFA transition table.
Step 5 : Mark the states of DFA which contains final state of NFA as final states of DFA.
NFA with Epsilon Transition
If any finite automata contains ε (null) move or transition, then that finite automata is called NFA with ∈ moves
Example of NFA with Epsilon Move:
Equivalence and Minimization of Finite Automata
Main topic
Introduction to Finite Automata
DDNRCSDD
DFA Designing
DFA for Languages
Example: Asked in Previous year University Exam:
Design a deterministic finite automata(DFA) for accepting the language L = {a^n b^{m} | m+n=even}
DFA for strings
Example: Asked in Previous year University Exam:
Construct a DFA machine over input alphabet \sum_= {0, 1}, that accept even number of 1's
Subtopic
Example: Asked in Previous year University Exam:
Construct a DFA machine over input alphabet Sigma= {0, 1}, that accepts odd number of 0's and even number of 1's
Difference between NFA and DFA
In DFA no transition for empty input i.e for epsilon
In NFA transition for empty input i.e. for epsilon
Difference in Transition function
DFA transition function: Q x Sigma->Q
NFA transition Function: Q x Sigma->2^Q
String Acceptance by FA
String Acceptance by NFA
Testing
Lets take one input string abab
First input is a, so from state A we will go to state B
Second input is b, so from state B we will go to state C
Third input is a, so from state C we will go to state C itself
Fourth input is b, so from state C we will go to state C itself(final state)
String Acceptance by DFA
Testing
Lets take one input string abab
First input is a, so from state A we will go to state B
Second input is b, so from state B we will go to state C
Third input is a, so from state C we will go to state C itself
Fourth input is b, so from state C we will go to state C itself(final state)
A string is said to be accepted by a Finite Automata when it is accepted by final state starting from initial state while consuming one input during each transition
Conversion from NFA to DFA
While converting NFA to DFA, if NFA has n states than the corresponding DFA will have 2^n states.
DFA is not designed for all 2^n states but only for those states reachable from initial state.
Example: Convert the following NFA into DFA
Solution: Transition table is
Example: Previous year University Exam Question
Convert the following NFA into DFA
Representation of Finite Automata
It can be represented in two ways:
1. Transition/State diagram
2. Transition/State table
Transition Table:
Non-Deterministic Finite Automata (NFA/NDFA)
NFA is also of 5-tuples (Q, Sigma, Del, q0, qf)
Where, 4-tuples are same as DFA but the difference is in Del only. Del- Transition function which maps Q x Sigma-> 2^Q, For example- Del (q0, a) = {q0,q1}
NFA Example:
Deterministic Finite Automata (DFA)
Tuples
Q-f
qf- Final state or set of final states enclosed in circle or marked by a special symbol in Transition table and enclosed in double circle in Transition diagram
Q-0
q0- Initial/starting state, denoted by Arrow in Transition table and circle with arrow in transition diagram
Delta
Del- Transition function which maps Q x Sigma->Q i.e. there is one transition for each input from one state to another. For exam Del(q0,a)= q1
Sigma
Sigma- Finite set of nonempty inputs denoted by a....z/0.....9
Q
Where. Q- Finite nonempty set of states denoted by q0,q1,q2....../A,B........Z,
