Construction of minimal DFA
Information on this page based on: YouTube: Theory Of Computation 2, Construction of minimal DFA and problems
 Construct a minimal DFA that accepts set of all strings over {a,b} of length 2
ω ∊ {a,b} and ω = 2
Σ = {a,b}
L = {aa,ab,ba,bb}
This DFA is NOT corect. It does accept set of all strings over {a,b} of length 2, but it should also reject
strings of other lengths for example: {a,a,a}
This DFA is corect. It does accept set of all strings over {a,b} of length 2 and rejects strings of other lengths for example: {a,a,a}
When is the string accepted:
The string is accepted by the FA if we are able to reach a final state starting from the initial state
upon scanning the entire string.
When is the language accepted:
The language is accepted by the FA if all strings in the language are accepted.
All strings not in the language are rejected.
Notes:
 A FA can have more than 1 final state.
 State D is also called the dead or trap state.
 This minimal DFA has 4 states and state C (also referred as q2) is the final state.
 The language L is finite which means the FA is finite (= finite number of states).
 Construct a minimal DFA that accepts set of all strings over {a,b} of length 2 or more
ω ∊ {a,b} and ω >= 2
L = {aa,ab,ba.bb,aaa, ..., bbb, ...}
Notes:
 For a language L you can draw many DFA diagrams, but there is only 1 minimal DFA.
The word "minimal" refers to the minimal number of states used.
 The language L is infinite, we do not know if the FA is finite or infinite.
By drawing the FA diagram there are a finite number of states which means this minimal DFA is finite.
 State A represents set of all strings of length 0.
 State B represents set of all strings of length 1.
 State C represents set of all strings of length 2.
 This minimal DFA has 3 states and state C (also referred as q2) is the final state.
 Construct a minimal DFA that accepts set of all strings over {a,b} of length 2 or less
ω ∊ {a,b} and ω <= 2
L = {ε,a,b,aa,ab,ba,bb}
Notes:
 For a language L you can draw many DFA diagrams, but there is only 1 minimal DFA.
The word "minimal" refers to the minimal number of states used.
 The language L is finite which means the FA is finite (= finite number of states).
 State A represents set of all strings of length 0.
 State B represents set of all strings of length 1.
 State C represents set of all strings of length 2.
 State D represents set of all strings of length 3 or more which will be rejected.
 If you have ε, always make the inital state a final state.
 This minimal DFA has 4 states and states A, B and C (respectively referred as q0, q1, q2) are the final states.
 Number of states required in a minimal DFA that accepts set of all strings with a certain length
In general a minimal DFA accept strings of length n requiring the following the number of states:
ω ∊ {a,b}
ω = n, number of states required: (n+2)
ω >= n, number of states required: (n+1)
ω <= n, number of states required: (n+2)
 Construct a minimal DFA that accepts set of all strings over {a,b}, where the length modulo 2 = 0
ω ∊ {a,b} and ω mod 2 = 0
L = {ε,aa,ab,ba,bb,aaaa,bbbb,...}
Notes:
 Even length strings satisfies the condition: ω mod 2 = 0
 ε is a string of length 0 and ε mod 2 = 0
 The language L is infinite, we do not know if the FA is finite or infinite.
By drawing the FA diagram there are a finite number of states which means this minimal DFA is finite.
 ω mod 2 = 0 can also be written as ω ≅ 0 (mod 2). The symbol ≅ means congruent.
 State A represents set of all strings of even lengths.
 State B represents set of all strings of odd lengths.
 This minimal DFA has 2 states and state A (also referred as q0) is the final state.
 Construct a minimal DFA that accepts set of all strings over {a,b}, where the length modulo 2 = 1
ω ∊ {a,b} and ω mod 2 = 1
L = {a,b,aaa,aab,...}
Notes:
 Odd length strings satisfies the condition: ω mod 2 = 1
 ε is a string of length 0 and does not satisfy condition ε mod 2 = 1
 The language L is infinite, we do not know if the FA is finite or infinite.
