Class 9: Configuration

Section 2.1 of Theory of Computing, A Gentle Introduction, concentrating on pages 17-20.
Printout the homework and answer the questions on that paper.

More formality
We now know how to define machines formally, and we know how to define algorithms on those machines formally. However, we haven't given any formal proofs that these algorithms do what we claim they do. In other words, we've never proven that the machines they produce accept the languages we claim they accept. In fact, we don't even have a formal definition of what it means for a machine to accept a string. Our starting point for pinning all this down exactly will be the concept of configuration. In the discussions that follow, we will refer to the machine M3 below:

Machine M3.

Suppose you were tracing throught the computation of a big finite automaton on a very long input string. Halfway through the computation, the phone rings. If you go answer the phone, will you have to restart your work from the beginning when you get back? What would you need to remember in order to pick up where you left off? All you'd need to know is the state you were in, and what's left of the input!

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 x Σ*. It is interpreted as "Machine M is in state q with string w left on the input tape".

As a machine computes, it moves from configuration to configuration. However, the rules of the machine constrain which configurations can follow each other in a single step. For example, if you look at machine M3 above, it's clear that from configuration (q1,cba) you go to configuration (q2,ba) in one step, not to any other configuration. In one step, you remove the front character from the string of input on the tape, and you use δ with the current state and that front character to determine your next state. This notion is also formalized in the "yields in one step" relation.

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:

For machine M = (Q,Σ,δ,s,W), we say that configuration (p,v) yields configuration (q,w) if there is a sequence of configurations (q1,w1), (q2,w2), ..., (qk,wk) such that

(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.

Formal definition of a machine accepting a string
After all those definitions, we can finally say what it means for a machine M to accept a string w:

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.

Christopher W Brown
Last modified: Fri Sep 11 08:42:43 EDT 2009