CSE 305
Lecture 18
Finite-State Automata (5)
Md. Mijanur Rahman, Prof. Dr.
Dept. of Computer Science and Engineering, Jatiya Kabi Kazi Nazrul Islam University, Bangladesh.
[Link]
1
Contents
Finite State Automata
Finite State Machine NFA, e-NFA with Definitions and Examples
Types of Finite Automata Conversion of e-NFA into NFA (without e)
Transition Function, Diagram and Table The Equivalence of NFA’s with and without e-moves
DFA with Definitions and Examples The Equivalence of DFA’s and NFA’s
Two-way FA
Extended Transition Function
FA with Output: Moore machine, Mealy machine,
Language of a DFA Equivalence
Minimization of DFA Applications of FA
2
Equivalence of DFA and NFA
• It requires a method of converting NFA to its equivalent DFA.
• In NFA, when a specific input is given to the current state, the machine goes to
multiple states. It can have zero, one or more than one move on a given input
symbol.
• On the other hand, in DFA, when a specific input is given to the current state, the
machine goes to only one state. DFA has only one move on a given input symbol.
• The Equivalence of DFA’s and NFA’s:
• Let, M = (Q, ∑, δ, q0, F) is an NFA which accepts the language L(M). There should be
equivalent DFA denoted by M' = (Q', ∑', q0', δ', F') such that L(M) = L(M’).
3
Conversion from NFA to DFA
Steps for converting NFA to DFA:
• Step 1: Initially Q' = ϕ
• Step 2: Add q0 of NFA to Q'. Then find the transitions from this start state.
• Step 3: In Q', find the possible set of states for each input symbol. If this set of states is
not in Q', then add it to Q’.
• Step 4: In DFA, the final state will be all the states which contain F(final states of
NFA)
4
Example: Conversion from NFA to DFA
• Example-1: Convert the following NFA to DFA.
• Solution: For the given transition diagram we will first construct the transition table.
5
Example: Conversion from NFA to DFA
• Now we will obtain δ' transition for state q0.
• The δ' transition for state q1 is obtained as:
• The δ' transition for state q2 is obtained as:
6
Example: Conversion from NFA to DFA
• Now we will obtain δ' transition on [q1, q2].
7
Example: Conversion from NFA to DFA
• The state [q1, q2] is the final state as well because it contains a final state q2.
• The transition table for the constructed DFA will be:
8
Example: Conversion from NFA to DFA
• The state [q1, q2] is the final state as well because it contains a final state q2.
• The Transition diagram will be:
• The state q2 can be eliminated because q2 is an unreachable state.
9
Example: Conversion from NFA to DFA
• Example-2 : Convert the following NFA to DFA.
• Solution: For the given transition diagram we will first construct the transition table.
10
Example: Conversion from NFA to DFA
• Now we will obtain δ' transition for state q0.
• The δ' transition for state q1 is obtained as:
• Now we will obtain δ' transition on [q0, q1].
11
Example: Conversion from NFA to DFA
• As in the given NFA, q1 is a final state, then in DFA wherever, q1 exists that state becomes a
final state. Hence in the DFA, final states are [q1] and [q0, q1].
• Therefore set of final states F = {[q1], [q0, q1]}.
• The transition table for the constructed DFA will be:
12
Example: Conversion from NFA to DFA
• Therefore set of final states F = {[q1], [q0, q1]}.
• The transition diagram for the constructed DFA will be:
• Even we can change the name of the states of DFA.
13
Example: Conversion from NFA to DFA
NFA
• Changing the name of the states of DFA.
Suppose:
A = [q0]
B = [q1]
C = [q0, q1]
• With these new names the DFA will be as follows:
DFA
14
Equivalence of DFA and NFA with e-Moves
• It requires a method of converting NFA with e-moves to its equivalent DFA.
• Non-deterministic finite automata(NFA) is a finite automata where for some cases when a specific
input is given to the current state, the machine goes to multiple states or more than 1 states. It can
also contain ε move. It can be represented as M = { Q, ∑, δ, q0, F}.
Q: finite set of states
∑: finite set of the input symbol
q0: initial state
F: final state
δ: Transition function
• On the other hand, in DFA, when a specific input is given to the current state, the machine goes to
only one state. DFA has only one move on a given input symbol.
• The Equivalence of DFA and NFA with e-moves:
• Let, M = (Q, ∑, δ, q0, F) is an NFA with e-moves which accepts the language L(M). There should be
equivalent DFA denoted by M' = (Q', ∑', q0', δ', F') such that L(M) = L(M’).
15
Conversion from NFA with ε to DFA
• NFA with ∈ move: If any FA contains ε transaction or move, the finite automata is called NFA
with ∈ move.
• ε-closure: ε-closure for a given state A means a set of states which can be reached from the
state A with only ε(null) move including the state A itself.
• Steps for converting NFA with ε to DFA:
• Step 1: We will take the ε-closure for the starting state of NFA as a starting state of DFA.
• Step 2: Find the states for each input symbol that can be traversed from the present. That means the
union of transition value and their closures for each state of NFA present in the current state of DFA.
• Step 3: If we found a new state, take it as current state and repeat step 2.
• Step 4: Repeat Step 2 and Step 3 until there is no new state present in the transition table of DFA.
• Step 5: Mark the states of DFA as a final state which contains the final state of NFA.
16
Example: Conversion from NFA with ε to DFA
• Example-1: Convert the following NFA with e-move into its equivalence DFA.
• Solution: For the given transition diagram we will first construct the transition table.
States Input e Input 0 Input 1
q0 {q1, q2} - -
q1 - q3 -
q2 - - q3
q3 - - q4
*q4 - - -
17
Example: Conversion from NFA with ε to DFA
• Let us obtain ε-closure of each state.
• Now, let ε-closure {q0} = {q0, q1, q2} be state A.
18
Example: Conversion from NFA with ε to DFA
• Now, let ε-closure {q0} = {q0, q1, q2} be state A.
• Hence,
The partial DFA will be
19
Example: Conversion from NFA with ε to DFA
• Now,
The DFA will be:
• For state C:
20
Example: Conversion from NFA with ε to DFA
• Example-2: Convert the following NFA with e-move into its equivalence DFA.
• Solution: For the given transition diagram we will first construct the transition table.
States Input e Input 0 Input 1 Input 2
q0 q1 q0 - -
q1 q2 - q1 -
*q2 - - - q2
21
Example: Conversion from NFA with ε to DFA
• Let us obtain the ε-closure of each state.
• Now we will obtain δ' transition. Let ε-closure(q0) = {q0, q1, q2} call it as state A.
22
Example: Conversion from NFA with ε to DFA
• Thus we have obtained
δ'(A, 0) = A
δ'(A, 1) = B
δ'(A, 2) = C
• The partial DFA will be:
• Now we will find the transitions on states B and C for each input.
23
Example: Conversion from NFA with ε to DFA
• Now we will find the transitions on states B and C for each input. Hence,
24
Example: Conversion from NFA with ε to DFA
• Thus we have obtained
δ'(B, 0) = ϕ
δ'(B, 1) = B
δ'(B, 2) = C
• The partial transition diagram will be
25
Example: Conversion from NFA with ε to DFA
• Now we will obtain transitions for C:
Hence the DFA is:
• As A = {q0, q1, q2} in which final state q2 lies, hence A is final state. B = {q1, q2} in which the state q2 lies, hence
B is also final state. C = {q2}, the state q2 lies, hence C is also a final state. 26
?
THE END
27