By drawing the FA diagram there are a finite number of states which means this minimal DFA is finite.
 ω mod 2 = 1 can also be written as ω ≅ 1 (mod 2). The symbol ≅ means congruent.
 State A represents set of all strings of even lengths.
 State B represents set of all strings of odd lengths.
 This minimal DFA has 2 states and state B (also referred as q1) is the final state.
 Construct a minimal DFA that accepts set of all strings over {a,b}, where the length modulo 3 = 0
ω ∊ {a,b} and ω mod 3 = 0
L = {ε,aaa,aab,aaaaaa,...}
Notes:
 Strings with lengths 0, 3, 6, 9, ... satisfies the condition: ω mod 3 = 0
 ε is a string of length 0 and does satisfy condition ε mod 3 = 0
 The language L is infinite, we do not know if the FA is finite or infinite.
By drawing the FA diagram there are a finite number of states which means this minimal DFA is finite.
 ω mod 3 = 0 can also be written as ω ≅ 0 (mod 3). The symbol ≅ means congruent.
 State A represents set of all strings of length 0, 3, 6, 9, ....
 This minimal DFA has 3 states and state A (also referred as q0) is the final state.
 Construct a minimal DFA that accepts set of all strings over {a,b}, where the length modulo 3 = 1
ω ∊ {a,b} and ω mod 3 = 1
L = {a,b,aaaa,aaab,...}
Notes:
 Strings with lengths 1, 4, 7, 10, ... satisfies the condition: ω mod 3 = 1
 ε is a string of length 0 and does not satisfy condition ε mod 3 = 1
 The language L is infinite, we do not know if the FA is finite or infinite.
By drawing the FA diagram there are a finite number of states which means this minimal DFA is finite.
 ω mod 3 = 1 can also be written as ω ≅ 1 (mod 3). The symbol ≅ means congruent.
 State B represents set of all strings of length 1, 4, 7, 10, ....
 This minimal DFA has 3 states and state B (also referred as q1) is the final state.
 How many states are in a minimal DFA that accepts set of all strings over {a,b}, where the length modulo n = 0
ω ∊ {a,b} and ω mod n = 0
Answer: The number of states is n
For example:
ω ∊ {a,b} and ω mod 2 = 0 > number of states = 2
ω ∊ {a,b} and ω mod 3 = 0 > number of states = 3
ω ∊ {a,b} and ω mod 4 = 0 > number of states = 4
ω ∊ {a,b} and ω mod 5 = 0 > number of states = 5
ω ∊ {a,b} and ω mod 6 = 0 > number of states = 6
:
 Construct a minimal DFA that accepts set of all strings over {a,b}, where the number of "a" are 2
ω ∊ {a,b} and n_{a}(ω) = 2
L = {aa,baa,aab,aba,aabb,bbaa,bbbaa,...}
Notes:
 The language L is infinite, we do not know if the FA is finite or infinite.
By drawing the FA diagram there are a finite number of states which means this minimal DFA is finite.
 State A represents set of all strings of length 0
 State B represents set of all strings of length 1
 State C represents set of all strings of length 2
 State D (dead state) represents set of all strings of length 3
 This minimal DFA has 4 states and state C (also referred as q2) is the final state.
 Construct a minimal DFA that accepts set of all strings over {a,b}, where the number of "a" are at least 2
ω ∊ {a,b} and n_{a}(ω) >= 2
L = {aa,aaa,baa,aab,aba,aaab,aabb,bbaa,bbbaa,aaabb,...}
Notes:
 The language L is infinite, we do not know if the FA is finite or infinite.
By drawing the FA diagram there are a finite number of states which means this minimal DFA is finite.
 State A represents set of all strings of length 0
 State B represents set of all strings of length 1
 State C represents set of all strings of length 2
 This minimal DFA has 3 states and state C (also referred as q2) is the final state.
 Construct a minimal DFA that accepts set of all strings over {a,b}, where the number of "a" is 2 or less
ω ∊ {a,b} and n_{a}(ω) <= 2
L = {ε,a,b,aa,ab,ba,bb,aab,aba,baa,aabb,aabbb,...}
Notes:
 The language L is infinite, we do not know if the FA is finite or infinite.
