Theory of Computation

• Make SURE you appreciate the equivalence of the following
  
  
  • p => q
  • ~p v q
  • q v ~p
  • ~(~q) v ~p
  • ~q => ~p
  
  Consider for example, the conditional statement "if you are taking CS 139, then you are learning about automata." This means the same thing as "either you are not take CS 139 or you are learning about automata (or both)." That doesn't necessarily feel comfortable at first, but you must get used to it! The conditional statement will be true if you are not taking CS 139, regardless of whether or not you are learning about automata. (This is perhaps because it is generally agreed that propositions are true unless they have to be false. If you aren't taking CS 139, anything I assert predicated on the condition that you are is true!) On the other hand, the conditional statement will be true provided that you are learning about automata, regardless of whether or not you are taking CS 139. That's it. But let's consider the contrapositive: "if you are not learn about automata, then you are not taking CS 139." This is logically equivalent to the original conditional statement.
  
  
• I want to show you the most direct proof by induction that Letzter and I could come up for the "graph theorem." Here goes:
  
  Theorem: For any natural number n, any connected graph with precisely n vertices has at least n-1 edges.
  
  Proof. Clearly OK when n = 1. Now suppose true for some particular natural number k (i.e. n=k). We need to show that from this assumption it would necessarily also be true when n = k+1. To do so we need to consider an arbitrary connected graph G with k+1 vertices. From a HW assignment we know that G has at least one vertex v whose removal yields a connected graph H (with k vertices). Note that k is at least one, so H is not the empty graph. From our assumption (the "inductive hypothesis"), H must have at least k-1 edges. Going back to G, we know that G has at least one edge incident with v. This edge is not part of H. So G has at least k edges (=1+(k-1)). Good. We have thus established that if we're OK for n=k, then we are also OK for n=k+1. (Using formal notation used in class, P(k) => P(k+1).) By the Principal of Mathematical Indication, the theorem now follows (for all natural numbers n, P(n)). []
  
  
• Here is my solution to a HW exercise. You were essentially asked to prove that in any connected graph there is always at least one vertex whose removal keeps the resulting graph connected. Here is my proof:
  
  Suppose this is false. Let G be a minimal counter-example. That is, let G be a connected graph with as few vertices as possible such that the removal of any of these vertices disconnects the graph. Now, let v be a vertex of G whose removal produces a connected component with as few vertices as possible (as per my hint). Let H be this connected component. Since H has fewer vertices than G, it must contain a vertex u whose removal from H results in a connected graph K. Now consider K as part of G. Is it possible that no vertex in K is adjacent to v? If this were so, then K would be directly connected (by at least one edge) to u, u would be adjacent to v, and v would be connected to the rest of G, but there would be NO other edges. Picture:
  

          K ====== u ------- v ======= (rest of G) 
  

  Here "=======" means one or more edges while "-------" represents a single edge. But this situation contradicts our choice of v, since removing u from G would produce a smaller connected component, namely K. Therefore, there must be some edges connecting K directly to v. It is then clear that by removing u, we would still have a connected graph. Picture:
  

   
          K ====== v ======= (rest of G) 
  

  This is a contradiction. So the original claim (theorem) has been established.

• I will write "d" in place of "delta",
• and I will write "dh" in place of "delta hat,"
• and I will write "e" for "epsilon,"
• and I will write "s" for "sigma,",
• and I will write "t" for "tau."

• q is in dh(q,e);
• if q' is in d(q,e) then q' is in dh(q,e);
• if q' is in dh(q,e) and q'' is in dh(q',e) then q'' is in dh(q,e);
• dh(q,e) is as small as possible subject to the above three requirements;
• if s is a symbol and q' is in d(q,s), then q' is in dh(q,s);
• if q' is in dh(q,s) and q'' is in dh(q',t) then q'' is in dh(q,st);
• dh(q,s) is as small as possible subject to the above requirements.

