1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 15
Текст из файла (страница 15)
This problem refers to Problems 2.1.5 and 2.1.6. Show that if f : ~* f-t ~* isa function that can be computed by a deterministic finite-state transducer,then {(w, f (w)) : W E ~*} is a set of pairs of strings accepted by somedeterministic two-tape finite automaton.2.1. 7. We say that state q of a deterministic finite automaton M = (K, ~,J, qo, F)is reachable if there exists W E ~* such that (qo, w) f-M (q, e). Show thatif we delete from NI any nonreachable state, an automaton results thataccepts the same language.
Give an efficient algorithm for computing theset of all reachable states of a deterministic finite automaton.liiJNONDETERMINISTIC FINITE AUTOMATAIn this section we add a powerful and intriguing feature to finite automata.This feature is called nondeterminism, and is essentially the ability to changestates in a way that is only partially determined by the current state and inputsymbol.
That is, we shall now permit several possible "next states" for a givencombination of current state and input symbol. The automaton, as it reads theinput string, may choose at each step to go into anyone of these legal next states;the choice is not determined by anything in our model, and is therefore said tobe nondeterministic. On the other hand, the choice is not wholly unlimitedeither; only those next states that are legal from a given state with a given inputsymbol can be chosen.Chapter 2: FINITE AUTOMATA64Such nondeterministic devices are not meant as realistic models of computers. They are simply a useful notational generalization of finite automata,as they can greatly simplify the description of these automata.
Moreover, weshall see below that nondeterminism is an inessential feature of finite automata:every nondeterministic finite automaton is equivalent to a deterministic finiteautomaton. Thus we shall profit from the powerful notation of nondeterministicfinite automata, always knowing that, if we must, we can always go back andredo everything in terms of the lower-level language of ordinary, down-to-earthdetermipistic automata.aFigure 2-4To see that a nondeterministic finite automaton can be a much more convenient device to design than a deterministic finite automaton, consider thelanguage L = (ab U aba)*, which is accepted by the deterministic finite automaton illustrated in Figure 2-4.
Even with the diagram, it takes a few moments toascertain that a deterministic finite automaton is shown; one must check thatthere are exactly two arrows leaving each node, one labeled a and one labeled b.And some thought is needed to convince oneself that the language accepted bythis fairly complex device is the simple language (ab U aba) *. One might hope tofind a simpler deterministic finite automaton accepting I,; unfortunately, it canbe shown that no deterministic finite automaton with fewer than five states canaccept this language (later in this chapter we develop methods for minimizingthe number of states of deterministic finite automata).However, L is accepted by the simple nondeterministic device shown inFigure 2-5.
When this device is in state ql and the input symbol is b, thereare two possible next states, qo and q2' Thus Figure 2-5 does not represent adeterministic finite automaton. Nevertheless, there is a natural way to interpretthe diagram as a device accepting L. A string is accepted if there is some wayto get from the initial state (qo) to a final state (in this case, qo) while followingarrows labeled with the symbols of the string.
For example ab is accepted bygoing from qo to ql, to qo; aba is accepted by going from qo to ql to q2, to qo.Of course, the device might guess wrong and go from qo to ql to qo to ql on652.2: Nondeterministic Finite AutomatabFigure 2-5input aba, winding up in a nonfinal state; but this does not matter, since thereis some way of getting from the initial to a final state with this input.
On theother hand, the input abb is not accepted, since there is no way to get from qoback to qo while reading this string.Indeed, you will notice that from qo there is no state to be entered when theinput is b. This is another feature of nondeterministic finite automata: just asfrom some states with some inputs there may be several possible next states, sowith other combinations of states and input symbols there may be no possiblemoves.We also allow in the state diagram of a nondeterministic automaton arrowsthat are labeled by the empty string e. For example, the device of Figure 2-6accepts the same language L. From q2 this machine can return to qo either byreading an a or immediately, without consuming any input.Figure 2-6The devices illustrated in Figures 2-5 and 2-6 are instances of the followinggeneral type:Definition 2.2.1: A nondeterministic finite automaton is a quintuple M(K,~, Ll, s, F), whereK is a finite set of states,~ is an alphabet,=Chapter 2: FINITE AUTOMATA66s E K is the initial state,F <:;:.
K is the set of final states, andLl, the transition relation, is a subset of K x(~U {e}) x K.Each triple (q, u,p) ELlis called a transition of 111 -the formal counterpart of an arrow labeled a from q to p in the state diagram of M. If M is instate q and the next input symbol is a, then M may next follow any transitionof the form (q, a,p) or (q, e,p); if a transition (q, e,p) is followed, then no inputsymbol is read.The formal definitions of computations by nondeterministic finite automataare very similar to those for deterministic finite automata.
A configuration ofM is, once again, an element of K x ~'. The relation f-!vJ between configurations(yields in one step) is defined as follows: (q, w) f-!vJ (q', w') if and only if thereis au E ~ U {e} such that w = uw' and (q,u,q') E Ll. Note that f-!vJ need notbe a function; for some configurations (q,w), there may be several pairs (q',w')-or none at all- such that (q,w) f-!vJ (q',w'). As before, f-M is the reflexive,transitive closure of f-!vJ and a string w E ~.
is accepted by M if and only ifthere is a state q E F such that (s,w) f-M (q,e). Finally L(M), the languageaccepted by M, is the set of all strings accepted by M.Example 2.2.1: Figure 2-7 shows one of several possible nondeterministic finite automata that accept the set of all strings containing an occurrence of thepattern bb or of the pattern bab (see Section 2.5 for a systematic study of automata for detecting patterns in the input string). Formally, this machine is(K,~, Ll, s, F), whereK = {qO,ql,q2,q3,q4},~ = {a,b},s = qo,andLl = {(qo,a,qo), (qo,b,qo), (qO,b,ql),(ql, b, q2), (ql , a, q3), (q2, e, q4),(q3, b, q4), (q4, a, q4), (q4, b, q4)}.When M is given the string bababab as input, several different sequences ofmoves may ensue. For example, III may wind up in the nonfinal state qo in case672.2: Nondeterministic Finite Automataa,bbbaeba,bFigure 2-7the only transitions used are (qO, a, qo) and (qO, b, qo):(qo, bababab) f- M (qo, ababa b)f- M (qO, babab)f- M (qO, abab)f- M (qO, e)The same input string may drive M from state qo to the final state q4, andindeed may do so in three different ways.
One of these ways is the following.(qo, bababab) f- M (ql, ababab)f- M (q3, babab)f- M (q4, abab)f- M (q4, bab)f- M (q4, ab)f-M (q4, b)f-M (q4, e)Since a string is accepted by a nondeterministic finite automaton if and only ifthere is at least one sequence of moves leading to a final state, it follows thatbababab E L(M).\;Example 2.2.2: Let ~ be the alphabet ~ = {al,"" an}, containing n symbols,where n ~ 2, and consider the following language:L = {w : there is a symbol a; E~not appearing in w}.68Chapter 2: FINITE AUTOMATAThat is, L contains all those strings in ~* that fail to contain occurrences ofall symbols in~.
For example, if n = 3, then e,al,a2,alala3al E L, buta3al a3al a2 ~ L.It is relatively easy to design a nondeterministic finite automaton M =(K, ~,6., s, F) that accepts this rather sophisticated language. Here K containsn + 1 states K = {s, ql, q2, ... , qn}, all accepting (F = K). 6. has two kindsof transitions (see Figure 2-8 for an illustration of the case n = 3). The initialtransitions are those of the form (s, e, qi) for all i, 1 ::; i ::; n, and the maintransitions are all triples of the form (qi,aj,qi), where if- j. This completes thelist of transitions in 6..Figure 2-8Intuitively, M starts its operation on an input by guessing the symbol missing from the input, and passing to the corresponding state. If the symbol selectedis ai, then state qi is visited.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
