Construction of minimal DFA and cross product of DFA
Information on this page based on:
YouTube: Theory Of Computation 3, Construction of DFA and cross product of DFA
YouTube: Theory Of Computation 4, DFA and problem
 Construct a minimal DFA that accepts set of all strings over {a,b} in which number of a's and b's are even
ω ∊ {a,b} and n_{a}(ω) mod 2 = 0 && n_{b}(ω) mod 2 = 0
L = {ε,aa,bb,aabb,abab,baba,aaaa,bbbb,...}
Notes:
 ε is a string of length 0 and does satisfy condition n_{a}(ω) mod 2 = 0 and n_{b}(ω) 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.
 n_{a}(ω) mod 2 = 0 can also be written as n_{a}(ω) 0 (mod 2).
n_{b}(ω) mod 2 = 0 can also be written as n_{b}(ω) 0 (mod 2).
The symbol ≅ means congruent.
 The strings are divided in four classes: "ee", "eo", "oe" and "oo".
 This minimal DFA has 4 states and state "ee" (also referred as q0) is the final state.
 Construct a minimal DFA that accepts set of all strings over {a,b} in which number of a's and b's are even using cross product
ω ∊ {a,b} and n_{a}(ω) mod 2 = 0 && n_{b}(ω) mod 2 = 0
Counting a's
L = {ε,aa,aaaa,aaaaaa,...}
Counting b's
L = {ε,bb,bbbb,bbbbbb,...}
Cross product (combining a's and b's)
Multiply the states {A,B} with {C,D}: {A,B} x {C,D} = {AC,AD,BC,BD}
The cross product consists of 4 states.
In counting a's, state A is the initial state.
In counting b's, state C is the initial state.
AC is the initial state of the 4 states.
Determine the transition for each state (AC,AD,BC,BD) and for each input (a,b)
 State AC and input a
Counting a's DFA diagram: A > a > B
Counting b's DFA diagram: C > a > C
Result: AC> a > BC
 State AC and input b
Counting a's DFA diagram: A > b > A
Counting b's DFA diagram: C > b > D
Result: AC> b > AD
 State BC and input a
Counting a's DFA diagram: B > a > A
Counting b's DFA diagram: C > a > C
Result: BC> a > AC
 State BC and input b
Counting a's DFA diagram: B > b > B
Counting b's DFA diagram: C > b > D
Result: BC> b > BD
 State BD and input a
Counting a's DFA diagram: B > a > A
Counting b's DFA diagram: D > a > D
Result: BD> a > AD
 State BD and input b
Counting a's DFA diagram: B > b > B
Counting b's DFA diagram: D > b > C
Result: BD> b > BC
 State AD and input a
Counting a's DFA diagram: A > a > B
Counting b's DFA diagram: D > a > D
Result: AD> a > BD
 State AD and input b
Counting a's DFA diagram: A > b > A
Counting b's DFA diagram: D > b > C
Result: AD> b > AC
For each state add ee,eo,oe and ee:
e 
and 
e 
{ee} 
e 
and 
o 
{eo} 
o 
and 
e 
{oe} 
o 
and 
o 
{oo} 
e 
or 
e 
{ee,eo,oe} 
e 
or 
o 
{ee,eo,oo} 
o 
or 
e 
{ee,oe,oo} 
o 
or 
o 
{oe,eo,oo} 
If counting a's DFA diagram has m number of states and counting b's DFA diagram has n number of states
the cross product m x n will have mxn states.
