Figure 3.10: A generic one-state automaton

4. The desired regular expression is the sum (union) of all the expressions derived from the reduced automata for each accepting state, by rules (2) and (3).

Start (Z 1 0Л 0,1

~(aJ-

Figure 3.11; An NFA accepting strings that have a 1 either two or three positions from the end

Example 3.61 Let us consider the NFA in Fig. 3.11 that accepts all strings of Os and Vs such that either the second or third position from the end has a 1. Our first step is to convert it to an automaton with regular expression labels. Since no state elimination has been performed, all we have to do is replace the labels 0,1 with the equivalent regular expression 0 H- 1. The result is shown in Fig. 3.12.

0 + 1

Start I 0+1 0 +1

-Ha}-Чв

Figure 3.12: The automaton of Fig. 3.11 with regular-expression labels

Let us first eliminate state B. Since this state is neither accepting nor the start state, it will not be in any of the reduced automata. Thus, we save work if we eliminate it first, before developing the two reduced automata that correspond to the two accepting states.

State В has one predecessor, A, and one successor, C. In terms of the regular expressions in the diagram of Fig. 3.7: Qi - 1. Л = 0 + 1, = 0 (since the arc from .4 to С does not exist), and 5 = 0 (because there is no

strings that it accepts is R*

Start

Figure 3.13: Eliminating state В

Now, we must branch, eliminating states С and D in separate reductions. To eliminate state C, the mechanics are sindlar to those we performed above to eliminate state B, and the resulting automaton is shown in Fig. 3.14.

0 + 1

Start 4) 1(0 + 1)(0 + 1)

Figure 3.14; A two-state automaton with states A and D

In terms of the generic two-state automaton of Fig. 3.9, the regular expressions from Fig, 3.14 are; /? = 0 + 1, 5 1(0 + 1)(0 + 1), T - 0, and U = 0. The expression U can be replaced by e, i,e eliminated in a concatenation; the justification Is that 0* - e, as we discussed above. .Also, the expression SWT is equivalent to 0, since T, one of the terms of the concatenation, is 0. The generic expression [R + SU*TYSU thus simplifies in this case to R*5, or (0 + 1)*1(0 + 1)(0 + 1). In informal terms, the language of this expression is any string ending in 1, followed by two symbols that are each either 0 or 1. That language is one portion of the strings accepted by the automaton of Fig, 3.11: those strings whose third position from the end ha.s a 1.

Now, we nuist start again at Fig. 3.13 and eliminate state D instead of C. Since D has no successors, an inspection of Fig. 3.7 tells us that there will be no changes to arcs, and the arc from С to D is eliminated, along with state D. The resulting two-state automaton is shown in Fig, 3.15.

loop at state B). As a result, the exjiresRion on the new arc from A to С is Й +1(0 + 1).

To simplify, we first eliminate the initial Й, which may be ignored in a union. The expression thus becomes 10*(0 + 1). Note that the regular expression 0* is equivalent to the regular expression f, since

L(0*) = {e} и L(0) и L(0)L(0) U - -

Since all the terms but the first are empty, we see that L(0*) - {f}, which is the same as L{f-). Thus, 10*(0 + 1) is equivalent to 1(0 + 1), which is the expression wc use for the arc Л. -) С in Fig. 3,13.

0 + 1

Start 4) 1(0 + 1) 0 + 1

Ordering the Ehmination of States

As we observ(;d in Example 3.6, when a state is neither the Start state nor an accepting state, it gets eliminated in all the derived automata. Thus, one of the advantages of the state-elimination process compared with the mei:lianic;al gencration of regular expressions thar. we described in Section 3,2.1 is that w4> can .start by eliminating all the states that, are neither start nor accepting, once and for all. We only have to begin duplicating the reduction effort when we need to eliminate some accepting states.

Even there, we can combine some of the effort. For instance, if there are three ncrcptmg statics p, q, and 7 , we can eliminate p and then branch to eliminate either q or r. thus producing the automata for acee])ting states r and q, respectively. We then start again with all three accepting states and eliminate both q and r to get the automaton for p.

0 + 1

Start iJ 1(0 + t)

Figure 3,15: Two-slate automaton resulting from tlic elimination of D

This automaton is very much like that of Fig. 3.14; only the label on the arc from the start state to the accepting state is different. Thus, we can apply the rule for two-state autoniata and simplify the expression to get (0 + (0 +1), This expression represents the other type of string the automaton accepts: those with a 1 in the second position from the end.

All that remains is to sum the two expressions to get the expression for the. entire automaton of Fig, 3,11, This expr(;ssion is

(0 + 1)*1(0 -H 1) + (0 -h 1)1(0 + 1)(0 -b 1)

□

3.2.3 Converting Regular Expressions to Automata

We shall now complete the plan of Fig, 3.1 by showing that every language L that is LiR) for some regular (:x])ression is also L{E) for some e-NFA E. The proof is a structural induction on the expression R. We start by showing how to <:onstni<:t automata for the ha.sis expressions: single symbols, e, and 0, We then show h()w to combine these automata into larger automata that accept the union, concatenatiou. or closure of the language accepted by smaller automata.