Define a finite state machine.
- An abstract representation of how something changes from one state to another in response to an input, condition or event.
- The machine can only have 1 state at a time and is defined as a list of states and conditions for transitions.
Define a finite state automaton.
A FSM with no outputs, one start state and a series of accept states.
State 4 uses of finite state machines.
- Robotics.
- Video Game Design.
- Design of compilers.
- Definition of programming languages.
Define a mealy machine.
A type of finite state machine, where an output is produced on each transition and determined by the current state and its input.
State 3 uses of a mealy machine.
- Map an input sequence to an output sequence.
- Language parsing.
- Language translation.
Define a set.
A well-defined collection of unordered objects, where each member only appears once.
What does x ∈ S mean?
x is a member of set S.
What does x ∉ S mean?
x is not a member of set S.
Write in plain English the meaning of this expression S = { x | x ∈ N ᴧ x is even }.
- x | = x is such that x ∈ N = x is a member of the set of Natural numbers
- ᴧ = and
- x is even
- x is such that x is a member of a set of Natural numbers and is even.
How might the empty set be represented?
- {} or ø
- A empty set is a set with no members.
How many empty sets are there?
Only one empty set exists, because all members of a set can only appear once.
Explain x = {x | A ∪ B}.
Union: x is such that it is a member of set A, or a member of set B, or a member of set A and B
Explain x = {x | A ∩ B}.
Intersection: x is such that it is a member of both set A and set B only
Explain x = {x | A \ B}.
Difference: x is such that it is a member of set A, but not a member of set B
Describe set A such that this expression is true A ⊆ B.
A is a subset of B as long as every member of set A is also a member of set B.
Describe set A such that this expression is true A ⊂ B.
A is a proper subset of B when members of set A is also a member of set B, but not all of them.
Define in words the cartesian product of two sets
The set of all ordered pairs (a, b) such at a ∈ A and b ∈ B.
Write the state comprehension for A x B
A x B = {(a, b) | a ∈ A ᴧ b ∈ B}
A = {1,2} and B = {4,8} What is A X B?
{(1,4), (1,8), (2,4), (2,8)}
A = {2,4,6,8}, what is |A|
The cardinality of set A is the number of elements in the finite set, which is 4
Define a countably infinite set
A set where there are an infinite number of distinct numbers which can be counted using N.