Automata Theory and Logic
Deterministic Finite Automata (DFA)
A T U TO R IAL
BY
A N I M ESH CHAT U RVEDI
AT
I N DI A N I N STITU TE OF T ECHN OLOGY I N DOR E ( I I T - I)
Deterministic Finite Automata (DFA)
Representation of DFA
M1 = (Q, Σ, δ, q1, F ) where
Q = {q1, q2, q3}, Σ = {0, 1},
0 1
q1 q1 q2
the transition function δ is
q2 q3 q2
q3 q2 q2
Final state F = {q2}.
q1 is the start state, and F = {q2}.
Example: Testing Membership
01011
Next
symbol
0 0,1
1 1
A B C
Start 0
Current
state
4
Example: Testing Membership
01011
Next
symbol
0 0,1
1 1
A B C
Start 0
Current
state
5
Example: Testing Membership
01011
Next
symbol
0 0,1
1 1
A B C
Start 0
Current
state
6
Example: Testing Membership
01011
Next
symbol
0 0,1
1 1
A B C
Start 0
Current
state
7
Example: Testing Membership
01011
Next
symbol
0 0,1
1 1
A B C
Start 0
Current
state
8
Example: Testing Membership
01011
Next
symbol
0 0,1
1 1
A B C
Start 0
Current
state
9
11 1
0
0,1
1
0111 111 1
0 0
The machine accepts a string if the
process ends in a double circle
SLIDE BY STEVEN RUDICH: WWW.CS.CMU.EDU/~RUDICH RUDICH0123456789
Build a DFA
accepts the set of all strings over {0,1} that end with 00
Computer Science GATE 2009
Build a DFA
accepts the set of all strings over {0,1} that end with 00
Computer Science GATE 2009
Minimal DFA
Draw a minimal DFA which accepts the same language as a DFA with alphabet ∑ = {a,b} is given
below
Computer Science GATE 2011
Minimal DFA
Draw a minimal DFA which accepts the same language as a DFA with alphabet ∑ = {a,b} is given
below
Computer Science GATE 2011
Number of states
Definition of a language L with alphabet {a} is given as following
L = {ank | k > 0, and n is a positive integer constant}
What is the minimum number of states needed in a DFA to recognize L?
Computer Science GATE 2011
Number of states
Definition of a language L with alphabet {a} is given as following
L = {ank | k > 0, and n is a positive integer constant}
What is the minimum number of states needed in a DFA to recognize L?
n+1 states are needed in a DFA to recognize L
Let n = 3 and k=1
3+1 = 4 states
Computer Science GATE 2011
Find missing arks
Consider the set of strings on {0,1} in which, every substring of 3 symbols has at most two
zeros. For example, 001110 and 011001 are in the language, but 100010 is not. All strings of
length less than 3 are also in the language. Draw the missing arks to complete a partially
completed DFA given below
language is shown below.
Computer Science GATE 2012
Find missing arks
Consider the set of strings on {0,1} in which, every substring of 3 symbols has at most two
zeros. For example, 001110 and 011001 are in the language, but 100010 is not. All strings of
length less than 3 are also in the language. Draw the missing arks to complete a partially
completed DFA given below
Missing arks
Computer Science GATE 2012
Find missing arks
Consider the set of strings on {0,1} in which, every substring of 3 symbols has at most two
zeros. For example, 001110 and 011001 are in the language, but 100010 is not. All strings of
length less than 3 are also in the language. Draw the missing arks to complete a partially
completed DFA given below
Missing arks
Computer Science GATE 2012
Up Next
A DFA represent a Regular Expression language
Deterministic finite automata (DFA) and Non-deterministic finite automata (NFA) have same
expressive power.
Deterministic and non-deterministic finite automata accept exactly the same set of languages.
DFA or NDFA has less expressive power than Deterministic push down automata (DPDA)
