Write down a sequence of configurations in which this machine starts with cbcaa and
δ:{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.
(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.
(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.
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.
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.
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) => stuckOnly 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:
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) => STUCKSince one of these computations (the second one) leaves us in an accepting state, the string is accepted!