Another equivalent dCHoriirtion, using parameters x and to the left of the vertical bar, is:

[xOly I X and у are any strings of Os and Is}

Examples of strings in the language include 01, 11010, and 100011. Examphis of strings nut in the language include e, 0, and 111000.

What do we know about an automaton that can accept this language i? First, its input alphabet is E - {0, 1). It has some set of states, Q. af which one, say qo, is the start state. This automaton has to remembcj: the importaut facts about what inputs it has seen so far. To decide whether 01 is a substring of the input, A needs to remember:

1. Has it already seen 01? Tf so, then it acct-pts every sequcnc!- of further inputs; i.e., it will only be in accepting states from now on.

2. Has it never seen 01, but its most recent input was 0, so if it now sees a 1; it will have seen 01 and сгш accept everything it sees from here on?

3. Has it never seen 01, but its last input was either nonexistent (it just started) or it last saw a 1? In this case, .4 cannot accept until it first sees a 0 and then sees a 1 irmnediately after.

Thce three conditions can each be represented by a state. Condition (3) is represented by the start state, (/q. Surely, when just starting, we need to s(>e a 0 aiul then a 1, But if in state we next set; a 1, then we are no closer to seeing 01, and so we must stay in state t/o- That is, й(о, 1) = %.

However, if we arc in state qo and we next set; a. 0, we are in condition (2). That is. wc have never seen 01, but we have our 0, Thus, let us use q-j to represent condition (2). Our transition from qo on input 0 is f)(fy(),0) = 72-

Now, let us consider the transitkms from state q-2- И wc see a 0, we are no better off than we were, but no worse (uttier. We have not seen 01, but 0 wa-? the last symbol, so we are still waiting for a 1. State q-> describes this situation perfectly, so wc want {qiO) - q. If wo are in state 72 and we see a 1 input, we now know th(Te is a 0 followed by a 1. We can go to an accepting stare, which we shall call q\, and which corresponds to condition (1) above. That is. 6{q2.,l) = qj.

Finally, we nmst design tlie transitions for state qi. In this state, we have already setin a 01 sequence, so regardless of what happens, wt; shall still be in a situation where w(;ve seen 01. That is, d{qi,0) - 5{qi, 1) = q\.

Thus, Q = {qo.,qi,q-2}- As we said, (fy is thn start state, and the only accepting slate Is qi\ that is, F - The complete; spcicificatlon of the

automaton A that accepts the language L of strings that htive a 01 sub.mrlug, is

A[{qo.qi,q-l},{:)--<loA<ii)) where 5 is the traniiticm function described above. C[

FiguH! 2,4: The transition diagram for the DFA accepting all strings with a substrhig 01

2.2.3 Simpler Notations for DFAs

Specifying a DFA as a fivc-tnple with a detailed description of the S transition function is both tedious and hard to read. There are two preferred notations for describing automata:

1. A transition diagram, which is a graph such as the {)nes we saw in Section 2.1.

2. A transition table, which is a tabular listing of the 6 function, which by implication tells us the set of states and the input alphabet.

Transition Diagrams

A transition diagram for a DFA A = {Q, £. 6, qo, F) is a graph defined as follows:

a) Foi each state in Q there is a node.

b) For each state q m Q and each input symbol a in E, let 6{q,a) = p. Then the transition diagram has an arc from node q to node p, labeled a. If there are several input symbols that cause transitions from q to p, then the transition diagram can have one arc, labeled by the list of these symbols,

c) There is an arrow into the start state qo, labeled Start. This arrow does not originate at any node.

d) Nodes corresponding to accepting states {those in F) are marked by a double circle. States not in F have a single circle.

Example 2.2: Figure 2,4 shows the transition diagram for the DFA that we designed in Example 2.1, We see in that diagram the three nodes that correspond to the three states. There is a Start arrow entering the start state, 0; and the one accepting state, gi, is represented by a double circle. Out of each state is one arc labeled 0 and one arc labeled 1 {although the two arcs are combined into one with a double label in the case of 51), The arcs each correspond to one of the 5 facts developed in Example 2.1, □

Ttansition Tables

A transition tablt is a conventional, tabular representation of a function like S that takes two arguments and returns a value. The rows of the table corresi)ond to tlie states, and the columns correspond to the inputs. The entry for the row corresponding to state q and the column corresponding to input o. is the state

Example 2.3: The transition table corresponding to the function 5 of Example 2.1 is shown in Fig. 2.5. We have also shown two oth<;r hiatures of a transition table. The start state is marked with an arrow, and the accepting states are mark(>d with a star. Since wc can deduce the sets of states and input symbols by looking at tli(! row and column heads, we can now read from the transition table all the information we need to specify the finite automaton uniqutuy. D

Figure 2.-5: Tran.sition table for the DFA of Example 2.1

2.2.4 Extending the Transition Function to Strings

We have explaintul informally that the DF.4 defines a language: th(; .set of all strings that result in a sequence of state transitions from the start state to an ac:c(;ptiiig state. In terms of the transition diagram, the language of a DFA is the set of labels along all the paths that lead from the start state to any accepting state.

.Now, we need to make the lujtion of the language of a DFA precise. To do so, we define an extended transition function that describes what happens when we start in any state and follow any sequence of inputs. If S is our transition function, then the extended transition function constrmlcd from 6 will be called 6. The extended transition fum:tion is a function that takes a state q and a string w and returns a state p - the state that the automaton reaches when starting in state q and processing the sequence of inputs u>. Wp. dt;fine в by induction on the length of th(! input string, as follows;

BASIS; e{q,r) ~ q. That is, if we are in state q and read no inputs, then we are still in statt q.