Section 9.3 Finite-State Machines
735
PrACtiCe 49 Describe the sets recognized by the machines in Figure 9.8.
figure 9.8
■
In Practice 49d, state s 3 is a “dead” state from which there is no recovery. The
appearance of a 0 in states s 0 , s 1 , or s 2 irrevocably ruins the pattern the machine
is able to recognize. In contrast, the machine of Example 31 (or any machine that
recognizes strings with a certain ending) will never have a dead state because
there is always hope that subsequent input will match the ending pattern.
regular sets and Kleene’s theorem
We want a compact, symbolic way to describe sets such as those appearing in the
answer to Practice 49. We will describe such sets by using regular expressions;
each regular expression describes a particular set. First, we define what regular
expressions are; then we will see how a regular expression describes a set. We assume here that I is some finite set of symbols; later I will be the input alphabet for
a finite-state machine.
Definition rEGuLAr ExPrEssions ovEr I
regular expressions over I are the
1. symbol [ and the symbol l.
2. symbol i for any i [ I.
3. expressions (AB), (A ~ B), and (A)* if A and B are regular expressions.