A computation by a finite automaton involves two things: the machine's states and the transitions between them, and the input on the tape. If you stop in the middle of a computation, all you need to know to start back up and continue is what state you're in, and what symbols are left on the tape. We refer to this as the configuration of the machine during the computation.
A configuration of machine
M = (Q,Σ,δ,s,W) is a tuple
(q,w) ∈ Q
It is interpreted as "Machine M is in state q with
string w left on the input tape".
For machine M = (Q,Σ,δ,s,W), we say that configuration (p,v) yields in one step configuration (q,w) if for some character a ∈ Σ we have v = aw and δ(p,a) = q. This is sometimes denoted (p,v) ⇒ (q,w), or (p,v) ⇒M (q,w) when you need to clearly indicate which machine you're referring to.A computation simply chains together steps like these. For example, if you look at machine M3 above, it's clear that from configuration (q0,abcacb) you eventually get to configuration (q1,cb). The computation looks like:
(q0,abcacb) ⇒ (q1,bcacb) ⇒ (q0,cacb) ⇒ (q0,acb) ⇒ (q1,cb)We package up this whole thing and simply say that (q0,abcacb) yields (q1,cb), though clearly not in "one step". This we also make formal with a definition:
(p,v) = (q1,w1) ⇒ (q2,w2) ⇒ ... ⇒ (qk,wk) = (q,w)This is sometimes denoted (p,v) ⇒* (q,w), or (p,v) ⇒*M (q,w) when you need to clearly indicate which machine you're referring to.
Machine M = (Q,Σ,δ,s,W) accepts string w ∈ Σ* if configuration (s,w) ⇒* (q,λ) for some state q ∈ W.In other words: M starts off in state s with string w on the input tape, and it ends up in an accepting state with the empty string left on the input tape. All of this may seem like a lot of work that essentially leaves us knowing no more than we did when we started. However, all of these definitions will give us a way to prove that algorithms do what we say they do.
So now we can write down the computation of a DFA M on an input string w. For machine M3 (from above) on input abcacb we get the following computation:
(q0,abcacb) ⇒ (q1,bcacb) ⇒ (q0,cacb) ⇒ (q0,acb) ⇒ (q1,cb) ⇒ (q2,b) ⇒ (q2,λ)... and since q2 is accepting, the input abcacb is accepted.