Start

P P P P P P

pV\piJ\pLJ pU pU pO

с P.C P.C

о о о о о о о

с Р.С Р,С Р,С Р,С Р,С Р,С Figure 2.3: The product automaton for the store and bank

out of г or a;, respectively, for input Z), then there is no arc out of (г, x) labeled Z.

We can now see how the arcs of Fig. 2.3 were selected. For instance, on input pay, the store goes from state a to b, but stays put if it is in any other state besides a. The bank stays in whatever state it is in when the input is pay, because that action is irrelerant to the bank. This observation explains the four arcs labeled P at the left ends of the four rows in Fig. 2.3, and the loops labeled P on other states.

For another example of how the arcs are selected, consider the input redeem. If the bank receives a redeem message when in state 1, it goes to state 3. If in states 3 or 4, it stays there, while in state 2 the bank automaton dies; i.e., it has nowhere to go. The store, on the other hand, can make transitions from state 6 to (i or from с to e when the redeem input is received. In Fig. 2.3, we see six arcs labeled redeem, corresponding to the six combinations of three bank states and two store states that have outward-bound arcs labeled R. For example, in state (1, b), the arc labeled R takes the automaton to state {3,d), since redeem takes the bank from state 1 to 3 and the store from 6 to d. As another example, there is an arc labeled Я from (4,c) to (4, e), since redeem takes the bank from state 4 back to state 4, while it takes the store from state с to state e.

2.1.5 Using the Product Automaton to Validate the Protocol

Figure 2.3 tells us some int(;restiiig things. For instance, of the 28 states, only ten of them can be reached from the start state, whicli is (l,a) - the combination of the start states of the bank and store automata. Notice that states like (2,fi) and {4,d) are not accessible, that is, T,h<;ro is no path to them from the start state. Inaccessible states need not be included in the automaton, and we did so in this example just to be systematic.

Howoлer, the real purpose of analysing a protocol such as this one using automata is to ask and answer questions that mean can the following typo of error occur? In the example at hand, wc might ask whethfr it is poHSible that the store can ship goods and never get paid. That is, can th< prothut automaton get into a state in which the store; has shipped (that is, tht* state is in column c, e, or g), and yet no transition on input T was over made or will be made?

For instance, in state (3,e), the goods have shipped, but there will eventually be a transition on input T to state {4,д). In terms of what tin* bank is doing, once it has gotttui to state 3, it has received tlu; redeem request and processed it. That means it must have been in state 1 bcforc receiving the redeem and therefore the cancel message had not been received and will be ignonid if received hi the future. Thus, the bank will eventually perform tin; trinsfcir of money to the; store.

However, state (2,c) is a problem. The state is accessible, but th<; only arc out leads back to that state. This state corresponds to a situation where the bank receivfid a cancel message before a redeem message. Howtiv<>r. tht; store received a pay message; i.e., the customer was being duplicitous and has both spent and canceled the same money. The store foolishly shipped before trying to redeem the money, and when the store does execute the redeem action, the bank will not even acknowledge the message, because it is in state 2, where it has canceled the money and will not process a redeem request.

2.2 Deterministic Finite Automata

Now it is time to present the formal notion of a finite automaton, .so that we may start to make precise some of the informal arguments an<i descriptions that we saw in Sections 1.1.1 and 2.1. We begin by introducing the formali.sm of a deterministic finite automaton, one that is in a single state after reading any sequence of inputs. The term deterministic refers to the fact that on each input there is one and only one state to whit:h the automaton can transition from its {:urrent state. In contrast, nondeterministic finite automata, the subject of Section 2.3, can be in several states at once. The term finite automaton will refer to the deterministic variety, although we shall икс deterministic or tht; abbreviation DFA normally, to remind the reader of which kind of automaton we are talking about.

More accuratftly, the graph is a picture of some transition function S, and the arcs of the graph &K constructed to reflect the transitions specified by 6.

2.2.1 Definition of a Deterministic Finite Automaton

A dtterininistic finite automaton consists of:

1. A finite set of states, often denoted Q.

2. A finite set of input symbols, often denoted S.

3. A transition function that takes as arguments a state and an input symbol and returns a state. The transition function will commonly be denoted S. In our informal graph representation of automata, S was represented by arcs between states and the labels on the arcs. If is a state, and a is an input symbol, then 5{q, a) is that state p such that there is an arc labeled a from to p.

4. A start state, one of the states in Q.

5. A set of final or accepting states F. The set F is a subset of Q.

A deterministic finite automaton will often be referred to by its acronym: DFA. The most succinct representation of a DRA is a listing of the five components above. In proofs wc often talk about a DFA in five-tuple notation:

A = {Q,i:,5,qo,F)

where A is the name of the DFA, Q is its set of states, E its input symbols, S its transition function, qo its start state, and F its set of accepting states.

2.2.2 How a DFA Processes Strings

The first thing we need to understand about a DFA is how the DFA decides whether or not to accept a sequence of input symbols. The language of the DFA is the set of all strings that the DFA accepts. Suppose aicj a is a sequence of input symbols. We start out with the DFA in its start state, qo. We consult the transition function 6, say S{qoa-\) - to find the state that the DFA A enters after processing the first input symbol Gi . We process the next input symbol, a2, by evaluating 5{gi,a2); let us suppose this state is q. We continue in this manner, finding states qs,q\, ,Яп fh that {j-i,aj) - qi for each i. If q, is a member of F, then the input aiaa - On is accepted, and if not then it is rejected.

Example 2.1: Let ns formally specify a DFA that accepts all and only the strings of Os and Is that have the sequence 01 somewhere in the string. We can write this language L as:

{w I w is of the form xOly for some strings X and у consisting of Os and Is only}