By drawing the FA diagram there are a finite number of states which means this minimal DFA is finite.
 State A represents set of all strings of length 0
 State B represents set of all strings of length 1
 State C represents set of all strings of length 2
 State D (dead state) represents set of all strings of length 3
 This minimal DFA has 4 states and state A, B and C (respectively referred as q0, q1 and q2) are the final states.
 Construct a minimal DFA that accepts set of all strings over {a,b}, where the number of "a" is even
ω ∊ {a,b} and n_{a}(ω) mod 2 = 0
L = {ε,b,aa,aab,aba,baa,aaaab,aababab,...}
Notes:
 The language L is infinite, we do not know if the FA is finite or infinite.
By drawing the FA diagram there are a finite number of states which means this minimal DFA is finite.
 n_{a}(ω) mod 2 = 0 can also be written as n_{a}(ω) ≅ 0 (mod 2). The symbol ≅ means congruent.
 State A represents set of all strings of length 0, 2, 4, 6, 8,... (even lengths)
 State B represents set of all strings of length 1, 3, 5, 7, 9,... (odd lengths)
 This minimal DFA has 2 states and state A (also referred as q0) is the final state.
 Construct a minimal DFA that accepts set of all strings over {a,b}, where the number of "a" is odd
ω ∊ {a,b} and n_{a}(ω) mod 2 = 1
L = {a,ab,abb,abaa,aaab,aabaaa,ababab,...}
Notes:
 The language L is infinite, we do not know if the FA is finite or infinite.
By drawing the FA diagram there are a finite number of states which means this minimal DFA is finite.
 n_{a}(ω) mod 2 = 1 can also be written as n_{a}(ω) ≅ 1 (mod 2). The symbol ≅ means congruent.
 State A represents set of all strings of length 0, 2, 4, 6, 8,... (even lengths)
 State B represents set of all strings of length 1, 3, 5, 7, 9,... (odd lengths)
 This minimal DFA has 2 states and state B (also referred as q1) is the final state.
 Construct a minimal DFA that accepts set of all strings over {a,b}, where the number of "a" modulo 3 = 0
ω ∊ {a,b} and n_{a}(ω) mod 3 = 0
L = {ε,aaa,aaba,aaab,aaabb,aaaaaa,...}
Notes:
 Strings with lengths 0, 3, 6, 9, ... satisfies the condition: n_{a}(ω) mod 3 = 0
 ε is a string of length 0 and does satisfy condition n_{a}(ω) mod 3 = 0
 The language L is infinite, we do not know if the FA is finite or infinite.
By drawing the FA diagram there are a finite number of states which means this minimal DFA is finite.
 n_{a}(ω) mod 3 = 0 can also be written as n_{a}(ω) 0 (mod 3). The symbol ≅ means congruent.
 State A represents set of all strings where the length of "a" are 0, 3, 6, 9, ....
 This minimal DFA has 3 states and state A (also referred as q0) is the final state.
 Which state is the final state in a minimal DFA with N states that accepts set of all strings over {a,b}, where the number of "a" modulo N = k
ω ∊ {a,b} and n_{a}(ω) mod N = k and N = number of states
Answer:
Number of states = N and ω ∊ {a,b} and n_{a}(ω) mod N = k > final state = qk
Number of states = N and ω ∊ {a,b} and n_{a}(ω) mod N = 0 > final state = q0
Number of states = N and ω ∊ {a,b} and n_{a}(ω) mod N = 1 > final state = q1
Number of states = N and ω ∊ {a,b} and n_{a}(ω) mod N = 2 > final state = q2
Number of states = N and ω ∊ {a,b} and n_{a}(ω) mod N = 3 > final state = q3
:
For example:
Number of states = 3 and k = 2
ω ∊ {a,b} and n_{a}(ω) mod 3 = 2
L = {aa,aaaaa,aaaaaaaa,aabb,baaaaa,...}
Final state = q2
For example:
Number of states = 4 and k = 1
ω ∊ {a,b} and n_{a}(ω) mod 4 = 1
L = {a,aaaaa,aaaaaaaaa,ab,aabaaa,...}
Final state = q1
