**Reading**-
Section 2.1 of
*Theory of Computing, A Gentle Introduction*, concentrating on pages 17-20. **Homework**- 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:

**Configurations**-
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

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*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".*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

A computation simply chains together steps like these. For example, if you look at 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) ⇒*when you need to clearly indicate which machine you're referring to._{M}(q,w)*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)**(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)**(p,v) ⇒* (q,w)*, or*(p,v) ⇒**when you need to clearly indicate which machine you're referring to._{M}(q,w) **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

In other words:*M = (Q,Σ,δ,s,W)**accepts*string*w ∈ Σ*if configuration^{*}*(s,w) ⇒* (q,λ)*for some state*q ∈ W*.*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,λ)**q2*is accepting, the input*abcacb*is accepted.

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