Java Reference
In-Depth Information
Example. Consider the regular expression, (ajb)ab. This describes a language over the
alphabet fa;bg; it is the language consisting of all strings starting with either an a or a b,
followed by zero or more a's, and ending with a b.
An FSA F that recognizes this same language is F = (;S;s 0 ;M;F), where =
fa;bg;S = f0; 1; 2g;s 0 = 0;M = fm(0;a) = 1;m(0;b) = 1;m(1;a) = 1;m(1;b) = 2g;F =
f2g.
The corresponding state transition diagram is shown in Figure 2.7.
FIGURE 2.7 An FSA recognizing (ajb)ab.
An FSA recognizes strings in the same way that state transition diagrams do. For exam-
ple, given the input sentence baaab and beginning in the start state 0, the following moves
are prescribed:
m(0;b) = 1 =) in state 0 we scan a b and go into state 1,
m(1;a) = 1 =) in state 1 we scan an a and go back into state 1,
m(1;a) = 1 =) in state 1 we scan an a and go back into state 1 (again),
m(1;a) = 1 =) in state 1 we scan an a and go back into state 1 (again), and
m(1;b) = 2 =) nally, in state 1 we scan a b and go into the nal state 2.
Each move scans the corresponding character. Because we end up in a final state after
scanning the entire input string of characters, the string is accepted by our FSA.
The question arises, given the regular expression, have we a way of automatically gen-
erating the FSA? The answer is yes! But first we must discuss two categories of automata:
Non-deterministic Finite-State Automata (NFA) and Deterministic Finite-state Automata
(DFA).
2.5 Non-Deterministic Finite-State Automata (NFA) versus De-
terministic Finite-State Automata (DFA)
The example FSA given above is actually a deterministic finite-state automaton.
Definition 2.3. A deterministic finite-state automaton (DFA) is an automaton where there
are no -moves (see below), and there is a unique move from any state, given a single input
symbol a. That is, there cannot be two moves:
m(r;a) = s
m(r;a) = t
where s 6= t. So, from any state there is at most one state that we can go into, given an
incoming symbol.
 
Search WWH ::




Custom Search