SLR7 Finite State Machines Flashcards
(40 cards)
What is a finite state machine?
A model of computation, used to design computer programs and sequential logic circuits
What is it a model of?
An abstract model of how a machine reacts to external events
How many states can a finite state machine be in at one time?
Can only be in one of a finite number of states at any one time, which changes based on trigger conditions
What do you use to visualise FSMS?
State transition diagrams
How is a state represented?
A circle with text in
How is a start state represented?
A circle with an arrow coming into it
How do you represent an accept state?
Circle inside circle
What are tranisiton conditions?
Each transition must have a transition condition
Structured as ‘transition/input’ which causes the state following the direction of the transition arrow
What is a mealy machine?
It is an FSM with an output
What is a mealy machines output determined by?
its current state and its current input
What are regular expressions?
An equivalent way of defining a regular language
When is a language considered regular?
When it can be represented by a regular expression
When a FSM will accept the language
What are some things you might want to use FSM to model?
- digital systems
- compilers
- network protocols
What is finite state automation?
- an FSM that has no output
- has a start state and a set of accept states which define whether it accepts or rejects finite strings or symbols
What is deterministic FSM automation?
if the next state is uniquely determined by the input when in a specific state
What happens when data input into an FSM is valid?
the FSM will terminate in an accepting state
What is a set?
an abstract data type which contains unordered unique values
sets can contains other sets
What is set comprehension?
A different way of creating a set - rather than specifying all of the items individually, we can select what we want from a more general set
What does | mean?
it means ‘such that’
What does e mean?
means ‘is drawn from’
What does ^ mean?
means ‘and’
What does a simple set comprehension look like?
A = { x | xeN ^ x>1}
How does a set comprehension look?
S = {Instruction | x e Defined Set ^ x satisfies condition}
How do you represent an empty set?
{} or zero with a cross through it
