finite state machines Flashcards
what does finite mean?
countable
What does a finite state machine need to function?
Memory to store the current state and some kind of logic device to determine the next state
What is the definition of a finite state machine?
A machine with a fixed set of possible states, a set of allowable inputs which change the state and a set of possible outputs
What do the outputs of a finite state machine depend on?
The current state (which is determined by the sequence of past inputs)
Are general purpose computers FSMs?
yes
What is clock rate?
The rate at which general purpose computers advance
faster clock rate = faster problem solving
What is a state transition diagram?
A way of describing a finite state machine graphically
In a state transition diagram what is a state?
A circle
In a state transition diagram what is a transition?
An arrow from state to state
labelled with the input which causes it (and any outputs caused in the form input/.output)
Why are finite state machines useful?
They are good for recognising sequences
for example, legal and valid inputs for a programming language
What is the name for a finite state machine with no outputs?
FSA
finite state automaton
How is an initial state represented in a state transition diagram?
A circle with an arrow (can be labelled start) pointing into it
How is the accepting/goal state represented in a state transition diagram?
A circle with a circle around it
What is a FSM with outputs at the transitions called?
A mealy machine
What do finite state automatons have?
An initial state and one or more accepting states
