Set Theory

4.4.2.2 (21 questions). Public Notes: AQA's A Level Computer Science

Define a finite state machine.

  1. An abstract representation of how something changes from one state to another in response to an input, condition or event.
  2. 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.

  1. Robotics.
  2. Video Game Design.
  3. Design of compilers.
  4. 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.

  1. Map an input sequence to an output sequence.
  2. Language parsing.
  3. 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 }.

  1. x | = x is such that x ∈ N = x is a member of the set of Natural numbers
  2. ᴧ = and
  3. x is even
  4. 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.