Recall our convention ilial, letters at the beginning of the alphabet are symbols, and iliose near the end of the aipliabet are strings. We need that convention to make sense of the phrase of the form xa.

INDUCTION: Suppose w is a string of the form xa; that is, a is the last symbol of and X is the string consisting of all but the last symbol.* For example, w = 1101 is broken into x = 110 and a = 1. Then

S{q,w) = 5{§{(bx),a) (2.1)

Now (2,1) may seem like a lot to take in, but the idea is simple. To compute 6{q, w), first compute e(q, x), the state that the automaton is in after processing all but the last symbol of w. Suppose this state is p; that is, 5{q, x) = p. Then 5{q,w) is what we get by making a transition from state p on input o, the last symbol of w. That is, 6{q,w) - 6{p,a).

Example 2.4: Let us design a DFA to accept the language

L - {u, I UI has both an even number of Os and an even number of Is}

It should not be surprising that the job of the states of this DFA is to count both the number of Os and the number of Is, but count them modulo 2. That is, the state is used to remember whether the number of Os seen so far is even or odd, and also to remember whether the number of Is seen so far is even or odd. There are thus four states, which can be given the following interpretations:

qa: Both the number of Os seen so far and the number of Is seen so far are even.

5i: The number of Os seen so far is even, but the number of Is seen so far is odd.

92: The number of Is seen so far is even, but the number of Os seen so far is odd.

q: Both the number of Os seen so far and the number of Is seen so far are odd.

State 5o is both the start state and the lone ac:copting state. It is the start state, because before reading any inputs, the numbers of Os and Is seen so far are both zero, and zero is even. It is the only accepting state, because it describes exactly the condition for a sequence of Os and Is to be in language L.

We now know almost how to specify the DFA for language L. It is A = i{qo, ?i, д2,щ}, {0,1}, (5,90, {?□})

Start

Figure 2,6: Transition diagram for the DFA of Example 2.4

where the transition function S is described by the transition diagram of Fig. 2,6. Notice how each input 0 causes the state to cross the horizontal, dashed line. Thus, after seemg an even number of Os we are always above the line, in state qo or qi while after seeing an odd number of Os we are always below the line, in state q2 or дз. Likewise, every 1 causes the state to cross the vertical, dashed line. Thus, after seeing an even number of Is, we are always to the left, in state {jo or while after seeing an odd number of Is we are to the right, in state Qi or qs. These observations are an informal proof that the four states have the interpretations attributed to them. However, one could prove the correctness of our claims about the states formally, by a mutual induction in the spirit of Example 1.23.

We can also represent this DFA by a transition table. Figure 2.7 shows this table. However, we are not just concerned with the design of this DFA; we want to use it to illustrate the construction of S from its transition function 6. Suppose the input is 110101. Since this string has even numbers of Os and Is both, we expect it is in the language. Thus, we expect that S{qo, 110101) = qo, since 70 is the only accepting state. Let us now verify that claim.

Figure 2,7: Transition table for the DFA of Example 2.4

The check involves computing 6{qo, w) for each prefix w of 110101, starting at f. and going in increasing size. The summary of this calculation is:

Standard Notation and Local Variables

After reading this section, you might imagine that our customary notation is required; that is, you must use S for the transition function, use A for the name of a DFA, and so on. We tend to use the same variables to denote the same thing across all examples, because it helps to remind you of the types of variables, much the way a variable i in a program is almost always of integer type. However, we are free to call the components of an automaton, or anything else, anything we wish. Thus, you are free to call a DFA M and its transition function T if you like.

Moreover, you should not be surprised that the same variable means different things in different contexts. For example, the DFAs of Examples 2.1 and 2.4 both wore given a transition function called 5, However, the two transition functions are each local variables, belonging only to their examples. These two transition functions are very different and bear no relationship to one another.

6{qn,l) = fi{S{(!o,€), 1) =6{qo,l) = Qy.

. %n,ll) - й((од,1),1) - %ь1) - qo.

(go, ПО) = S{Sigo, 11),0) - 6{qo,0) - (?2.

. (gn, 1101) = 5{6{qu, 110), i) = 1) - 93.

5{qo, 11010) - 6{6{qoM01), 0) - (93,0) = 9,.

(90,110101) - d(5(qo, 11010), 1) = 5{q 1) - 90-□

2.2.5 The Language of a DFA

Now, we can define the language of a DFA A - {Q,T 6,qQ,F). This language is denoted L{A), and is defined by

L{A) = {ги I 6{qo,w) is in F}

That is, the language of A is the set of strings w that take the start state 90 to one of the accepting states. If L is L{A) for some DFA A, then we say L is a regular language.