• Consider an NFA with states A, B and C. Let's say that on input 0, the following transitions are possible: A->A , A->B , C->B and C->C . Let's say that on input 1, the following transitions are possible: A->C, B->A, B->C . Let's say that A is starting and accepting and that C is also accepting. (Stop and draw the state diagram for this.)
  
  The subset construction produces a DFA with the same language, but 8 states labeled using the 8 subsets of {A,B,C}. Here are the transitions on a 0 input:

      {}      ->   {} 
      {A}     ->   {A,B} 
      {B}     ->   {} 
      {C}     ->   {B,C} 
      {A,B}   ->   {A,B} 
      {A,C}   ->   {A,B,C} 
      {B,C}   ->   {B,C} 
      {A,B,C} ->   {A,B,C} 
  

  
  Here are the transitions on a 1 input:

   
      {}      ->   {} 
      {A}     ->   {C} 
      {B}     ->   {A,C} 
      {C}     ->   {} 
      {A,B}   ->   {A,C} 
      {A,C}   ->   {C} 
      {B,C}   ->   {A,C} 
      {A,B,C} ->   {A,C} 
  

  
  The starting state is of course {A}. The only non-accepting states are {} and {B}, because the others have either A or C as part of their label. Notice that being in the state {A,B} in the DFA is like saying "I could be in state A or B in the NFA." From here an input or 1 takes you to {A,C} because in the NFA you can go from A to C or from B to A or from B to C.
  
  
• We also considered the language that consists of all binary strings except 11. But this is the complement of the language { 11 } , complementing in the language of all binary strings, that is, {0,1}^*. It is possible to make a 4-state DFA whose language is { 11 } . Then just reverse which states accept and which do not, and you have a DFA whose language is the desired language. We need to use a DFA, not an NFA here, right?
  
  
• Let's try another example. Say L₁ is the language of binary strings that begin and end with a 1. Say L₂ is the language of binary strings that have an odd number of 1's. Here are two DFAs for these languages, as you will no doubt check for yourself:
  
  
  Let's now draw the "Cartesian product" of these two automata, but ignore accepting states for now. We get the following, as you should be able to check:
  
  
  Notice that I did not indicate accepting states here. First get comfortable with the idea that each state here is keeping track of a pair of states, one from the first automaton, and one from the second. The states in the top (bottom) row correspond to an even (odd) number of ones. Notice that the state in the bottom-left position is unreachable from the start state. It can be removed, although it is part of the Cartesian product construction.
  
  Now figure out which state(s) should accept if you want the language to be the intersection of the original two languages. Then decide again if you want the language to be the union instead of the intersection.
  
  

 
Title: Capillary surfaces and their behaviors in cylinders

Speaker: Dr. Kirk Lancaster, Professor of Mathematics, Wichita State University

Date and time: Wednesday, February 22, 3:30 pm Location: Howard Hall 308

Following the talk, Prof. Lancaster will be available to talk with students who are thinking about graduate school.

Abstract: Capillary surfaces are ubiquitous: a drop on your windshield, the sap in a tree, the fuel in a spaceship, fluid in a cylinder, etc. 
Capillary phenomena occur as the result of an interaction of surface tension, exterior force fields (e.g. gravity) and the attraction of fluids
to surfaces (i.e. "wetting energies"). In a microgravity environment such as in free fall or at very small scales such as occurs in nanoscale
fabrication, the influence of gravity becomes largely insignificant and the interaction of surface tension and surface chemistry becomes
dominant in determining the shapes of stationary liquids.

Special types of capillary surfaces can be of great interest; some examples are hanging drops ("pendant drops"), drops on a surface ("sessile
drops"), liquid bridges, fluids in a vertical cylinder and fluids in a container.  When the container is not smooth (e.g. has edges or
corners), determining the behavior or shape of a capillary surface in the container can be problematic.  I will consider capillary surfaces in
a vertical cylinder whose cross-section has a corner P. In this case, the capillary surface will be a graph z=f(x,y) over the cross-section and
the function f may be discontinuous at P; this problem has been investigated by a variety of researchers.  When the cross-section has a convex
(or protruding) corner at P, Paul Concus and Robert Finn made a conjecture approximately 14 years ago that under certain conditions, f must be
discontinuous at P. I will describe the behavior of capillary surfaces z=f(x,y) near P when f is discontinuous at P and give a very brief
outline of my recent proof of the Concus-Finn Conjecture.  I will also discuss examples. 

• For simplicity, you may assume that the input file has exactly one number per line.
• You should write the completelyReduce function and you should arrange for it to eliminate the original states (but not the new start nor the new accept state) in increasing numeric order.
• You guys should let me (the user) specify the name of the file containing the data.

