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

Ravindrababu Ravula has created more than 70 excellent YouTube movies about this subject.
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


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

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

    DFA example 17

    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,...}

    DFA example 18

    Counting b's

    L = {ε,bb,bbbb,bbbbbb,...}

    DFA example 19

    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.

    DFA example 20

    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

    DFA example 21

    For each state add ee,eo,oe and ee:

    DFA example 22

    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.