Finite-State Automata

Section 17.3 Finite-State Automata

We have seen how regular expressions can be used to generate languages mechanically. How might languages be recognized mechanically? The question is of interest because if we can mechanically recognize languages like \(L= \{\)all legal C++ programs that will not go into infinite loops on any input\(\}\text{,}\) then it would be possible to write uber-compilers that can do semantic error-checking like testing for infinite loops, in addition to the syntactic error-checking they currently do.

What formalism might we use to model what it means to recognize a language ``mechanically’’? We look for inspiration to a language-recognizer with which we are all familiar, and which we’ve already in fact mentioned: a compiler. Consider how a C++ compiler might handle recognizing a legal if statement. Having seen the word

if

, the compiler will be in a state or phase of its execution where it expects to see a (; in this state, any other character will put the compiler in a ``failure" state. If the compiler does in fact see a ( next, it will then be in an ``expecting a boolean condition" state; if it sees a sequence of symbols that make up a legal boolean condition, it will then be in an ``expecting a )" state; and then ``expecting a {’ or a legal statement"; and so on. Thus one can think of the compiler as being in a series of states; on seeing a new input symbol, it moves on to a new state; and this sequence of transitions eventually leads to either a ``failure" state (if the if statement is not syntactically correct) or a ``success" state (if the if statement is legal). We isolate these three concepts---states, input-inspired transitions from state to state, and ``accepting" vs ``non-accepting" states---as the key features of a mechanical language-recognizer, and capture them in a model called a finite-state automaton. (Whether this is a successful distillation of the essence of mechanical language recognition remains to be seen; the question will be taken up later in this chapter.)

A finite-state automaton (FSA), then, is a machine which takes, as input, a finite string of symbols from some alphabet \(\Sigma\text{.}\) There is a finite set of states in which the machine can find itself. The state it is in before consuming any input is called the start state. Some of the states are accepting or final. If the machine ends in such a state after completely consuming an input string, the string is said to be accepted by the machine. The actual functioning of the machine is described by something called a transition function, which specifies what happens if the machine is in a particular state and looking at a particular input symbol. (``What happens" means ``in which state does the machine end up".)

Example 17.3.1. A transition function.

Below is a table that describes the transition function of a finite-state automaton with states \(p\text{,}\) \(q\text{,}\) and \(r\text{,}\) on inputs \(0\) and \(1\text{.}\)

Table 17.3.2.

	\(p\)	\(q\)	\(r\)
\(0\)	\(p\)	\(q\)	\(r\)
\(1\)	\(q\)	\(r\)	\(r\)

The table indicates, for example, that if the FSA were in state \(p\) and consumed a \(1\text{,}\) it would move to state \(q\text{.}\)

Subsection 17.3.1 Deterministic Finite-State Automata

FSAs actually come in two flavors depending on what properties you require of the transition function. We will look first at a class of FSAs called deterministic finite-state automata (DFAs). In these machines, the current state of the machine and the current input symbol together determine exactly which state the machine ends up in: for every \(\lt\) current state, current input symbol\(\gt\) pair, there is exactly one possible next state for the machine.

Definition 17.3.3. Deterministic Finite-State Automaton.

Formally, a deterministic finite-state automaton \(M\) is specified by 5 components: \(M=(Q, \Sigma, q_0, \delta, F)\) where

\(Q\) is a finite set of states;
\(\Sigma\) is an alphabet called the input alphabet;
\(q_0 \in Q\) is a state which is designated as the start state;
\(F\) is a subset of \(Q\text{;}\) the states in \(F\) are states designated as final or accepting states;
\(\delta\) is a transition function that takes \(\lt\)state, input symbol \(\gt\) pairs and maps each one to a state: \(\delta : Q \times \Sigma \rightarrow Q\text{.}\)
- To say \(\delta(q,a) = q'\) means that if the machine is in state \(q\) and the input symbol \(a\) is consumed, then the machine will move into state \(q'\text{.}\)
- The function \(\delta\) must be a total function, meaning that \(\delta(q,a)\) must be defined for every state \(q\) and every input symbol \(a\text{.}\)
- Recall also that, according to the definition of a function, there can be only one output for any particular input. This means that for any given \(q\) and \(a\text{,}\) \(\delta(q,a)\) can have only one value. This is what makes the finite-state automaton deterministic: given the current state and input symbol, there is only one possible move the machine can make.

