Flashcards in finite state machines Deck (19):
what does finite mean?
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?
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?
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?
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
What do mealy machines have?
An initial state
(Usually no accepting state)
What can state transition tables include?
input, current state, output, next state
What do state transition tables do?
Show the effect on the current state of an FSM for particular inputs as well as any corresponding output