September 22

* Example of the conceptual power of nondeterminism

  Let L be a language.  Define 1/2(L) to be
     {x: for some y such that |x| = |y|, xy is in L}.

  1/2(L) is the set of first halves of strings in L.  Prove that for each
     regular L, 1/2(L) is regular.
 
  Proof:  Let M be a DFA for L.  M' will be an NFA constructed to accept 1/2(L).
  M' uses the "finger method" as follows.
  M' places the left finger on s in M, and the right finger on s_i in M
     where s_i is a nondeterministic "guess" as to where input x will lead.

  As aharacters of x are read, M' moves the left finger along transitions
     as dictated by characters read, and simultaneously moves the right finger
     along a nondeterministically chosen edge (which may be labeled with any
     character, not necessarily the one of x being read).

  M' accepts x iff at the end its left finger is on s_i and
     its right finger is on the accept state.
  Thus M' accepts x iff
     * x leads to some state s_i in M, and
     * there exists y |y| = |x| s.t. y leads from s_i to an accept state in M.

  Formally:

     Use tuple for fingers (we need a middle finger to remember
	the guessed s_i state).

     M' = (K', Sigma, delta', s', F'), where
	K' = K_{left finger} x K{middle finger} x K{right finger} and
	s in K = new start state

	* delta'(s, epsilon) = {: si in S}
	  "Guess" the state si to which input x will lead

	* delta'(, a) =
	  {: delta(si, a) = sl and
	  there exists b in Sigma s.t. delta(sk, b) = sm}
	  Note that the middle finger does not change after the initial guess

     F' = {:  si in S, sj in F}

     As you can see, the left finger moved on input x to where the
     middle finger guessed (si, si).  The right finger moved from si
     to some accepting state sj of M (si, sj).


* RE -> NFAs with epsilon-transitions

  Theorem:  Forall regular expressions r, construct NFA M L(M) = L(r).

  Proof:  By induction on the number of operations in r we show there exists an
  NFA with one final state for L(r).

  Base Case:  Number of operations = 0.  r is either
                               +-+   +===+
     empty,      so NFA is   ->| |   || ||
                               +-+   +===+

                               +===+
     epsilon,    so NFA is   ->|| ||
                               +===+

                               +-+ a +===+
     a in Sigma, so NFA is   ->| |-->|| ||
                               +-+   +===+


   Inductive Hypothesis:  Assume property holds for r defined with <=n
      operations.

   Inductive Step:  Prove property then holds for r = n+1 operations.
   In this case there exist r1, r2 defined using <=n operations each such
   that r is one of (r1r2), (r1 v r2), or (r1*).

   Let M1, M2 be NFAs with one final state accepting r1 and r2 respectively
   (by inductive hypothesis M1 and M2 exist).  Your homework assignment will
   be used to complete the inductive step.


* DFA -> RE 

  Theorem:  Given a DFA M = (K, Sigma, delta, s1, F), construct a regular
     expression r for L(M).

  Proof:

     Let R_{i j}^{k} = strings leading from si to sj that do not pass through
	any states numbered > k (although they may begin or end at one).

    Assume K = {s1, ..., sn}.

    Then R_{ij}^{n} = strings leading from si to sj and
       if F = {sj_1, sj_2, ..., sj_s}
       then L(M) = R_{1 j1}^{n} union R_{1 j2}^{n} union ... union R_{1 js}^{n}.

       L(M) = all ways to get to final states with paths that do not pass
	  through any states numbered higher than n.

    Lemma.  Forall i, j, k there exists regular expression
	       r_{ij}^{k} s.t. L(r_{ij}^k) = R_{ij}^k

    The theorem follows from the lemma.

    L(M) = R_{1 j1}^n union R_{1 j2}^n union ... union R_{1 js}^n
	 = L(r_{1 j1}^n) union ... union L(r_{1 js}^n)
	 = L(r_{1 j1}^n v r_{1 j2}^n v ... v r_{1 js}^n), which is
	 a regular expression for L(M)

    Now we will proof the lemma.

    Note that +-----       +---
	      | R_{ij}^0 = | a: delta(s_i, a) = s_j           if i neq j
	      |            | a: delta(s_i, a) = s_j union e   if i = j
	      |            +---
	      | R_{ij}^k = R_{ij}^k-1 union R_{ik}^k-1(R_{kk}^k-1)*R_{kj}^k-1
	      +-----

	      How do we transition from i to j without going through states
	      higher than k?
	      Either by transitioning from i to j without going through states
	      higher than k-1, or
	      by transitioning from i to k without going through states higher
	      than k-1 followed by
	      transitioning from k to k in one move without going through states
	      higher than k-1 followed by
	      transitioning from k to j without going through states higher
	      than k-1.

     +------------------------------------+
     |                                    |
     |                                    |<- States > k
     |                                    |
     +----------------S_k-----------------+<- States = k
     |               ^| ^^                |
 S_1----->O==========++-+|                |<- States < k
     |                   |                |
     |                   v                |---> means one move
     |            +======O                |===> means a finite sequence of moves
     +------------|-----------------------+
                  v
                 S_j

     We will prove the lemma by induction on k using the note.

     Base Case:  Let k = 0.  By the first part of the note,
	R_{ij}^0 <= Sigma union e and thus there exists a simple regular
	expression for the finite set (the union of individual symbols and/or e)

     Inductive Hypothesis:  Assume forall i, j that r_{ij}^k-1 is a regular
	expression for R_{ij}^k-1.

     Inductive Step:  Prove that there exists re for R_{ij}^k.
	By the second part of the note,
	R_{ij}^k = R_{ij}^k-1 union R_{ik}^k-1(R_{kk}^k-1)*R_{kj}^k-1
		= L(r_{ij}^k-1) union L(r_{ik}^k-1)(L(r_{kk}^k-1))*L(r_{kj}^k-1)
		= L(r_{ij}^k-1 v r_{ik}^k-1(r{kk}^k-1)*r_{kj}^k-1).
		Because each of the rs are re, the entire equation is a re.


* Example

   1                1
  +--+            +----+
  v  |     0      v    | 
  +--+----------->+====+
  |s1|     0      ||s2||
  +--+<-----------+====+

  L(M) = L(r_{12}^2)

  r_{12}^2 = r_{12}^1                v r_{12}^1(r_{22}^1)*r_{22}^1

	   = r_{12)^0 v r_{11}^0(r_{11}^0)*r_{12}^0
	     v r_{12)^0 v r_{11}^0(r_{11}^0)*r_{12}^0(r_{22}^1)*r_{22}^1

	   = r_{12)^0 v r_{11}^0(r_{11}^0)*r_{12}^0
	     v r_{12)^0 v r_{11}^0(r_{11}^0)*r_{12}^0
	       (r_{22}^0 + r_{21}^0(r_{11}^0)*r_{12}^0)+

   We know that r_{11}^0 = r_{22}^0 = 1 v e
	        r_{12}^0 = r_{21}^0 = 0

	   = 0 v (1 v e)+0 v (0 v (1 v e)+0)[(1 v e) v 0(1 v e)*0]+

	   = (0 v (1 v e)+ 0)[1 v e v 0(1 v e)*0]+

	   = (0 v (1 v e)+ 0)[1 v e v 01*0]*

	   = (1 v e)*0(1 v e v 01*0)*

	   = 1*0(1 v 01*0)*