Intro Theory Computation
Intro Theory Computation ECS 120
Popular in Course
Popular in Engineering Computer Science
This 6 page Class Notes was uploaded by Ashleigh Dare on Tuesday September 8, 2015. The Class Notes belongs to ECS 120 at University of California - Davis taught by Staff in Fall. Since its upload, it has received 49 views. For similar materials see /class/187780/ecs-120-university-of-california-davis in Engineering Computer Science at University of California - Davis.
Reviews for Intro Theory Computation
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/08/15
ECS 120 Lesson 3 7 Finite State Machines Pt 2 Oliver Kreylos Wednesday April 4th 2001 1 Formal De nition of Finite State Machines As can be seen from the rst two examples of Finite State Machines7 we have to specify several parts when trying to give a formal de nition of one o How many and which states does the automaton have 0 What characters can the automaton read 0 How does the automaton move from state to state 0 Which state does the automaton start in 0 Which states are nal states These ve questions lead directly to the formal de nition A Finite State Machine M is a 5 tuple M QE57 107F7 where 0 Q is a nite set of states 0 E is the input alphabet o 6 Q gtlt E a Q is the transition function 0 go 6 Q is the initial state 0 F C Q is the set of nal states or accepting states As an example here is the formal de nition for the pushbutton automaton shown last lecture PB On OffPUSHOnPUSH 1 Off Off PUSH 1 On OffOn The transfer functions of more complicated automata are usually given in tabular form Here is the formal de nition for the doorlock automaton shown last time For brevity let us denote the states idle 3 seen 31 seen 314 seen 3141 seen and wrong key by q0q1q2Q3q4 and Q5 respec tively DL QO7QI7QZ7QS7Q47QS7O71779767q07Q4 where l o 1 2 3 4 5 6 7 8 9 Q0 Q5 Q5 Q5 Q1 Q5 Q5 Q5 Q5 Q5 Q5 Q1 Q5 Q2 Q5 Q5 Q5 Q5 Q5 Q5 Q5 Q5 5 Q2 Q5 Q5 Q5 Q5 Q3 Q5 Q5 Q5 Q5 Q5 Q3 Q5 Q4 Q5 Q5 Q5 Q5 Q5 Q5 Q5 Q5 Q4 Q5 Q5 Q5 Q5 Q5 Q5 Q5 Q5 Q5 Q5 Q5 Q5 Q5 Q5 Q5 Q5 Q5 Q5 Q5 Q5 Q5 As another example let us consider an automaton that reads an integer in binary notation as a word over the alphabet 01 and has to decide whether that integer is divisible by three In other words we consider an automaton D3 that accepts the language LD3 w 6 01 l The integer represented by w is divisible by 3 Figure 1 shows the automaton as a state diagram Here is the formal description of the automaton D3 Q07Q17Q27071757Q07Q0 where How did we come up with this automaton First we have to look at the problem from an automaton7s point of view As programmers we tend to attack the problem like this First store all input characters in memory Second convert them to an integer Third calculate the remainder when dividing that integer by three Fourth accept the word iff the remainder is zero Alas this doesnt work for an automaton for two reasons First an automaton cannot store its input characters because it has no memory and second it cannot divide by three because it has no arithmetic logical unit Thus we have to nd another way to solve the problem A general insight about automata states that automata work by classifying input words as they are read one character at a time and always having a partial answer ready as the input word is read Let us rst restate the problem and then apply this insight The question whether an integer n is divisible by three is equivalent to the question whether its remainder when dividing by three is zero or in formula 71 mod 3 0 Now the application of above insight says that we have to construct the nal integer value of the read word as we go along and keep track of the current remainder as we go How is an integer value de ned by a binary string if read left to right Let us rst decide that the empty word has an integer value of zero Then after we have read a number of binary digits say that the integer value of the read word is 1 Now we read another digit 7 what happens to the value Reading another digit means that we add another digit to the right of the current binary word effectively shifting the old digits one to the left Shifting one to the left means multiplying the words value by two After shifting the new digit is added to the word If the new digit is zero the words value doesn7t change if it is one the value increases by one So here are the two different cases 0 Current value 1 read 0 New value is 21 0 Current value 1 read 1 New value is 21 1 Knowing how to keep track of the integer value of the current word we now have to classify it according to our problem which means we have to keep track of the current word7s remainder when divided by three There can be three different values for the remainder 7 0 1 and 2 7 and we will need a state representing each of those Now that we have decided the states we need to create the transition function How does the remainder change as we are reading additional digits To nd out we need two rules from modular arithmetics ab mod n a mod n b mod mod n a b mod n a mod n b mod mod n 3 Applying these rules to the calculation of the current value7 we get 0 Current remainder 1 mod 717 read 0 New remainder is 21 mod 3 2 mod 3 1 mod 3 mod 3 2 1 mod 3 mod 3 0 Current remainder 1 mod 717 read 1 New remainder is 21 1 mod 3 211 mod 3 1 mod 3 mod 3 21 mod 3 1 mod 3 21 mod 3 1 mod 3 Now we know how to express the new remainder in terms ofthe old remainder and the read character this can directly be translated into the transition function 6 by plugging in the three possible values of 1 mod 3 The last tasks left are to de ne the start state and the nal states In this case7 we decided that the empty word has a value of zero and thus has a remainder of zero therefore7 the start state must be go And since we only want to accept words having a remainder of zero7 qo must also be the only nal state Figure 1 An automaton that decides whether an integer represented as a binary string is divisible by 3 11 Discussion Problems 0 Can an FSM have zero states 0 Does there have to be an outgoing arrow for each input character from each state 0 Can an FSM have zero nal states If so7 what is the language accepted by an FSM with zero nal states 2 Formal De nition of Computation Now that we can formally de ne an automaton7 we have to formalize our description of how an automaton accepts or rejects a word Let M Q72767q07F be a Finite State Machine7 and let w wlwgwn E E be a string of length 71 over M7s input alphabet 2 Then M accepts w if and only if there exists a sequence of states r0771 7m 6 Q with the conditions 1 70907 2 6n1wi 77 for all 239 127717 and 3 TnEF These three conditions state that the automaton starts out in the start state 10 that it follows the transition function 6 from one state to the next as it reads each character wig and that the state the automaton ends in is a nal state in F Now we can formally de ne the language LM accepted by automaton M as LM w E 2 l M accepts w The above de nition is taken verbatim from the textbook7 but for our purposes7 it is not quite formal enough Recall that earlier we formally speci ed words over an alphabet using a recursive de nition to t into our framework7 the de nition of computation has to match the formal de nition of words The problem in the above de nition lies in the statement let w 101102 wn E E be a word of length 7177 Our recursive de nition does not de ne how to write a word as a sequence of characters7 so we should not use it in another formal de nitionl To recall Basically7 we de ned a word in the following way 1 E is a word 2 If a E E is a character7 and z E 2 is a word7 then ax is a word In order to formally de ne computation7 we have to base its de nition on the de nition of a word We do that by generalizing the transfer function 6 of an automaton In its known form7 6 takes a state and a single character and returns the new state the automaton will be in after reading that character 1How to write a word as a sequence of characters can be deducted from the de nition7 but that s a different story We now de ne a generalized transition function 6 that does not take a single character but a complete word and returns the state the machine will be in after having read the entire word We de ne 6 Q gtlt 2 a Q as follows 1 D 6q 6 q When reading the empty word meaning reading nothing at all an automaton does not change its state For any w E 2 6 ie for any non empty word there exist a character a E 2 and a word z E 2 such that w ax inductive case of the de nition of a word We de ne 6q w 66qa When w is a non empty word we can split it into an initial character a and a suf x word x When an automaton is in a state q and reads a word w ax from the left it is going to see character a rst and react to it by moving to another state That new state 1 is given by the transition function 6 and once the machine has read the rst character it will read the rest of the word s starting from state 1 Thus the recursive de nition of 6 First we apply 6 to q and a then we apply 6 to q the shorter rest of the word x With the de nition of 6 we can now de ne exactly what it means to say M accepts 11 Let M Q26q0F be an automaton and let w E 2 be a word Then M accepts w iff 210710 E F In other words a machine accepts a word ifthat word will take it from the start state to a nal state Similarly we can now de ne the language of an automaton Let M Q 26q0F be an automaton Then the language of the automaton M is de ned as LM w E 2 l 6q0w E F
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'