DFA and regular expressions

 Example of a Deterministic Finite Automata, DFA


 Machine Definition  M = (Q, Sigma, delta, q0, F)
 Q = { q0, q1, q2, q3, q4 } the set of states (finite)
 Sigma = { 0, 1 }           the input string alphabet (finite)
 delta                      the state transition table - below
 q0 = q0                    the starting state
 F = { q2, q4 }             the set of final states (accepting
                            when in this state and no more input)

                          inputs
   delta          |    0    |    1    |
         ---------+---------+---------+
              q0  |   q3    |   q1    |
              q1  |   q1    |   q2    |
    states    q2  |   q2    |   q2    |
              q3  |   q4    |   q3    |
              q4  |   q4    |   q4    |

              ^       ^         ^
              |       |         |
              |       +---------+-- every transition must have a state
              +-- every state must be listed

  An exactly equivalent diagram description for the machine M.
  Each circle is a unique state. The machine is in exactly one state
  and stays in that state until an input arrives. Connection lines
  with arrows represent a state transition from the present state
  to the next state for the input symbol(s) by the line.

 L(M) is the notation for a Formal Language defined by a machine M.
 Some of the shortest strings in L(M) = { 00, 11, 000, 001, 010, 101, 110,
 111, 0000, 0001, 0010, 0011, 0100, 0101, 0110, 1001, ... }

 In words, L is the set of strings over { 0, 1} that contain at least
 two 0's starting with 0, or that contain at least two 1's starting with 1.

 Every input sequence goes through a sequence of states, for example
  00   q0 q3 q4
  11   q0 q1 q2
  000  q0 q3 q4 q4
  001  q0 q3 q4 q4
  010  q0 q3 q3 q4
  011  q0 q3 q3 q3
  0110 q0 q3 q3 q3 q4

Rather abstract, there are tens of millions of DFA being used today. 

 Definition of a Regular Expression
                 ------------------
  A regular expression may be the null string,
     r = epsilon

  A regular expression may be an element of the input alphabet, sigma,
     r = a

  A regular expression may be the union of two regular expressions,
     r = r1 + r2

  A regular expression may be the concatenation (no symbol) of two
  regular expressions,
     r = r1 r2

  A regular expression may be the Kleene closure (star) of a
  regular expression
     r = r1*    (the asterisk should be a superscript,
                 but this is plain text)

  A regular expression may be a regular expression in parenthesis
     r = (r1)

  Nothing is a regular expression unless it is constructed with only the
  rules given above.

  The language represented or generated by a regular expression is a
  Regular Language, denoted L(r).

  The regular expression for the machine M above is
    r = (1(0*)1(0+1)*)+(0(1*)0(0+1)*)

  Later we will give an algorithm for generating a regular expression from
  a machine definition.  For simple DFA's, start with each accepting
  state and work back to the start state writing the regular expression.
  The union of these regular expressions is the regular expression for
  the machine.

  For every DFA there is a regular language and for every regular language
  there is a regular expression. Thus a DFA can be converted to a
  regular expression and a regular expression can be converted to a DFA.

Given a DFA and one or more strings, determine if the string(s)
are accepted by the DFA. This may be error prone and time
consuming to do by hand. Fortunately, there is a program
available to do this for you.

On linux.gl.umbc.edu  do the following:

  ln -s /afs/umbc.edu/users/s/q/squire/pub/dfa dfa
  cp    /afs/umbc.edu/users/s/q/squire/pub/download/ab_b.dfa .
  dfa < ab_b.dfa    # or  dfa < ab_b.dfa > ab_a.out

Practical definition of a DFA

Here, we start with the state diagram:



From this we see the states Q = {
  Off, Starting forward, Running forward,
  Starting reverse, Running reverse }

The alphabet (inputs) Sigma = {
  off request,
  forward request,
  reverse request,
  time-out }

The initial state would be Off.

The final state would be Off.

The state transition table, Delta,is obvious yet very wordy.

Note: that upon entering a state, additional actions may be specified.
Inputs could be from buttons, yet could come from a computer.