Finite-State Machines as Recognizers WJ. Barnier242 Tas for Teaching 1986 IureeMopuLar Descrurrion SHetr Time Auton MacHEMAries Fete: Aprucaions Fin: ‘Tagcer AUDIENCE ApsrRacr: Prexeguistres MAP Unit 671 FINITE-STATE MACHINES AS RECOGNIZERS We. Barnie Mathematice and Computer Seence Sonoma State Univerty Rohnert Park, CA 94828 Discrete Mathematics Computer Ssence Stadente ina fest or second computer scence course This medile develops the concep of fite-tate machine through nomber examples. IF snteodsces regular cexpresions and esablahes their connection with Erte sate machines. Famllanty wath modulaearhmeti binary arthinete. and Pascal syntax, plus a tolerance for “chasing around!” in lagrams © Copyright 1986, 1987 by COMAP. In, All rights reservedFinite-State Machines as Recognizers WJ. Barnier Mathematics and Computer Science Sonoma State University Rohnert Park, CA 94928 Table of Contents 1. INTRODUCTION... cseeeee DEFINITION AND EXAMPLES teseeeneesee EXPRESSIONS .....400c00200 0+ EXAMPLES WITH BINARY NUMBERS ae LIMITATIONS OF FINITE-STATE MACHINES. - PERSPECTIVE. WHERE FSM FIT IN| REFERENCES FOR FURTHER READING . SOLUTIONS TO THE EXERCISESa Tinh for Teaching 186 MODULES AND MONOGRAPHS IN UNDERGRADUATE MATHEMATICS AND ITS APPLICATIONS ProrecT (UMAP? “The goal of UMAP was to develop, through 2 community of users and developers. a system of instractional madules in undergraduate mathematics land its applications to be used to supplement existing courses and from which complete courses may eventually be built, The Project was guided by a National Advisory Board of mathematicians scientists, and educators. UMAP was funded by a grant from the National Science Foundation and is now supported by the Consortium for Mathematics and Its Applications, lnc (COMP), 2 nonproft corporation engaged in esearch and development in mathematics education COMAP Starr Solomon A. Garfunkel Executive Director, COMAP. Laurie W. Aragon ‘Business Development Manager Philp A. McGaw Production Manager Nancy Hawley Copy Editor ‘Annemarie S. Morgan Administrative Assistant Brian Sterling Fulfilment Coordinator UMAP ApvisoRY BOARD Steven J. Brams New York University Llayron Clarkson Texas Southern University Donald A, Larson SUNY at Buffalo R, Duncan Luce Harvard University Frederick Mosteller Harvard University George M. Miller Nassau Community College Walker Sears University of Michigan Press Arnold A. Straseenburg SUNY at Stony Brook ‘Alfeed B. Willeox Mathematical Assocation of America“Fnitestate machines model computers with memory’ “A very nice example isthe New York City subooy turnstile Fine Sate Machines 25 Introduction “The history of finite-state machines FSM) (also called finite-state automata) can be traced back to a model of neural networks introduced by McCulloch and Pitts [19431 Finte-state machines are the most fundamental and simple of the automata models, They are useful in the design of compilers for computer languages such as Pascal Finite-state machines model computers with memory. They also read input from a fnite set of symbols and produce output. The ‘examples of FSMs that we consider will all have a very small number of states. The states act as a form of memory: as a rule, the fewer the states, the smaller the “memory.” Is such a model even qualitatively adequate for modeling the behavior of a modern digital computer. which can have millions of bytes of memory and billions of bytes of secondary storage? It is not the size of memory that keeps a computer from being aan FSM, In fact, a computer without its auxiliary disks and tapes is lan FSM: the states are all the possible states of its memory. In other words, the fact that an FSM has finitely many states does not Keep it from having a huge number; finite does not necessary mean smal ‘A very nice example is the New York City subway turnstile {Hayes 1983] It has four arms at waist level, which rotate one quarter turn when unlocked and admit one person. The turnstile is initially locked. Depositing a token unlocksit, Pushing on the unlocked turnstile admits one person and leaves it locked. Depositing a token in an unlocked turnstile leaves it unlocked. Pushing on 2 locked turnstile leaves it locked. To model the turnstile as 2 finite-state machine, we introduce symbolism similar to that of later examples. Let 5p be the locked state, s, be the unlocked state, f stand for token depost, and p stand for pushing the turnstile. In Figure 1, each state is symbolized by a node with a label (either 5, or 5), and the directed arcs symbolize transitions from one state to another. Note that each transition depends on the present state and the input: Oo The finite set of symbols is {f,p} and the output set is (locked, unlocked}. This machine has only two states and consequently a very Figure t46 Toul for Tracing 1985 small amount of memory. Knowing the machine is in state sp or state scan only tell us what the last input symbol was. Hence this machine temembers only the last input. For example, depositing two tokens without pushing for admission between the deposits is equivalent to depositing one token. Machines as recognizers produce output that indicates whether an input sequence is acceptable or not. In the turnstile example, we right decide that acceptable strings are exactly those that, starting in so leave the machine in s, (unlocked). So the strings (read left to right) “pp” and “pit” are both acceplable, but “tty” is not acceptable. Any sequence that is acceptable to a given machine may be thought of as syntactically correct. Those sequences not acceptable are considered syntactically incorrect. ‘Checking for syntax errors is one task a language compiler per- forms.One of the main reasons that the concept of finite-state machines js important to computer science is its usefulness in designing the syntax-checking part of a compiler, OF course, when 2 compiler is designed for a language, the syntax rules, and hence the acceptable ‘sequences of input symbols, are given. Itis the job of the designer to create a finite-state machine that accepts only syntactically correct sequences. The examples that follow are in the spirit ofthis important application in computer science Definition and Examples Definition. A finite-state machine (FSM) is a S-tuple M = (5, V, 8, F 6) where: Sis a finite set of states: V is a finite set of input symbols; £15 X V=>S is the next-state fiction; Fe Sis the set of reogwizing states; and So Sis a designated state called the initial stat. Example 1, The turnstile revisited. Mis described by; $= {S, s:b: V = {Eph g:5 X V=> S defined by ths, = 61860.) = 50 $6.0 = 9661.0) = 5 FatedFonte Sate Machines 247 It is usually more convenient to write the next-state function at a state table: When we write ¢4s,,p)= 50, we mean that when the machine is in state 5; and gels input p, it makes a transition to state 55 How does a finite-state machine respond to 2 string of inputs? ‘We label the states so that we can assume that the FSM always starts in state 50. Strings will be processed (read and input) left to right. If our FSM gets an input string such as tpt it will tart in state 5, and move consecutively to 51, 5, $1, 1 a8 it reads #,p, fin order ©-O-O-O-O Another way to define a finite-state machine is to show it as a directed graph, called a stale graph; this is the way we originally introduced the turnstile example. Each state is a node. The next-state function is shown by placing a dected arc labeled x from states to state o(s, x) (Figure 3), It is also customary to show any recognizing states a8 nodes with double boundaries, Figure 4 shows the turnstile example again, using this convention. Example 2. Define M = (5, V, 5, Fs) by §= {50 5, Sah V = (2,8): F= tay) and the next-state Function is defined by either the state graph or the next-state table in Figure 5. Figure 2 Figure 3. Figure &a Tiny for Teaching 1986 Figure s Practice problem. Refer to Example 2 In what state will the finite-state machine be after each of the following input strings is processed? i, abaab it aababa Solation. i. so is, Definition, -M = (5, V,¢,F 59) acepts a string, of inputs from V if starting in state sq, M i in a recognizing state after processing the string, The set of strings which an FSM accepts is the set recognized by the FSM. ‘What strings are accepted by the FSM of Example 2? This fie state machine accepts strings of a's and b's with either 1 4, or 4 4°, or 7 a's, etc. With modular arithmetic notation, we can describe the set recognized by the FSM of Example 2 as the set of strings of a's and bs with k a's, where & = 1 (mod 3. It is important to detect errors that can occur when data is stored or transmitted. Data within computers is stored or transmitted in ‘groups of bits (0's and 1's). Strings of O's and 1's are commonly called bit strings. Each group of bits is called a word. To facilitate the detection of errors, an extra bit, called a parity bi, is frequently included in each word. For example, if each word is made up of 8 bits (7 data bits plus 1 parity bit, the pority bit could be chosen so that all words have an. ‘even number of 1's, Each word is said to have even party in this case. ‘A single bit ecror that occurs in a word is easily detected, since the parity of that word will not be even (OF course, we could just as well choose to give each word an todd number of 1's lodd party. In order that parity bits be effective, we need to test each word for parity. That is what the FSM of following example does: it is @ parity checker. Example 3. A parity checker ‘Define M by the stage graph of Figure 6 4Finite Sate Machines 249 Figure 6 We see that 5 = {60,51}, V = {0, 1}, and F = {so}. State 5, stands for “have read an even number of 1's" and 5, stands for “have read an odd number of 1's" Practice problem. Refer to Example 3. Draw the next-state table for thie FSM. Solution. Practice problem. Refer to Example 3.Use modular arithmetic notation to write the set of strings recognized by this FSM. Solution. Bit strings with k 1's, where k= 0 (mod 2). Practice problem. Make the necessary change in the FSM of Example ‘3 #0 that it accepts bit strings of odd parity ‘To make the directed graphs easier to read, duplicate arcs with diferent labels will be eliminated in favor of a single arc labeled with the set of labels ofall the arcs (Figure 7). Orr memes OO Figure 7 Example 4. We will design an FSM to model an automatic teller machine ‘Our machine will have alphabet D = {0,1.2,...,9} and accept only the string 73 (your secret identification number). The states will be 55 (waiting for frst input), 5, (waiting for second input after correct frst inpub. 52 (correct frst two inputs), and s, (incorrect string). Clearly F = {sz}. Figure 8 shows the state graph. ‘An automatic teller machine used by bank customers for deposits, and withdrawals has each customer's personal identification number 5250 Toul fr Teaching 1986 stored in memory. After the customer's card is inserted, the customer is requested to input the identification number. The machine then either ‘accepts or rejects the number, based on which card has been inserted. Figure 8 Exercises 1 Design 2 finite-state machine that accepts strings of 0's and 1's with EV's.and £= 2 (mod 3) 2, Design a finite-state machine that accepts k O's and kis divisible by 3 ng of O's and 1's with 13. Design finite-state machines that accept strings of 0's and 1's with k's and: a km 3(mod @ b. kis divisible by 4 44. Design a finite-state machine that accepts strings of O's and 1's with E Ve and k= 1 (mod §) or & = 3 (mod 5). 5. Design a finite-state machine that models an automatic teller machine and accepts only the string 916. Let V = {0,1,....9). More Examples and Introduction to Regular Expressions To facilitate our discussion of finite-state machines and the sets accepted by them, we will introduce regular expressions. We state without proof an important fact about regular expressions and finite- state machines:Fini Stt Machines 251 Every set recognized by a finite-state machine can be represented by a regular expression. Conversely, for every set corresponding to a regular expression, there isa finite-state machine that recognizes the set You will also see that regular expressions provide a concise and useful method of defining certain parts of programming languages, Let us consider a finite-state machine that recognizes a set of strings of a's and 8s (Figure 9), How shall we describe the set recognized? Figure 8 By examining the state graph, we see that the strings accepted are exactly those beginning with an «followed by any number (possibly zero) of a's followed by two 4's followed by any number (possibly zero) of B's Using notation developed in what follows, we write this set a6 ‘aa*bbb*. The string aa*Bbb" is a regular expression. We read a"bbb* as: one a then any number of a's: then two b's then any number of 83 ‘We will use the standard notation for the empty set and A for the en string. Definition. Regular expressions over V must satisfy: 1, @ and 2 are both regular expressions. 2, Each element of V isa regular expression 3. IFA and B are regular expressions then so are AB, A v B, and A* ‘At this point we need not attribute any meaning to the symbols AB, AV B, and A*. Following the next definition, you will see what tach denotes. When symbols are placed adjacent to one another, as in ‘AB, the symbols are said to be concatenated. Before showing how regular expressions can be used to represent sets, we need to say something about punctuation, ‘As usual, parentheses must be used for clarity but can be omitted in many cases by observing the following hierarchical rules. Parenthe- sized expressions are of highest precedence, ie., they are performed first. In the absence of parentheses, the hierarchical order is: * is performed first, concatenation second, and v third. Both v and * apply to as little as possible, and operators of the same level of precedence are performed left to rightSo, abv a means (ab) v a, not Mb v a), ab* means ob"), not (ab), av b* means a v (5), not (a v BY, and avbve means (av b) ve Definition. Regular expressions represent sets, called regular sets, by the following rules: 1, D represents the set ©, and A represents (A). (Notice that # A; the first set has no members, while the second has exactly one (the empty string)) 2. For each element x € V, x represents {2} 3. AB represents the set AB; A v B represents the union (Av B) of the sets A and B; A* represents the set of all strings of symbols from A. When A and B are sets, the set AB is the set ofall concatenations ab, where a is any element of A and b is any element of B. In other words, AB = (ab: ac A and b€ B}. For example, if A= {1,2} and Be={z,1,A}, then AB = {1z, 11,1, 21, 21, 2} This definition allows us to consider the regular expression rep- resenting a set a8 identified with that set. So, when de V and we write d as a regular expression, we mean the set {d}. This convention may seem confusing at first, but it is 30 helpful in what follows that itis worth the effort to understand its ramifications ‘The following example will help make the notation clear Example 5. Regular Expression — Set 2 2 4 {a} a fay a fa} a ah o 12,6, bb, bbb, ab {a, ab, abb, ..} ab {ab) avb {0,8} lever {,a,b,ab, ba, } = {a,8)" ave 1a, A,5, 0b...) Practice Problem. Find finite-state machines that recognize iO baPriteSate Machines 253 Solution. Let V = {0,1} {0, 8 40.0), O-8 ; The set of identifiers for Pascal can be written L(L v D)*, where L={A, Z,a,...,2) and D = {0,1,,..,9}. Note that this defines the set of identifiers as strings of letters and digits with a letter on the i tn in of ie Let V be the alphabet available on a given computer, Figure 10 LB vu) v Figure 10 The syntax diagrams found in most textbooks on Pascal are close ‘cousins to finite-state machines. Figare 11 shows one kind of eyntax diagram for an identifier. The paths through the syntax diagram correspond to the paths ofthe state graph that lead to an accepting state. digit ener. 4-3 Teter Figure 11 Example 7. "An FSM that recognizes the set of all valid decimal real numbers, without exponents, in Pascal Valid decimal numbers in Pascal may be preceded by a sign +, ~) and the decimal point must be preceded by at least one digit and followed by at least one digit. Let V= Dv (+...) where D = {0,1,...,9}, Figure 12 shows the state graph 9254 Tos for Teaching 1986 Figure 12 States like +, in Example 4, s, in Example 6, and s, in Example 7 ate frequently called dump (or eror) states. Practice problem. Write a regular expression for the set of valid decimal numbers in Pascal. Solution. (+y — vA)DD*. DD* One of the tasks a compiler performs is checking whether identifiers, decimal numbers, ec, are syntactically correct. This is done in the lexical analyzer part of the compiler. We have already pointed ‘out that finite-state machines are useful in designing the lexical analyzer for a compiler. A compiler is a program that is usually written in a high-level programming language. So, in order to use a finite state machine as part of a compile, iti» necessary to translate it into this high-level language Example 2. Figure 13 gives 2 Pascal program fragment that implements the FSM of Example 7 For the program itisassumed that V isthe character set available on the computer and "ch” is 2 defined variable of type character. “Digits” is a set and “state” isa variable taking on the values 80, St, $2, $3, 54, and $5. devin ‘State := SO; Digits = ['0'...'9"l; read (ch; while not EOLN do begin case state of ‘50: if ch in Digits then state = $2 ‘lee if (ch = +) or (ch = —" then State = ST else State Figure 13. 10Fie Sete Machines 285 St: if chin Digits then State = 52 lee State ™ 55, 52: if chin Digits then State = $2 hse if (ch =~) then State = 53 ele State = 55; 53: Af ch in Digits then State = 54 dle State = 55; 54: Af ch in Digits then State = $4 dae Slate = 55; 55 Stay There *) end; of Case *) read (ch) end; of While ") Uf State = 54 then wrtteln (Valid decimal number.) else watteln (Not a valid decimal number.) end Figure 13 ont) Exercises 6, Let V = (0,1, Design finite-state machines that accept ‘strings beginning with 00 . strings ending with 00 «strings ending with 001 17. In Pascal, valid decimal numbers in exponential form may be preceded by a sign (+,—) and the decimal point (if any) must be preceded by at least one digit and followed by at least one digit ‘An “e" or “E" follows, and this is followed by an optional sign and then at least one digit. Here are some examples: Valid Invalid 30717 3765 ~S2.1E5 3.9650 +3205 7403 0572 74+E3 ‘4. Write a regular expression for the set of all valid decimal real ‘numbers in exponential form. b, Design an FSM that recognizes the set of all valid decimal real ‘numbers in exponential form. 8, Write a computer program to implement the FSM of Exercise 7 nTools for Teaching 1985. 9. In standard Pascal a comment is any string of characters beginning with the character {, ending with the character J. and having no } between { and }. Let L be the set of strings which are valid comments ‘a. Write L as a regular expression . Design an FSM that recognizes L 10. Many Pascal compilers allow the characters (* as an alternate to { and *) a8 an alternate to } for comments, (Set Exerelze 9 above) Let L be the set of all strings that are valid comments when the compiler allows these as delimiters for comments. Note that the Pascal standard prescribes that { and (* must be regarded as ivalent, as also } with *), so that “a comment may begin with (‘and close with or begin with ‘? and close with ‘." a. Write L as a regular expression. b. Design an FSM that recognizes L. 111, Write, as concisely as possible, a regular expression for each set recognized by the given FSM below. Let V = (0, 1) 24. Fre Sle Macks 257 12. Write, as concisely a9 possible, a regular expression for each set recognized by the FSM defined in: & Example 3 b. Example 2 Examples with Binary Numbers How to design an FSM that accepts a-nonnegative integer 1 if and only if is odd? In order for the FSM to process an integer. the integer will be veritten in binary notation, Recall that n = (ob. means 2 {0,1} and n= bya! +2!" +. +b, For example, 35 = (100011), since 351-2" +0-2¢+0-2°+ oee Deh ‘A number n in binary notation is odd if and only if the last digit in its representation is. So we simply design an FSM which accepts strings of 08 and 1s (read left to right) that end with a 1 Practice problem. Draw the state graph for the above FSM. ‘A more dificult problem is to design an FSM that accepts # if and only if m is evenly divisible by 3. ‘As an FSM processes the binary representation of a given integer, it proceeds in stages. For example, et n= 13 = (1101). As the string, 1101 is processed left to right, we see 0+ (0), = 1+ 1D, = 3-4 (110), = 6+ (110: = 13. How does an integer change as the next digit is input? Here are some more examples, with 0 as the next input digi 4 =(100),+ 8 = (1000), $ = (101), + 10 = (1010), “The digit input of 0 seems to double the integer from one stage to the next. What happens when the digit input is 1? Here are two examples with J as input 4 = (100), + 9 = (1001), s In fact, by bs = 2B, Det by o (01); > 11 = (101). BA ‘hols for Teaching 1986 So the integer at each stage is equal to twice the previous integer plus the digit input ample An TSM that accepts m if and only ifn is evenly divigible 3 Let & stand for the integer at each stage of input. The states will be sdk = 0 (mod 3), 6k = 1 (mod 3), and sk = 2 (mod 3). Using fact @ above gives the next-state table in Figure 14. For example, in, the integer j at that stage of input is congruent to 2. If the next digit is a 1, then the integer becomes congruent to 2-j+i=2-2+1=5m2 (mod 3) by (1). Hence (52, 1)= sy. Similarly, gl5,,1)* so since 21+ 13 0(mod 3) Figure 14 To conclude g(s, 1) = 43 in the example above, we used the fact that if j = 2mod 3), then 2° j + 1 2+ 2-4 1 (mod 3) This is a corol- lary of the following two theorems 1, If = ylmod d and 2 = wolmod A) then x + 2= y+ 1 (mod d), ymod d), then w+ x= w+ y (mod d. You are asked to prove these theorems in the following exercise set. In practice, computer scientists would not address the problems in this section by using FSMs. However, these simple problems are {good exercise in learning how to build FSMs IE Exercises 13, In each of the following cases, design a finite-state machine that reads the binary representation of an integer and accepts # if and only if: a misodd b. n= 2 (mod 4) « nis not divisible by 3 “Fine State Macks 259 14, In each of the following cases, design a finite-state machine that reads the binary representation of an integer n and accepts 1 if and only if: a n= 1 (mod 8) Bb. mia not divisible by 5 15, In each of the following cases, design a finite-state machine that reads the binary representation of an integer m and accepts m if and only if: 1. the decimal representation of m ends with a zero 1. the binary representation of m ends with a zero 16. Prove each of the following: a. If x ylmod d) and 20 w(mod d) then r+ z= y + (mod d bi If x=y (mod @), then x = w- y (mod d) (Recall that n= m (mod dif and only if n—m is evenly divisible by 4) Limitations of Finite-State Machines We have seen that finite-state machines can be designed to recog nize any regular set. Conversely, any set recognized by an FSM can be represented by a regular expression. So, for example, there is a finite-state machine to recognize OI" = {w; w= OTL", where n,m are nonnegative integers}. Here we are using the following helpful notation: 6" denotes bb... (x times) and 5° = A ‘This raises a natural question. Is there an FSM to recognize the set {0°1"- a nonnegative integer}? In other words, is this seta regular set? The answer is no. Example 10, The set £={O'1":n a nonnegative integer} is not a regular set Here is a proof by contradiction. Suppose there is an FSM which recognizes L. This FSM must have a finite number of states, say m of them. The string O°*"1"" is in the set, so the given FSM must accept it, While processing the 0's of 0°11", the FSM has to be in some 1s26h Tools for Teaching 1988 state s more than once, since the FSM hes m states through which to process m-+1 0's. So it takes some finite number of 0's to go from s back to s, Let us say 0! will do it; see Figure 18. Then it is not dificult to.see that the FSM must also accept 0'"""‘1""!, But this is acontradic- tion, since O***'1"*" is not in L Figure 15, Perspective: Where the FSMs Fit In Finite-state machines are the least powerful of the automata, Three other kinds of automata are commonly discussed. They are, in increas- ing order of their power a5 recognizers, push-down automata, linear bounded automata, and Turing mackines. Each type of automaton corre- sponds to a specific type of set (the language) that it recognizes. The Turing machine is our best theoretical model of a computer (though the model assumes infinite memory). ‘The four types of languages are named Type 3 (regular), Type 2 (context-free), Type 1 (context-sensitive) and Type 0 (phrase structure) ‘As we have seen, Type 3 languages correspond to finite-state machines. Figure 16. 16Finite Stats Machines 26) ‘Type 2 languages correspond to push-down automata, Type 1 to linear bounded automata, and Type 0 to Turing machines, Most compiler parsers are designed to be recognizers of context-free languages. The language = {0"I":n a nonnegative integer} discussed in Section $ ina Type 2 language but, as we proved, nota Type 3 language. The kinds of languages form the Chomsky hierarchy (Figure 16) References for Further Reading ‘You can learn mote about compiler design by consulting LAho et.al, 1966; Barrett and Crouch 1979; Lewia et.al, 19811 If you are interested ia learning more about formal languages and automata theory, a good place to statis Gersting 1982], More advanced treatments can be found in Backhouse 1979; Hayes 1983; Hopcroft and Ullman 1979; McNaughton 1982: Minsky 1967; Pollack 19821 Gautner 11987) gives an example of a toy that can be viewed as an FSM with a large number of states. ‘Aho, Alfred V., Ravi Sethi, and jeffrey D. Ullman. 1986. Compilers: Priniples, Tuchniqus, and Tools, Reading, MA: Addison-Wesley. Backhouse, R.C. 1979. Syntax of Programming Languages: Theory ond Practice London: Prentice-Hall International Barrett, W.A., and |.D. Crouch, 1979. Compiler Construction: Theory and Practice. CChicager Science Research Assodates. Beckman, FS. 1981, Mathematical Foundations of Programming. Reading, MA: ‘Addison-Wesley. Denning. PJ, 1B. Dennis, and JE Qualtz. 1978, Machines, Languages, and Computation. Englewood Chis, NJ: Prentice-Hall Gautner, T. 1987. The game of Quatrainment, Mathematics Magazine. To opp. Gersting, Judith L. 1982. Mathematical Structures for Computer Science. San Francisco, CA: W. H. Freeman, Hayes, Brian. 1983. Computer recreations: On the Gnite-state machine, a ‘minimal model of mousetraps, ribosomes, and the human soul. Sint ‘American 24916) (December 1983} 19-28, 178, Hoperoft,JE., and }D. Ullman. 1979. fnraduction fo Automate Theory, Languages, end Computation, Reading, MA: Addison-Wesley. Lewis, PM. Il, DJ. Rovenkrantz, and RE. Stearns. 1976. Compiler Design Theory. Reading, MA: Addigon-Wesley. McCullock, W. S. and W. Pitts, 1943. A logical calculus of the ideas of immanent in nervous activity. Ballets of Mathematical Biophysics 5: 115-133. ”282 Tine for Teaching 1986 McNaughton. 1982. EZementry Computability Formal Languages. and Axioms, Englewood Clifs, NI: Prentice-Hall Minsky, M. 1967. Computation: Fite and Infinite Machines. Englewood Clits, Nik Prentice-Hall Pollack, $ Ved, 1982, Studies in Computer Scene. Washington, DC: Mathemat Solutions to the Exercises Bey : : °, b : o 3= / Q— 2: ‘Oar 7 16) Z So “N28 KPO OQ GD r ‘6.1FinteStay Machines 263 7. & Gy — vAIDD*: DD"e v B+ ~ vA)DD "vit ~ vAIDD ev (ev ~ vA)DD* be let Ve Dy te =, } where D'= (0.1,2,...,9} ‘8 One sotuton: use Example 8 as a model and make appropriate changes. 9. L= {Ab eead as “feoncatenate A concatenate’), where A is the charac- ter set avaiable minus the characters} and { Solution similar and less complex than the solution to 10b following 410, a Compare your regular expression with the FSM in pact b. i. Let V be the character set available woth v1.0) Te Av illov ar By oor ¢ oF vitI0" 12, a UOT, Bd abab a wag & sols 6 Fett sf so 5 Fete) ae nl261 Taal or Teaching 1986 vas es [ot we sels Fatal ter als wr ag [Ot 1. Table from part a and ‘en a Fm teusa sud vo vel se 4 Fated tox 18, a Hint: This means n= 0 (mod 10) at 'b Hinte This means # is ever uss 16, a: Proof: Assume x = y (mod d) and : = w (mod 4 ex Then r—y= t+ d and 2—w= j-d for some integers fj 0 Solr —y)te— mba kod + joa vest Hence +2)—(y tw) = + fled vs: ‘Therefore 2+ = y+ (mod 1, 08 ', This proof is similar to the above proof. i