• Here is how things should be to begin with (see bottom of this message):

   
            RegExpr[0][0] = "e"
            RegExpr[0][1] = "e"
            RegExpr[0][2] = "p"
            RegExpr[0][3] = "p"
            RegExpr[0][4] = "p"
            RegExpr[0][5] = "p"
            RegExpr[1][0] = "p"
            RegExpr[1][1] = "e"
            RegExpr[1][2] = "2"
            RegExpr[1][3] = "2"
            RegExpr[1][4] = "p"
            RegExpr[1][5] = "e"
            RegExpr[2][0] = "p"
            RegExpr[2][1] = "p"
            RegExpr[2][2] = "e"
            RegExpr[2][3] = "p"
            RegExpr[2][4] = "p"
            RegExpr[2][5] = "e"
            RegExpr[3][0] = "p"
            RegExpr[3][1] = "p"
            RegExpr[3][2] = "p"
            RegExpr[3][3] = "1"
            RegExpr[3][4] = "1|2|e"
            RegExpr[3][5] = "p"
            RegExpr[4][0] = "p"
            RegExpr[4][1] = "2"
            RegExpr[4][2] = "p"
            RegExpr[4][3] = "e"
            RegExpr[4][4] = "e"
            RegExpr[4][5] = "p"
            RegExpr[5][0] = "p"
            RegExpr[5][1] = "p"
            RegExpr[5][2] = "p"
            RegExpr[5][3] = "p"
            RegExpr[5][4] = "p"
            RegExpr[5][5] = "e"
            

• After eliminating state 1:

            RegExpr[0][0] = e
            RegExpr[0][2] = 2
            RegExpr[0][3] = 2
            RegExpr[0][4] = p 
            RegExpr[0][5] = e 
            RegExpr[2][0] = p 
            RegExpr[2][2] = e
            RegExpr[2][3] = p 
            RegExpr[2][4] = p 
            RegExpr[2][5] = e 
            RegExpr[3][0] = p 
            RegExpr[3][2] = p 
            RegExpr[3][3] = 1 
            RegExpr[3][4] = 1|2|e 
            RegExpr[3][5] = p
            RegExpr[4][0] = p 
            RegExpr[4][2] = 22 
            RegExpr[4][3] = e|22
            RegExpr[4][4] = e
            RegExpr[4][5] = 2
            RegExpr[5][0] = p 
            RegExpr[5][2] = p  
            RegExpr[5][3] = p  
            RegExpr[5][4] = p  
            RegExpr[5][5] = e
       

• After eliminating state 2:

            RegExpr[0][0] = e
            RegExpr[0][3] = 2
            RegExpr[0][4] = p
            RegExpr[0][5] = e|2
            RegExpr[3][0] = p 
            RegExpr[3][3] = 1
            RegExpr[3][4] = 1|2|e  
            RegExpr[3][5] = p
            RegExpr[4][0] = p 
            RegExpr[4][3] = e|22 
            RegExpr[4][4] = e
            RegExpr[4][5] = 2|22  
            RegExpr[5][0] = p
            RegExpr[5][3] = p  
            RegExpr[5][4] = p  
            RegExpr[5][5] = e
       

• After eliminating state 3:

            RegExpr[0][0] = e
            RegExpr[0][4] = 21*(1|2|e)
            RegExpr[0][5] = e|2
            RegExpr[4][0] = p  
            RegExpr[4][4] = (e|22)1*(1|2|e)
            RegExpr[4][5] = 2|22  
            RegExpr[5][0] = p
            RegExpr[5][4] = p  
            RegExpr[5][5] = e 
       

• After eliminating state 4:

            RegExpr[0][0] = e
            RegExpr[0][5] = e|2|21*(1|2|e)((e|22)1*(1|2|e))*(2|22) 
            RegExpr[5][5] = e
       

  
  

•       4 -2 2 8 1 2 2 1 3 2 3 3 1 3 4 1 3 4 2 4 1 2 3 4 0 4 3 0
•       3 -1 2 6 1 2 1 2 3 1 3 1 1 2 1 2 3 2 2 1 3 2
•       2 1 1 1 1 2 1

•       e|2|21*(1|2|e)((e|22)1*(1|2|e))*(2|22)
•       e|1(e|21)*2|(2|1(e|21)*(1|22))(e|12|(2|11)(e|21)*(1|22))*1|(2|11)(e|21)*2
•       1

• 4. L = { a^mbⁿc^m   |   m, n >= 3 }
• 5. L = { ww   |   w in {0,1}^* }
• 6. L = { www   |   w in {0,1,2}^* }
• 7. L = { 0w1w   |   w in {0,1}^* }
• 8. L = { wtw^REV   |   w, t in {0,1}^* }
• 9. L = { sigma in {a,b,c}^*   |   each of the three letters (a,b,c) occurs the same number of times in sigma, and no letter is immediately repeated in sigma }