Example 17.3.4.

The transition function described by the table in the preceding example is that of a DFA. If we take \(p\) to be the start state and \(r\) to be a final state, then the formal description of the resulting machine is \(M= (\{p,q,r\}, \{0,1\}, p, \delta, \{r\})\text{,}\) where \(\delta\) is given by

: \(\displaystyle \delta(p,0)=p\)
: \(\displaystyle \delta(q,0)=q\)
: \(\displaystyle \delta(r,0)=r\)

: \(\displaystyle \delta(p,1)=q\)
: \(\displaystyle \delta(q,1)=r\)
: \(\displaystyle \delta(r,1)=r\)

The transition function \(\delta\) describes only individual steps of the machine as individual input symbols are consumed. However, we will often want to refer to``the state the automaton will be in if it starts in state \(q\) and consumes input string \(w\)", where \(w\) is a string of input symbols rather than a single symbol. Following the usual practice of using \(^*\) to designate ``0 or more", we define \(\delta^*(q,w)\) as a convenient shorthand for ``the state that the automaton will be in if it starts in state \(q\) and consumes the input string \(w\)". For any string, it is easy to see, based on \(\delta\text{,}\) what steps the machine will make as those symbols are consumed, and what \(\delta^*(q,w)\) will be for any \(q\) and \(w\text{.}\) Note that if no input is consumed, a DFA makes no move, and so \(\delta^*(q, \varepsilon) = q\) for any state \(q\text{.}\)

Example 17.3.5.

\(M\)

\begin{align*} \delta^*(p, 001)\amp =q \amp \text{ since }\delta(p,0)=p, \delta(p,0)=p,\text{ and }\delta(p,1)=q;\\ \delta^*(p, 01000) \amp = q \amp\\ \delta^*(p, 1111) \amp = r \amp\\ \delta^*(q, 0010) \amp = r \amp \end{align*}

We have divided the states of a DFA into accepting and non-accepting states, with the idea that some strings will be recognized as ``legal" by the automaton, and some not. Formally:

Definition 17.3.6. Language Accepted by FSA.

