Class 10: Finishing Proof, Starting Nondeterministic Finite Automata


Reading
These lecture notes!
Homework
Consider the machine M defined below (Note: e means the empty string here!):

Write down a sequence of configurations in which this machine starts with cbcaa and
  1. reads all input and ends in an accepting state
  2. reads all input and ends in a non-accepting state
  3. gets stuck before it gets all the input read
Make sure you read the lecture notes below so you understand the problem!

An example of a formal proof of correctness for an algorithm
(Continuing from last class ...) We're going to prove that the algorithm we went through in the last class really does what we said it did.

Algorithm 1-String
Input: alphabet Σ, and string w ∈ Σ*, where w = a1a2...an
Output: ({0,1,...,n+1},Σ,δ,1,{n+1}), where
δ:{0,1,...,n+1} x Σ &rarr {0,1,...,n+1}
δ(k,a) = { k+1 if 0 < k ≤ n and a = ak
0 otherwise

Claim: Algorithm 1-String produces a machine that accepts w and rejects every other string in Σ*.

Proof: We have two things to prove: first that M accepts w, and second that M rejects everything else. To be technically correct, all of this stuff needs to be proved by induction. We'll do it more informally here, though, so you get the drift without getting lost in the details. Note: If you're planning to go to grad school, you'll probably have to do these things by induction with all the gory details.

M accepts w
This is pretty easy, because we can list out each step of the computation and verify that δ yields what I say it does.
(1,a1a2...an) ⇒ (2,a2a3...an) ⇒ (3,a3a4...an) ⇒ ... ⇒ (n-1,an-1an) ⇒ (n,an) ⇒ (n+1,e)
So each step is correct according to the definition of δ, and the state we end up in is indeed an accepting state.

w is the only string M accepts
What we'll do is show that if M accepts a string it must be w. How? Well, let's look at an accepting computation and see what we can deduce: Suppose the following is an accepting computation:
(q1,w1) ⇒ (q2,w2) ⇒ ... ⇒ (qm,wm)
i.e. (qm,wm) = (n+1,e) and q1 = 1. Since (qm-1,wm-1) ⇒ (qm,wm) = (n+1,e) the definition of δ says that qm-1 must be n and wm-1 must be am. So, the last character in the string is an and the second to last state in the computation is n. You keep tracing the computation backwards and you end up building up the original string w1 from back to front. What you find is that w1 is w.
QED

A note about degrees of "proof"
(Repeating from last class ...) We professors tend to act as if something either is a "proof" or it's not. In fact, there are degrees of proof --- or perhaps more accurately there are degrees pickiness. Do you provide precise details of everything, or do you gloss over these details. In this class there tends to be two levels of proof: the higher level, or "bigger picture" type of proof is like our algorithms. The lower level, nitpickier type also provides correctness proofs for the algorithms. Even in the nitpickier level, there's degrees: do I go all out with induction, or do I sketch out the arguments like I did in the above example?

The most sincere comment I can make about degrees of proof is this: when you're really convinced, that's enough detail. This, of course, requires that you are sincere in evaluating when you're convinced. Hopefully, with the algorithms we've done so far you were convinced when you truly understood how the algorithm worked. Further proof, like the one above, probably seemed pointless. That's why I'm going to put most of the emphasis on the higher level view of understanding the algorithms. However, be aware that it's easy to convince yourself of things that aren't true, so there is value in getting down to all the details and working out every last one. When that's been done, you're really sure.

Let's be lazy and sloppy ... part 1
Suppose we allow ourselves to be a little sloppy and lazy in how we define machines. Can we still make sense of things? For example, what about the following machine, M1:

It's not a proper deterministic finite automaton, because it has no transitions from q0 for characters a or b. On the other hand, it's pretty easy to figure out what I mean. If you ever encounter a "missing" transition, just reject the string! We've been putting "error" states or "trap" states to do the same kind of thing. At any rate, we can be lazy and sloppy this way, and still make sense of the machine.

Now, what does this machine do? It accepts the language of all strings over {a,b,c} that start with a c and have an even number of a's and b's.

Let's be lazy and sloppy ... part 2
Suppose we allow ourselves to be a little sloppier and lazier. For example, I want a machine that accepts the same language as accepted by M1, but with the additional requirement that all strings must end with c as well as begin with c. I might modify M1 to get the machine M2:

This is really not a proper finite automaton --- even if we allow the sloppy practice of leaving out transitions. Why? Because now we have two transitions for state q1 and symbol c. This isn't allowed, and for a very good reason: now the computation is ambigous. Where do I go when I read a c in state q1. For example, for input cacbcc I have three possible computations:
(q0,cacbcc) => (q1,acbcc) => (q2,cbcc) => (q2,bcc) => (q1,cc) => (q1,c) => (q1,e)
(q0,cacbcc) => (q1,acbcc) => (q2,cbcc) => (q2,bcc) => (q1,cc) => (q1,c) => (q2,e)
(q0,cacbcc) => (q1,acbcc) => (q2,cbcc) => (q2,bcc) => (q1,cc) => (q2,c) => stuck
Only the second of these actually accepts the string (which, by my description, we'd really like to accept). So, computation by a machine like this is non-deterministic, i.e. we can't tell exactly what the computation will be for every input. Still, can we come up with a sensible definition of what strings such a machine accepts and what strings it rejects? How about this:
A non-deterministic finite automaton accepts a string if there is a way for it to end up in an accepting state. Only if there is no way for it to end up in an accepting state does it reject its input string. Another way to view this is to say that the machine always makes lucky guesses about which transition to take when there is more than one possiblity.
This is a definition that makes sense for M2, and would makes sense for any non-deterministic machine. Now, to tidy up a bit we have to admit that M2 doesn't do exactly what it's supossed to, because it doesn't accept the string c, which is indeed a string that starts and ends with c and contains an even number of a's and b's. The following machine, M3, fixes this:

Let's be lazy and sloppy ... part 3
Consider the machine M4:

This accepts the language of all strings that end with c. Now, suppose we want a machine accepting strings that start with c and have an even number of a's and b's or ending in c's. In other words, suppose I want a machine accepting the union of the languages accepted by M1 and M4. What about a machine like this? (Note: e stands for the empty string here.)

What does this mean? Well, what I mean is an e-transition is one the machine can take without reading in any input. In this case, the machine will essentially choose between running machine M1 or machine M4 before it starts reading input. Of course, the machine could choose to simply choose to stay in its start state and start reading characters. In that case, however, it'd be stuck since there aren't transitions for any of a, b or c. Here are all the possible computations on input cacc:
(q5,cacc) => (q2,cacc) => (q3,acc) => (q4,cc) => (q4,c) => (q4,e)
(q5,cacc) => (q0,cacc) => (q0,acc) => (q0,cc) => (q0,c) => (q1,e)
(q5,cacc) => (q0,cacc) => (q0,acc) => (q0,cc) => (q0,c) => (q0,e)
(q5,cacc) => (q0,cacc) => (q1,acc) => STUCK
Since one of these computations (the second one) leaves us in an accepting state, the string is accepted!
Summing up Non-Deterministic Finite Automata
Basically, a non-deterministic finite automaton is like a deterministic automaton except you can
  1. have a state/symbol combination with no defined transition,
  2. have a state/symbol combination with transitions to more than one state, and
  3. have e-transitions, i.e. transitions the machine can take without reading an input symbol.
Since many different computations are possible for a single input on a non-deterministic machine, and since they won't all necessarily agree on whether the input should be accepted, we need a new definition of what it means for a machine to accept a string. Our new definition is that a non-deterministic machine accepts a string as long as there is some way that it can process the string and end up in an accepting state.


Christopher W Brown
Last modified: Fri Sep 12 15:56:00 EDT 2003