# Theory of computation

The theory of computation is mathematically model a machine (for example a computer) and study the theory about it which means what are the problems which would be solved by this machine, what are the limitations of the machine etc.

More information about this subject can be found at: YouTube: Theory of Computation or Automata Theory by Gate Lectures by Ravindrababu Ravula

Based on these YouTube movies, notes have been made which you can find on this page.

## Construction of minimal DFA and cross product of DFA

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 na(ω) mod 2 = 0 && nb(ω) mod 2 = 0

L = {ε,aa,bb,aabb,abab,baba,aaaa,bbbb,...}

Notes:
• ε is a string of length 0 and does satisfy condition na(ω) mod 2 = 0 and nb(ω) 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.
• na(ω) mod 2 = 0 can also be written as na(ω) 0 (mod 2).
nb(ω) mod 2 = 0 can also be written as nb(ω) 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 na(ω) mod 2 = 0 && nb(ω) 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:

 a's logical operator b's final states 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.