1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 14
Текст из файла (страница 14)
It turns out thattheir theory is rich and elegant, and when we understand it we shall be in abetter position to appreciate exactly what the addition of auxiliary memoryaccomplishes in the way of added computational power.A further reason for studying finite automata is their applicability to thedesign of several common types of computer algorithms and programs. Forexample, the lexical analysis phase of a compiler (in which program units suchas 'begin' and '+' are identified) is often based on the simulation of a finiteautotnaton. Also, the problem of finding an occurrence of a string within another--for example, whether any of the strings air', water, earth, and fire occur in thetext of Elements of the Theory of Computation t - can also be solved efficientlyby methods originating from the theory of finite automata.InputtapeFinitecontrolFigure 2-1Let us now describe the operation of a finite automaton in more detail.Strings are fed into the device by means of an input tape, which is divided intosquares, with one symbol inscribed in each tape square (see Figure 2-1).
Themain part of the machine itself is a "black box" with innards that can be, atany specified moment, in one of a finite number of distinct internal states. Thisblack box -called the finite control- can sense what symbol is written at anyposition on the input tape by means of a movable reading head. Initially, thereading head is placed at the leftmost square of the tape and the finite control isset in a designated initial state. At regular intervals the automaton reads onesymbol from the input tape and then enters a new state that depends only on thetAll four of them do, three of them outside this page.572.1: Deterministic Finite Automatacurrent state and the symbol just read -this is why we shall call this device adeterministic finite automaton, to be contrasted to the nondeterministic versionintroduced in the next section.
After reading an input symbol, the reading headmoves one square to the right on the input tape so that on the next move it willread the symbol in the next tape square. This process is repeated again andagain; a symbol is read, the reading head moves to the right, and the state ofthe finite control changes. Eventually the reading head reaches the end of theinput string. The automaton then indicates its approval or disapproval of whatit has read by the state it is in at the end: if it winds up in one of a set of finalstates the input string is considered to be accepted. The language acceptedby the machine is the set of strings it accepts.When this informal account is boiled down to its mathematical essentials,the following formal definition results.Definition 2.1.1: A deterministic finite automaton is a quintuple M(K,~, J, s, F) whereK is a finite set of states,~ is an alphabet,s E K is the initial state,F ~ K is the set of final states, andJ, the transition function, is a function from K x~to K.The rules according to which the automaton M picks its next state areencoded into the transition function.
Thus if M is in state q E K and thesymbol read from the input tape is a E ~, then J(q, a) E K is the uniquelydetermined state to which K passes.Having formalized the basic structure of a deterministic finite automaton,we must next render into mathematical terms the notion of a computation byan automaton on an input string. This will be, roughly speaking, a sequenceof configurations that represent the status of the machine (the finite control,reading head, and input tape) at successive moments.
But since a deterministicfinite automaton is not allowed to move its reading head back into the part ofthe input string that has already been read, the portion of the string to the leftof the reading head cannot influence the future operation of the machine. Thusa configuration is determined by the current state and the unread part of thestring being processed. In other words, a configuration of a deterministicfinite automaton (K,~, J, s, F) is any element of K x ~*.
For example, theconfigur ation illustrated in Figure 2-1 is (q2, ababab).The binary relation I- M holds between two configurations of 111 if and onlyif the machine can pass from one to the other as a result of a single move. Thusif (q,w) and (q',w') are two configurations of M, then (q,w) I-M (q',w') if andonly if w = aw' for some symbol a E ~, and J(q, a) = q'. In this case we sayChapter 2: FINITE AUTOMATA58that (q,w) yields (q',w') in one step. Note that in fact I-M is a function fromK x ~+ to K x ~*, that is, for every configuration except those of the form (q, e)there is a uniquely determined next configuration.
A configuration of the form(q, e) signifies that M has consumed all its input, and hence its operation ceasesat this point.We denote the reflexive, transitive closure of I-M by I-~; (q,w) I-~ (q',w')is read, (q,w) yields (q',w') (after some number, possibly zero, of steps).
Astring w E ~* is said to be accepted by M if and only if there is a state q E Fsuch that (s, w) I-~ (q, e). Finally, the language accepted by M, L(M), isthe set of all strings accepted by M.Example 2.1.1: Let M be the deterministic finite automaton (K,~, J, s, F),whereK={qo,qd,~ = {a,b},s = qo,F = {qo},and J is the function tabulated below.q(JJ(q, (J)qoqoqlqlababqoqlqlqoIt is then easy to see that L( M) is the set of all strings in {a, b} * that havean even number of b's.
For M passes from state qo to ql or from ql back to qowhen a b is read, but 111 essentially ignores a's, always remaining in its currentstate when an a is read. Thus M counts b's modulo 2, and since qo (the initialstate) is also the sole final state, M accepts a string if and only if the numberof b's is even.If M is given the input aabba, its initial configuration is (qo, aabba). Then(qo, aabba) I-M (qo, abba)I-M (qo,bba)I-M (ql,ba)I-M (qO, a)I- M (qo, e)Therefore (qo, aabba) I-j,{ (qo, e), and so aabba is accepted by M.
<:;2.1: Deterministic Finite Automata59Figure 2-2The tabular representation of the transition function used in this exampleis not the clearest description of a machine. We generally use a more convenientgraphical representation called the state diagram (Figure 2-2). The statediagram is a directed graph, with certain additional information incorporatedinto the picture.
States are represented by nodes, and there is an arrow labeledwith a from node q to q' whenever J(q, a) = q'. Final states are indicated bydouble circles, and the initial state is shown by a >. Figure 2-2 shows the statediagram of the deterministic finite automaton of Example 2.1.1.Example 2.1.2: Let us design a deterministic finite automaton M that acceptsthe language L( M) = {w E {a, b} * : w does not contain three consecutive b's}.We let M = (K,"L"J,s,F), whereK = {qo, ql , q2, q3 } ,"L,={a,b},s = qo,F = {qO,ql,q2},and J is given by the following table.q(JJ(q, (J)qoqoqlqlq2q2q3q3ababababqoqlqoq2qoq3q3q3The state diagram is shown in Figure 2-3. To see that M does indeed acceptthe specified language, note that as long as three consecutive b's have not beenread, M is in state qi (where i is 0, 1, or 2) immediately after reading a run ofi consecutive b's that either began the input string or was preceded by an a. Inparticular, whenever an a is read and M is in state qo, ql, or q2, M returns toChapter 2: FINITE AUTOMATA60its initial state qo.
States qo, ql, and q2 are all final, so any input string notcontaining three consecutive b's will be accepted. However, a run of three b'swill drive AI to state q3, which is not final, and AI will then remain in this stateregardless of the symbols in the rest of the input string. State q3 is said to bea dead state, and if AI reaches state q3 it is said to be tmpped, since no furtherinput can enable it to escape from this state.OFigure 2-3Problems for Section 2.12.1.1. Let M be a deterministic finite automaton. Under exactly what circumstances is e E L(AI)? Prove your answer.2.1.2.
Describe informally the languages accepted by the deterministic finite automata shown in the next page.2.1.3. Construct deterministic finite automata accepting each of the following languages.(a) {w E {a, b}' : each a in w is immediately preceded by a b}.(b) {w E {a,b}' : w has abab as a substring}.(c) {w E {a, b}' : w has neither aa nor bb as a substring}.(d) {w E {a,b}' : w has an odd number of a's and an even number of b's}.(e) {w E {a,b}' : w has both ab and ba as substrings}.2.1.4.
A deterministic tinite-state transducer is a device much like a deterministic finite automaton, except that its purpose is not to accept strings orlanguages but to transform input strings into output strings. Informally, itstarts in a designated initial state and moves from state to state, dependingon the input, just as a deterministic finite automaton does. On each step,however, it emits (or writes onto an output tape) a string of zero or one ormore symbols, depending on the current state and the input symbol. Thestate diagram for a deterministic finite-state transducer looks like that for adeterministic finite automaton, except that the label on an arrow looks like612.1: Deterministic Finite Automataa(1....--------~Oba,ba,ba,ba, baaaba,ba,bbbaabaChapter 2: FINITE AUTOMATA62bibI1Faa~bibalealw, which means "if the input symbol is a, follow this arrow and emit output w".
For example, the deterministic finite-state transducer over {a, b}shown above transmits all b's in the input string but omits every other a.(a) Draw state diagrams for deterministic finite-state transducers over {a, b}that do the following.(i) On input w, produce output an, where n is the number of occurrencesof the substring ab in w.(ii) On input w, produce output an, where n is the number of occurrencesof the substring aba in w.(iii) On input w, produce a string of length w whose ith symbol is an a ifi = 1, or if i > 1 and the ith and (i - l)st symbols of ware different;otherwise, the ith symbol of the output is a b. For example, on inputaabba the transducer should output ababa, and on input aaaab it shouldoutput abbba.(b) Formally define(i) a deterministic finite-state transducer;(ii) the notion of a configuration for such an automaton;(iii) the yields in one step relation f- between configurations;(iv) the notion that such an automaton produces output u on input w;(v) the notion that such an automaton computes a function.2.1.5.
A deterministic 2-tape finite automaton is a device like a deterministic finiteautomaton for accepting pairs of strings. Each state is in one of two sets;depending on which set the state is in, the transition function refers to thefirst or second tape. For example, the automaton shown below accepts allpairs of strings (Wl,W2) E {a,b}* x {a,b}* such that IW21 = 2lwll·......-..---------i,,!r-----------------------..,,a,b!a,b~~i!a,b,,,___ .. __________ !States forfirst tape,,,L _.. _..
_____________ .. __ .. ___ _States forsecond tape2.2: Nondeterministic Finite Automata63(a) Draw state diagrams for deterministic 2-tape finite automata that accepteach of the following.(i) All pairs of strings (WI,W2) in {a,b}* x {a,b}* such that IWII = IW21,and wI(i) i- w2(i) for all i.(ii) All pairs of strings (WI, W2) in {a, b}' x {a, b} * such that the length ofW2 is twice the number of a's in Wi plus three times the number of b'sin Wi.(iii) {(anb,anb m ) : n,m;:::: O}.(iv) {(anb, amb n ) : n, m ;:::: O}.(b) Formally define(i) a deterministic 2-tape finite automaton;(ii) the notion of a configuration for such an automaton;(iii) the yields in one step relation f- between configurations;(iv) the notion that such an automaton accepts an ordered pair of strings;(v) the notion that such an automaton accepts a set of ordered pairs ofstrings.2.1.6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
