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