Maths for Regular Expressions/sets/subsets

Question 1

What is a set and an important rule of sets?

What are the three types of sets?

Answer 1

A set is an unordered collection of values or symbols.
Any value or symbol occurs at most once.
Sets can be common, finite and infinite

Question 2

What is the notation used for a set?

Answer 2

A = {1,2,3,4,5}
B = {-1,0,3,16,18}
C = {red, orange, yellow}
A set is usually denoted by a capital letter
A member is usually denoted by a lowercase letter

Question 3

What are some commonly used sets?

Answer 3

Natural numbers, the set of integers, real numbers and rational numbers and empty sets

Question 4

How is an empty set represented

Answer 4

• A = { Ø } or {} means an empty set

Question 5

What is the cardinality of a set?
What is the cardinality of sets A and B?
A = {1,2,3}
B = {}

Answer 5

The cardinality of a set is the number of elements in the set. The cardinality of set A is 3 and the cardinality of set B is 0 (empty sets have a cardinality of 0)

Question 6

What does the symbol | mean?

Answer 6

• the symbol | means “such that”

Question 7

What does the x represent?

Answer 7

• x represents the values of the set listed after the | symbol

Question 8

What does N mean?

Answer 8

• N means natural numbers

Question 9

what does the∊symbol mean?

Answer 9

-The∊symbol indicates membership so x ∊ N is read as “x belongs to N”

Question 10

What does x >= 1 mean?

Answer 10

• x >=1 means where x is greater or equal to one

Question 11

What does the ^ symbol mean

Answer 11

The ^ symbol stands for “and”

Question 12

Why do we use sets?

Answer 12

• Means we can group objects together and view them as a single entity
• A set becomes an abstraction
• Set theory and logic have a close relationship
• Many programming languages support sets as an abstract data type

Question 13

What is an infinite set?

Answer 13

An infinite set may be countable or uncountable.
- It has an infinite number of elements

(this includes natural, integer and real number sets)

Question 14

What is a finite set?

Answer 14

• A finite set is one whose elements can be counted off by natural numbers up to a certain number.
• It has a finite number of elements

Question 15

What is a countably infinite set?

Give examples of countably infinite sets

Answer 15

• Contains an infinite number of elements which can be mapped one to one to the set of of natural numbers.
• Natural and integer numbers are infinite countable sets

Question 16

What is an uncountably infinite set?

Answer 16

Contains an infinite number of elements which cannot be mapped one to one to the set of of natural numbers. Real numbers are an uncountable finite set

Question 17

What is compact representation/format?

Answer 17

It uses set comprehension to compact the set into a formula. for example : B = { n2 | n ∊ N ^ n < 5 }

Question 18

What is the cartesian product of two sets X and Y?

Answer 18

Can be written as X x Y or (X cross Y) is the set of all crossed pairs (x, y) where x is a member of X and y is a member of Y.
X = {1, 3, 5}
Y = {12, 25, 40}
Z = X x Y
Z = {(1, 12), (1, 25), (1, 40), (3, 12), (3, 25), (3, 40), (5, 12), (5, 25), (5, 40)}

Question 19

What does the set of {0^n1^n | n>=1} look like?

Answer 19

It will be a list of strings where each string has an equal number of 0’s and 1’s: {01, 0011, 000111, 00001111,…}

Question 20

What is a subset?

Answer 20

A set where all the elements of one set are elements of another set

Question 21

What is a proper subset?

Answer 21

A set that does not include all the elements of the set to which it belongs.

Question 22

What is the notation for a subset?

Answer 22

if X is a subset of Y
X = {1,2,4,6} , Y = {4,6,1,2}
This can be written as X ⊆ Y

Question 23

What is the notation for a proper subset?

Answer 23

This can be written as X ⊂ Y
if X is a subset of Y
X = {1,2,4,6} , Y = {4,6,1,2,9,13}

Question 24

What does A ⊆ B mean?

Answer 24

That subset A has fewer elements than or is equal to set B

Question 25

What does A ⊂ B mean?

Answer 25

Subset A has fewer elements than set B

Question 26

What is a set operation?

Answer 26

It defines the relationship between two or more different sets

Question 27

What is membership?

Answer 27

A set operation used to check whether an element is a member of a particular set

Question 28

What is the Union of two sets? And what is the symbol used to denote a Union?

Answer 28

• The union of two sets is the set that contains all the elements of these sets
• X U Y

Question 29

What is the Intersection of two sets? And what is the symbol used to denote a intersection?

Answer 29

• The intersection of two sets is the set that contains only the elements which are in both sets
• X ∩ Y

Question 30

What is the Difference of two sets? And what is the symbol used to denote a Union?

Answer 30

• The difference of two sets is the set that contains all the elements which are in one set but not both.
• X - Y

Question 31

State the set of X U Y, where X = {1,2,4,6} and Y = {1,4,8,9,13}

Answer 31

X U Y = {1,2,4,6,8,9,13}

Question 32

State the set of X ∩ Y, where X = {1,2,4,6} and Y = {1,4,8,9,13}

Answer 32

X ∩ Y = {1,4}

Question 33

State the set of X - Y, where X = {1,2,4,6} and Y = {1,4,8,9,13}

Answer 33

X - Y = {2,6}

- It’s equal to the elements that are in set X but not set Y

Question 34

State the set of Y - X, where X = {1,2,4,6} and Y = {1,4,8,9,13}

Answer 34

Y - X = {8,9,13}

- It’s equal to the elements that are in set Y but not set X

Question 35

What is a regular expression?

Answer 35

An expression used to specify a set of strings that satisfy given conditions

Question 36

Give some examples of what regular expressions can be used for in real life.

Answer 36

• To match patterns in text files (in a word processing program)
• By programmers to validate user input

Question 37

What does a | symbolise in regular expressions?

Answer 37

It separates alternatives. It represents a boolean OR.

Question 38

What does a ? symbolise in regular expressions?

Answer 38

It indicates that there are zero or one of the preceding element

Question 39

What does a * symbolise in regular expressions?

Answer 39

It indicates that there are zero or more of the preceding element

Question 40

What does a ⁺ symbolise in regular expressions?

Answer 40

It indicates that there are one or more of the preceding element

Question 41

What are the matched strings for the regular expression: (Edward) | (Eddie) | (Ed)

Answer 41

Edward, Eddie and Ed are all accepted

Question 42

What are the matched strings for the regular expression:

D|d) is (c|k

Answer 42

“Disc”, “disc”, “Disk” and “disk” are all accepted

Question 43

What are the matched strings for the regular expression:

Dialog(ue)?

Answer 43

Dialog and Dialogue are all accepted

Question 44

What are the matched strings for the regular expression:

ab*

Answer 44

a, ab, abb, abbb, abbb… are all accepted

Question 45

What are the matched strings for the regular expression:

a⁺b

Answer 45

ab, aab, aaab, aaaab… are all accepted

Question 46

What is a regular language?

Answer 46

Any language that can be represented by a regular expression, or a language accepted by a finite state machine