Class Notes (836,213)
United States (324,390)
PHIL-0170 (1)

First Notes

8 Pages
Unlock Document

George Smith

Q: finite set of internal states -fixed bound on the number of states S: finite input alphabets -no fixed bound on the length of the input strings R: finite output alphabet f: function from QxS->Q (state transition) g: function from QxS->R q1: initial state Sequential cycle time: virtually all computers work through timed cycles. Parity device checker -even number of 1's so far -odd number of 1's so far (even)-------------(odd) what I/O tasks can be performed? binary addition 10000 -> 16 +10010 -> 18 100010 -> 34 Binary Adding Machine Q: q0 or q1 S: <0,0> <1,0> <0,1> <1,1> R: 0, 1 Look at Notes for Carry parity diagram* -insight. Carry is part of how we add. "good" strings on alphabet {0,1} which begin with a 1 and contain exactly one 0 all others are bad. Good strings: 11101, 10111 Bad strings: 01, 10011, 10101. What questions should we ask? is first symbol a 1? have you hit a 0? have you hit another 0? Look at notes ---> 4 states to solve that problem. Non-deterministic Machines: 2 ways. -have state input pairs with no response. (machine does nothing) -have, for a given input pair, two or more options. - (state transition is no longer a function, but a relation - is it possible for the non-deterministic machine to work? any non-deterministic machine can be converted to a deterministic one acceptor transducer generator representing numbers -numerals -binary 0,1 8=10^3 -octal 0,1,2,3,4,5,6,7,10,11 -hexadecimal Finite State Machine: Finitistic: no magic Transducer: Acceptors: Generators: Questions: what machines are equivalent? (respond to all inputs the same) consider the machine: m states m+1 inputs. after m+1 steps, we cannot tell whether the machine was in 1 state or m+1 state* beginning with an a and having exactly 1 b same number of a's as b's finite state machines cannot do multiplication? suppose a FSmachine exists that ca
More Less

Related notes for PHIL-0170

Log In


Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.