Let \(M=(Q, \Sigma, q_0, \delta, F)\text{.}\) A string \(w \in \Sigma^*\) is accepted by \(M\) iff \(\delta^*(q_0, w) \in F\text{.}\) (Don’t get confused by the notation. Remember, it’s just a shorter and neater way of saying ``\(w \in \Sigma^*\) is accepted by \(M\) if and only if the state that M will end up in if it starts in \(q_0\) and consumes \(w\) is one of the states in \(F\text{.}\)")

The language accepted by \(M\), denoted \(L(M)\text{,}\) is the set of all strings \(w \in \Sigma^*\) that are accepted by \(M\text{:}\) \(L(M) = \{ w \in\Sigma^* \ | \ \delta^*(q_0, w) \in F\}\text{.}\)

Note that we sometimes use a slightly different phrasing and say that a language \(L\) is accepted by some machine \(M\text{.}\) We don’t mean by this that \(L\) and maybe some other strings are accepted by \(M\text{;}\) we mean \(L = L(M)\text{,}\) i.e. \(L\) is exactly the set of strings accepted by \(M\text{.}\)

It may not be easy, looking at a formal specification of a DFA, to determine what language that automaton accepts. Fortunately, the mathematical description of the automaton \(M=(Q, \Sigma, q_0, \delta, F)\) can be neatly and helpfully captured in a picture called a transition diagram. Consider again the DFA of the two preceding examples. It can be represented pictorially as:

Transition diagram for above DFA, \(M\) — Figure 17.3.7.

The arrow on the left indicates that \(p\) is the start state; double circles indicate that a state is accepting. Looking at this picture, it should be fairly easy to see that the language accepted by the DFA \(M\) is \(L(M) = \{ x \in \{0,1\}^* \ | \ n_1(x) \geq 2\}\text{.}\)

Example 17.3.8.

Find the language accepted by the DFA shown below (and describe it using a regular expression!)

Transition diagram representing a formal language — Figure 17.3.9.

The start state of \(M\) is accepting, which means \(\varep \in L(M)\text{.}\) If \(M\) is in state \(q_0\text{,}\) a sequence of two \(a\)’s or three \(b\)’s will move \(M\) back to \(q_0\) and hence be accepted. So \(L(M) = L((aa | bbb)^*)\text{.}\)

The state \(q_4\) in the preceding example is often called a garbage or trap state: it is a non-accepting state which, once reached by the machine, cannot be escaped. It is fairly common to omit such states from transition diagrams. For example, one is likely to see the diagram:

Transition diagram omitting a trap state — Figure 17.3.10.

Note that this cannot be a complete DFA, because a DFA is required to have a transition defined for every state-input pair. The diagram is ``short for" the full diagram:

Transition diagram with trap state — Figure 17.3.11.

As well as recognizing what language is accepted by a given DFA, we often want to do the reverse and come up with a DFA that accepts a given language. Building DFAs for specified languages is an art, not a science. There is no algorithm that you can apply to produce a DFA from an English-language description of the set of strings the DFA should accept. On the other hand, it is not generally successful, either, to simply write down a half-dozen strings that are in the language and design a DFA to accept those strings---invariably there are strings that are in the language that aren’t accepted, and other strings that aren’t in the language that are accepted. So how do you go about building DFAs that accept all and only the strings they’re supposed to accept? The best advice I can give is to think about relevant characteristics that determine whether a string is in the language or not, and to think about what the possible values or ``states" of those characteristics are; then build a machine that has a state corresponding to each possible combination of values of relevant characteristics, and determine how the consumption of inputs affects those values. I’ll illustrate what I mean with a couple of examples.

Example 17.3.12.

Find a DFA with input alphabet \(\Sigma = \ab\) that accepts the language \(L= \{w \in\Sigma^* \ | \ n_a(w) \text{ and } n_b(w) \text{ are both even } \}\text{.}\)

The characteristics that determine whether or not a string \(w\) is in \(L\) are the parity of \(n_a(w)\) and \(n_b(w)\text{.}\) There are four possible combinations of ``values" for these characteristics: both numbers could be even, both could be odd, the first could be odd and the second even, or the first could be even and the second odd. So we build a machine with four states \(q_1, q_2, q_3, q_4\) corresponding to the four cases. We want to set up \delta so that the machine will be in state \(q_1\) exactly when it has consumed a string with an even number of \(a\)’s and an even number of \(b\)’s, in state \(q_2\) exactly when it has consumed a string with an odd number of \(a\)’s and an odd number of \(b\)’s, and so on.

To do this, we first make the state \(q_1\) into our start state, because the DFA will be in the start state after consuming the empty string \(\varep\text{,}\) and \(\varep\) has an even number (zero) of both \(a\)’s and \(b\)’s. Now we add transitions by reasoning about how the parity of \(a\)’s and \(b\)’s is changed by additional input. For instance, if the machine is in \(q_1\) (meaning an even number of \(a\)’s and an even number of \(b\)’s have been seen) and a further \(a\) is consumed, then we want the machine to move to state \(q_3\text{,}\) since the machine has now consumed an odd number of \(a\)’s and still an even number of \(b\)’s. So we add the transition \(\delta(q_1, a) = q_3\) to the machine. Similarly, if the machine is in \(q_2\) (meaning an odd number of \(a\)’s and an odd number of \(b\)’s have been seen) and a further \(b\) is consumed, then we want the machine to move to state \(q_3\) again, since the machine has still consumed an odd number of \(a\)’s, and now an even number of \(b\)’s. So we add the transition \(\delta(q_2, b) = q_3\) to the machine. Similar reasoning produces a total of eight transitions, one for each state-input pair. Finally, we have to decide which states should be final states. The only state that corresponds to the desired criteria for the language \(L\) is \(q_1\text{,}\) so we make \(q_1\) a final state. The complete machine is shown below.

Transition diagram for finite state machine described in example — Figure 17.3.13.

Example 17.3.14.

\(\Sigma = \ab\)\(L = \{w \in\Sigma^* \ | \ n_a(w) \text{ is divisible by 3 } \}\text{.}\)\(a\)\(q_0\text{,}\)\(q_1\text{,}\)\(q_2\text{,}\)\(q_0\)\(a\)\(q_1\)\(a\)\(1 \bmod{3}\text{,}\)\(q_2\text{.}\)\(q_0\)\(\varep\)\(a\)\(b\)\(b\)

Transition diagram that accepts the language \(L = \{w \in\Sigma^*
\ | \
n_a(w) \text{ is divisible by 3 } \}\) — Figure 17.3.15.

Example 17.3.16.

Find a DFA with input alphabet \(\Sigma = \ab\) that accepts the language \(L = \{w \in\Sigma^* \ | w \text{ contains three consecutive a's } \}\text{.}\)

Again, it is not quite so simple as making a two-state machine where the states correspond to ``have seen \(aaa\)" and ``have not seen \(aaa\)". Think dynamically: as you move through the input string, how do you arrive at the goal of having seen three consecutive \(a\)’s? You might have seen two consecutive \(a\)’s and still need a third, or you might just have seen one \(a\) and be looking for two more to come immediately, or you might just have seen a \(b\) and be right back at the beginning as far as seeing 3 consecutive \(a\)’s goes. So once again there will be three states, with the ``last symbol was not an \(a\)’’ state being the start state. The complete automaton is shown below.

Transition diagram that accepts a language where the number of a characters is divisible by 3. — Figure 17.3.17.

Subsection 17.3.2 Nondeterministic Finite-State Automata

As mentioned briefly above, there is an alternative school of though as to what properties should be required of a finite-state automaton’s transition function. Recall our motivating example of a C++ compiler and a legal if statement. In our description, we had the compiler in an ``expecting a )" state; on seeing a ), the compiler moved into an ``expecting a } or a legal statement" state. An alternative way to view this would be to say that the compiler, on seeing a ), could move into one of two different states: it could move to an ``expecting a {" state or move to an ``expecting a legal statement" state. Thus, from a single state, on input ), the compiler has multiple moves. This alternative interpretation is not allowed by the DFA model. A second point on which one might question the DFA model is the fact that input must be consumed for the machine to change state. Think of the syntax for C++ function declarations. The return type of a function need not be specified (the default is taken to be int). The start state of the compiler when parsing a function declaration might be ``expecting a return type"; then with no input consumed, the compiler can move to the state ``expecting a legal function name". To model this, it might seem reasonable to allow transitions that do not require the consumption of input (such transitions are called \(\varep\)-transitions). Again, this is not supported by the DFA abstraction. There is, therefore, a second class of finite-state automata that people study, the class of nondeterministic finite-state automata.

A nondeterministic finite-state automaton (NFA) is the same as a deterministic finite-state automaton except that the transition function is no longer a function that maps a state-input pair to a state; rather, it maps a state-input pair or a state-\(\varep\) pair to a set of states. No longer do we have \(\delta(q,a) = q'\text{,}\) meaning that the machine must change to state \(q'\) if it is in state \(q\) and consumes an \(a\text{.}\) Rather, we have \(\partial(q,a) = \{q_1, q_2, \ldots, q_n\}\text{,}\) meaning that if the machine is in state \(q\) and consumes an \(a\text{,}\) it might move directly to any one of the states \(q_1, \ldots, q_n\text{.}\) Note that the set of next states \(\partial(q,a)\) is defined for every state \(q\) and every input symbol \(a\text{,}\) but for some \(q\)’s and \(a\)’s it could be empty, or contain just one state (there don’t have to be multiple next states). The function \(\partial\) must also specify whether it is possible for the machine to make any moves without input being consumed, i.e. \(\partial(q, \varepsilon)\) must be specified for every state \(q\text{.}\) Again, it is quite possible that \(\partial(q, \varepsilon)\) may be empty for some states \(q\text{:}\) there need not be \(\varep\)-transitions out of \(q\text{.}\)

Definition 17.3.18.

Formally, a nondeterministic finite-state automaton \(M\) is specified by 5 components: \(M=(Q, \Sigma, q_0, \partial, F)\) where

\(Q, \Sigma, q_0 \) and \(F\) are as in the definition of DFAs;
\(\partial\) is a transition function that takes \(\lt\)state, input symbol\(\gt\) pairs and maps each one to a set of states. To say \(\partial(q,a) = \{q_1, q_2, \ldots , q_n\}\) means that if the machine is in state \(q\) and the input symbol \(a\) is consumed, then the machine may move directly into any one of states \(q_1, q_2, \ldots , q_n\text{.}\) The function \(\partial\) must also be defined for every \(\lt\)state,\(\varep\)\(\gt\) pair. To say \(\partial(q,\varep) = \{q_1, q_2, \ldots , q_n\}\) means that there are direct \(\varep\)-transitions from state \(q\) to each of \(q_1, q_2, \ldots , q_n\text{.}\)

The formal description of the function \(\partial\) is \(\partial : Q \times (\Sigma \cup \{\varep\}) \rightarrow \POW(Q)\text{.}\)

The function \(\partial\) describes how the machine functions on zero or one input symbol. As with DFAs, we will often want to refer to the behavior of the machine on a string of inputs, and so we use the notation \(\partial^*(q,w)\) as shorthand for ``the set of states in which the machine might be if it starts in state \(q\) and consumes input string \(w\)". As with DFAs, \(\partial^*(q,w)\) is determined by the specification of \(\partial\text{.}\) Note that for every state \(q\text{,}\) \(\partial^*(q, \varep)\) contains at least \(q\text{,}\) and may contain additional states if there are (sequences of) \(\varep\)-transitions out of \(q\text{.}\)

We do have to think a bit carefully about what it means for an NFA to accept a string \(w\text{.}\) Suppose \(\partial^*(q_0,w)\) contains both accepting and non-accepting states, i.e. the machine could end in an accepting state after consuming \(w\text{,}\) but it might also end in a non-accepting state. Should we consider the machine to accept \(w\text{,}\) or should we require every state in \(\partial^*(q_0,w)\) to be accepting before we admit \(w\) to the ranks of the accepted? Think of the C++ compiler again: provided that an if statement fits one of the legal syntax specifications, the compiler will accept it. So we take as the definition of acceptance by an NFA: A string \(w\) is accepted by an NFA provided that at least one of the states in \(\partial^*(q_0,w)\) is an accepting state. That is, if there is some sequence of steps of the machine that consumes \(w\) and leaves the machine in an accepting state, then the machine accepts \(w\text{.}\) Formally:

Definition 17.3.19. Language Accepted by NFA.

Let \(M=(Q, \Sigma, q_0, \partial, F)\) be a nondeterministic finite-state automaton. The string \(w \in \Sigma^*\) is accepted by \(M\) iff \(\partial^*(q_0, w)\) contains at least one state \(q_F \in F\text{.}\)

The language accepted by \(M\), denoted \(L(M)\text{,}\) is the set of all strings \(w \in \Sigma^*\) that are accepted by \(M\text{:}\) \(L(M) = \{ w \in\Sigma^*|\partial^*(q_0, w) \cap F \neq \emptyset\}\text{.}\)

Example 17.3.20.

The NFA shown below accepts all strings of \(a\)’s and \(b\)’s in which the second-to-last symbol is \(a\text{.}\)

Diagram of a non-deterministic finite state automata described in example. — Figure 17.3.21.

It should be fairly clear that every language that is accepted by a DFA is also accepted by an NFA. Pictorially, a DFA looks exactly like an NFA (an NFA that doesn’t happen to have any \(\varep\)-transitions or multiple same-label transitions from any state), though there is slightly more going on behind the scenes. Formally, given the DFA \(M=(Q, \Sigma, q_0, \delta, F)\text{,}\) you can build an NFA \(M'=(Q, \Sigma, q_0, \partial, F)\) where 4 of the 5 components are the same and where every transition \(\delta(q,a) = q'\) has been replaced by \(\partial(q,a) = \{q'\}\text{.}\)

But is the reverse true? Can any NFA-recognized language be recognized by a DFA? Look, for example, at the language in Example 17.3.20. Can you come up with a DFA that accepts this language? Try it. It’s pretty difficult to do. But does that mean that there really is no DFA that accepts the language, or only that we haven’t been clever enough to find one?

It turns out that the limitation is in fact in our cleverness, and not in the power of DFAs.

Theorem 17.3.22.

Every language that is accepted by an NFA is accepted by a DFA.

Proof.

Suppose we are given an NFA \(N = (P, \Sigma, p_0, \partial, F_p)\text{,}\) and we want to build a DFA \(D=(Q, \Sigma, q_0, \delta, F_q)\) that accepts the same language. The idea is to make the states in \(D\) correspond to subsets of \(N\)’s states, and then to set up \(D\)’s transition function \(\delta\) so that for any string \(w\text{,}\) \(\delta^*(q_0, w)\) corresponds to \(\partial^*(p_0,w)\text{;}\) i.e. the single state that \(w\) gets you to in \(D\) corresponds to the set of states that \(w\) could get you to in \(N\text{.}\) If any of those states is accepting in \(N\text{,}\) \(w\) would be accepted by \(N\text{,}\) and so the corresponding state in \(D\) would be made accepting as well.

So how do we make this work? The first thing to do is to deal with a start state \(q_0\) for \(D\text{.}\) If we’re going to make this state correspond to a subset of \(N\)’s states, what subset should it be? Well, remember (1) that in any DFA, \(\delta^*(q_0, \varep) = q_0\text{;}\) and (2) we want to make \(\delta^*(q_0, w)\) correspond to \(\partial^*(p_0,w)\) for every \(w\text{.}\) Putting these two limitations together tells us that we should make \(q_0\) correspond to \(\partial^*(p_0, \varep)\text{.}\) So \(q_0\) corresponds to the subset of all of \(N\)’s states that can be reached with no input.

Now we progressively set up \(D\)’s transition function \(\delta\) by repeatedly doing the following:

find a state \(q\) that has been added to \(D\) but whose out-transitions have not yet been added. (Note that \(q_0\) initially fits this description.) Remember that the state \(q\) corresponds to some subset \(\{p_1, \ldots , p_n\}\) of \(N\)’s states.
for each input symbol \(a\text{,}\) look at all \(N\)’s states that can be reached from any one of \(p_1, \ldots , p_n\) by consuming \(a\) (perhaps making some \(\varep\)-transitions as well). That is, look at \(\partial^*(p_1,a) \cup \ldots \cup \partial^*(p_n,a)\text{.}\) If there is not already a DFA state \(q'\) that corresponds to this subset of \(N\)’s states, then add one, and add the transition \(\delta(q, a)= q'\) to \(D\)’s transitions.

The above process must halt eventually, as there are only a finite number of states \(n\) in the NFA, and therefore there can be at most \(2^n\) states in the DFA, as that is the number of subsets of the NFA’s states. The final states of the new DFA are those where at least one of the associated NFA states is an accepting state of the NFA.

Can we now argue that \(L(D) = L(N)\text{?}\) We can, if we can argue that \(\delta^*(q_0,w)\) corresponds to \(\partial^*(p_0,w)\) for all \(w \in\Sigma^*\text{:}\) if this latter property holds, then \(w \in L(D)\) iff \(\delta^*(q_0,w)\) is accepting, which we made be so iff \(\partial^*(p_0,w)\) contains an accepting state of \(N\text{,}\) which happens iff \(N\) accepts \(w\) i.e. iff \(w \in L(N)\text{.}\)

So can we argue that \(\delta^*(q_0,w)\) does in fact correspond to \(\partial^*(p_0,w)\) for all \(w\text{?}\) We can, using induction on the length of \(w\text{.}\)

First, a preliminary observation. Suppose \(w=xa\text{,}\) i.e. \(w\) is the string \(x\) followed by the single symbol \(a\text{.}\) How are \(\partial^*(p_0,x)\) and \(\partial^*(p_0,w)\) related? Well, recall that \(\partial^*(p_0,x)\) is the set of all states that \(N\) can reach when it starts in \(p_0\) and consumes \(x\text{:}\) \(\partial^*(p_0,x) = \{p_1, \ldots, p_n\}\) for some states \(p_1, \ldots, p_n\text{.}\) Now, \(w\) is just \(x\) with an additional \(a\text{,}\) so where might \(N\) end up if it starts in \(p_0\) and consumes \(w\text{?}\) We know that \(x\) gets \(N\) to \(p_1\) or \(\ldots\) or \(p_n\text{,}\) so \(xa\) gets \(N\) to any state that can be reached from \(p_1\) with an \(a\) (and maybe some \(\varep\)-transitions), and to any state that can be reached from \(p_2\) with an \(a\) (and maybe some \(\varep\)-transitions), etc. Thus, our relationship between \(\partial^*(p_0,x)\) and \(\partial^*(p_0,w)\) is that if \(\partial^*(p_0,x) = \{p_1, \ldots, p_n\}\text{,}\) then \(\partial^*(p_0,w) = \partial^*(p_1,a) \cup \ldots \cup \partial^*(p_n,a)\text{.}\) With this observation in hand, let’s proceed to our proof by induction.

We want to prove that \(\delta^*(q_0,w)\) corresponds to \(\partial^*(p_0,w)\) for all \(w \in\Sigma^*\text{.}\) We use induction on the length of \(w\text{.}\)

Base case: Suppose \(w\) has length 0. The only string \(w\) with length 0 is \(\varep\text{,}\) so we want to show that \(\delta^*(q_0,\varep)\) corresponds to \(\partial^*(p_0,\varep)\text{.}\) Well, \(\delta^*(q_0, \varep) = q_0\text{,}\) since in a DFA, \(\delta^*(q, \varep) = q\) for any state \(q\text{.}\) We explicitly made \(q_0\) correspond to \(\partial^*(p_0,\varep)\text{,}\) and so the property holds for \(w\) with length 0.
Inductive case: Assume that the desired property holds for some number \(n\text{,}\) i.e. that \(\delta^*(q_0,x)\) corresponds to \(\partial^*(p_0,x)\) for all \(x\) with length \(n\text{.}\) Look at an arbitrary string \(w\) with length \(n+1\text{.}\) We want to show that \(\delta^*(q_0,w)\) corresponds to \(\partial^*(p_0,w)\text{.}\) Well, the string \(w\) must look like \(xa\) for some string \(x\) (whose length is \(n\)) and some symbol \(a\text{.}\) By our inductive hypothesis, we know \(\delta^*(q_0,x)\) corresponds to \(\partial^*(p_0,x)\text{.}\) We know \(\partial^*(p_0,x)\) is a set of \(N\)’s states, say \(\partial^*(p_0,x) = \{p_1, \ldots, p_n\}\text{.}\)

At this point, our subsequent reasoning might be a bit clearer if we give explicit names to \(\delta^*(q_0,w)\) (the state \(D\) reaches on input \(w\)) and \(\delta^*(q_0,x)\) (the state \(D\) reaches on input \(x\)). Call \(\delta^*(q_0, w)\) \(q_w\text{,}\) and call \(\delta^*(q_0,x)\) \(q_x\text{.}\) We know, because \(w=xa\text{,}\) there must be an \(a\)-transition from \(q_x\) to \(q_w\text{.}\) Look at how we added transitions to \(\delta\text{:}\) the fact that there is an \(a\)-transition from \(q_x\) to \(q_w\) means that \(q_w\) corresponds to the set \(\partial^*(p_1,a) \cup \ldots \cup \partial^*(p_n,a)\) of \(N\)’s states. By our preliminary observation, \(\partial^*(p_1,a) \cup \ldots \cup \partial^*(p_n,a)\) is just \(\partial^*(p_0,w)\text{.}\) So \(q_w\) (or \(\delta^*(q_0,w)\)) corresponds to \(\partial^*(p_0,w)\text{,}\) which is what we wanted to prove. Since \(w\) was an arbitrary string of length \(n+1\text{,}\) we have shown that the property holds for \(n+1\text{.}\)

Altogether, we have shown by induction that \(\delta^*(q_0,w)\) corresponds to \(\partial^*(p_0,w)\) for all \(w \in\Sigma^*\text{.}\) As indicated at the very beginning of this proof, that is enough to prove that \(L(D)= L(N)\text{.}\) So for any NFA \(N\text{,}\) we can find a DFA \(D\) that accepts the same language.

Example 17.3.23.

Consider the NFA shown below.

We start by looking at \(\partial^*(p_0, \varep)\text{,}\) and then add transitions and states as described above.

\(\partial^*(p_0, \varep) = \{p_0\}\) so \(q_0 = \{p_0\}\text{.}\)
\(\delta(q_0,a)\) will be \(\partial^*(p_0,a)\text{,}\) which is \(\{p_0\}\text{,}\) so \(\delta(q_0,a) = q_0\text{.}\)
\(\delta(q_0,b)\) will be \(\partial^*(p_0,b)\text{,}\) which is \(\{p_0, p_1\}\text{,}\) so we need to add a new state \(q_1 = \{p_0, p_1\}\) to the DFA; and add \(\delta(q_0,b) = q_1\) to the DFA’s transition function.
\(\delta(q_1,a)\) will be \(\partial^*(p_0,a)\) unioned with \(\partial^*(p_1,a)\) since \(q_1 = \{p_0, p_1\}\text{.}\) Since \(\partial^*(p_0,a) \cup \partial^*(p_1,a) = \{p_0\} \cup \{p_2\} = \{p_0,p_2\}\text{,}\) we need to add a new state \(q_2 = \{p_0, p_2\}\) to the DFA, and a transition \(\delta(q_1,a) = q_2\) .
\(\delta(q_1,b)\) will be \(\partial^*(p_0,b)\) unioned with \(\partial^*(p_1,b)\text{,}\) which gives \(\{p_0, p_1\} \cup \{p_2\}\text{,}\) which again gives us a new state \(q_3\) to add to the DFA, together with the transition \(\delta(q_1,b) = q_3\text{.}\)

At this point, our partially-constructed DFA looks as shown below:

Diagram of an NFA partially converted to a DFA. — Figure 17.3.25.

The construction continues as long as there are new states being added, and new transitions from those states that have to be computed. The final DFA is shown below.

Diagram of completely converted DFA. — Figure 17.3.26.

Exercises 17.3.3 Exercises

1.

Give DFAs that accept the following languages over \(\Sigma =\ab\text{.}\)

\begin{equation*} L_2= L(a^*b^*) \end{equation*}
\begin{equation*} L_3= \{ x \ | \ n_a(x)+n_b(x) \text{ is even }\} \end{equation*}
\begin{equation*} L_4= \{ x \ | \ n_a(x) \text{ is a multiple of 5 }\} \end{equation*}
\begin{equation*} L_5= \{ x \ | \ x \text{ does not contain the substring } abb\} \end{equation*}
\begin{equation*} L_6= \{ x \ | \ x \text{ has no } a \text{'s in even positions}\} \end{equation*}
\begin{equation*} L_7 = L(aa^* \REOR aba^*b^*) \end{equation*}

2.

What languages do the following DFAs accept?

Transition diagram for exercise 2(a). — Figure 17.3.27.

Transition diagram for exercise 3(b). — Figure 17.3.28.

3.

Let \(\Sigma=\{0,1\}\text{.}\) Give a DFA that accepts the language

\begin{equation*} L = \{ x \in \Sigma^* \ | \ x \text{ is in binary }, 3|x \}. \end{equation*}

4.

What language does the NFA in Example 17.3.23 accept?

5.

Give a DFA that accepts the language accepted by the following NFA.

NFA diagram for exercise 5. — Figure 17.3.29.

6.

Give a DFA that accepts the language accepted by the following NFA. (Be sure to note that, for example, it is possible to reach both \(q_1\) and \(q_3\) from \(q_0\) on consumption of an \(a\text{,}\) because of the \(\varep\) -transition.)

NFA diagram for exercise 6. — Figure 17.3.30.

Prev Top Next