Decision algorithms and review

 Decision algorithms for regular sets:
  Remember: An algorithm must always terminate to be called an algorithm!
            Basically, an algorithm needs to have four properties
            1) It must be written as a finite number of unambiguous steps 
            2) For every possible input, only a finite number of steps
               will be performed, and the algorithm will produce a result
            3) The same, correct, result will be produced for the same input
            4) Each step must have properties 1) 2) and 3)

  Remember: A regular language is just a set of strings over a finite alphabet.
            Every regular set can be represented by an regular expression
            and by a minimized finite automata, a DFA.

  We choose to use DFA's, represented by the usual  M=(Q, Sigma, delta, q0, F)
  There are countably many DFA's yet every DFA we look at has a finite
  description. We write down the set of states Q, the alphabet Sigma,
  the transition table delta, the initial state q0 and the final states F.
  Thus we can analyze every DFA and even simulate them.

  Theorem:  The regular set accepted by DFA's with n states:
   1) the set is non empty if and only if the DFA accepts at least one string
      of length less than n.  Just try less than |Sigma|^|Q| strings (finite) 
   2) the set is infinite if and only if the DFA accepts at least one string
      of length k,  n <= k < 2n.  By pumping lemma, just more to try (finite)

  Rather obviously the algorithm proceeds by trying the null string first.
  The null string is either accepted or rejected in a finite time.
  Then try all strings of length 1, i.e. each character in Sigma.
  Then try all strings of length 2, 3, ... , k. Every try results in
  an accept or reject in a finite time.

  Thus we say there is an algorithm to decide if any regular set
  represented by a DFA is  a) empty,  b) finite  and  c) infinite.

  The practical application is painful! e.g. Given a regular expression,
  convert it to a NFA, convert NFA to DFA, use Myhill-Nerode to get
  a minimized DFA. Now we know the number of states, n, and the alphabet
  Sigma. Now run the tests given in the Theorem above.