# Maths for Regular Expressions/sets/subsets Flashcards

1
Q

What is a set and an important rule of sets?

What are the three types of sets?

A

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

2
Q

What is the notation used for a set?

A

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

3
Q

What are some commonly used sets?

A

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

4
Q

How is an empty set represented

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

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

A

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)

6
Q

What does the symbol | mean?

A
• the symbol | means “such that”
7
Q

What does the x represent?

A
• x represents the values of the set listed after the | symbol
8
Q

What does N mean?

A
• N means natural numbers
9
Q

what does the∊symbol mean?

A

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

10
Q

What does x >= 1 mean?

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

What does the ^ symbol mean

A

The ^ symbol stands for “and”

12
Q

Why do we use sets?

A
• 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
13
Q

What is an infinite set?

A

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

(this includes natural, integer and real number sets)

14
Q

What is a finite set?

A
• 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
15
Q

What is a countably infinite set?

Give examples of countably infinite sets

A
• 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
16
Q

What is an uncountably infinite set?

A

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

17
Q

What is compact representation/format?

A

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

18
Q

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

A

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)}

19
Q

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

A

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

20
Q

What is a subset?

A

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

21
Q

What is a proper subset?

A

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

22
Q

What is the notation for a subset?

A

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

23
Q

What is the notation for a proper subset?

A

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}

24
Q

What does A ⊆ B mean?

A

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

25
Q

What does A ⊂ B mean?

A

Subset A has fewer elements than set B

26
Q

What is a set operation?

A

It defines the relationship between two or more different sets

27
Q

What is membership?

A

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

28
Q

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

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

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

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

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

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

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

A

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

32
Q

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

A

X ∩ Y = {1,4}

33
Q

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

A

X - Y = {2,6}

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

34
Q

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

A

Y - X = {8,9,13}

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

35
Q

What is a regular expression?

A

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

36
Q

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

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

What does a | symbolise in regular expressions?

A

It separates alternatives. It represents a boolean OR.

38
Q

What does a ? symbolise in regular expressions?

A

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

39
Q

What does a * symbolise in regular expressions?

A

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

40
Q

What does a ⁺ symbolise in regular expressions?

A

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

41
Q

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

A

Edward, Eddie and Ed are all accepted

42
Q

What are the matched strings for the regular expression:

D|d) is (c|k

A

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

43
Q

What are the matched strings for the regular expression:

Dialog(ue)?

A

Dialog and Dialogue are all accepted

44
Q

What are the matched strings for the regular expression:

ab*

A

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

45
Q

What are the matched strings for the regular expression:

a⁺b

A

ab, aab, aaab, aaaab… are all accepted

46
Q

What is a regular language?

A

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