Maths for Regular Expressions/sets/subsets Flashcards
What is a set and an important rule of sets?
What are the three types of sets?
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
What is the notation used for a set?
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
What are some commonly used sets?
Natural numbers, the set of integers, real numbers and rational numbers and empty sets
How is an empty set represented
- A = { Ø } or {} means an empty set
What is the cardinality of a set?
What is the cardinality of sets A and B?
A = {1,2,3}
B = {}
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)
What does the symbol | mean?
- the symbol | means “such that”
What does the x represent?
- x represents the values of the set listed after the | symbol
What does N mean?
- N means natural numbers
what does the∊symbol mean?
-The∊symbol indicates membership so x ∊ N is read as “x belongs to N”
What does x >= 1 mean?
- x >=1 means where x is greater or equal to one
What does the ^ symbol mean
The ^ symbol stands for “and”
Why do we use sets?
- 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
What is an infinite set?
An infinite set may be countable or uncountable.
- It has an infinite number of elements
(this includes natural, integer and real number sets)
What is a finite set?
- 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
What is a countably infinite set?
Give examples of countably infinite sets
- 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
What is an uncountably infinite set?
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
What is compact representation/format?
It uses set comprehension to compact the set into a formula. for example : B = { n2 | n ∊ N ^ n < 5 }
What is the cartesian product of two sets X and Y?
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)}
What does the set of {0^n1^n | n>=1} look like?
It will be a list of strings where each string has an equal number of 0’s and 1’s: {01, 0011, 000111, 00001111,…}
What is a subset?
A set where all the elements of one set are elements of another set
What is a proper subset?
A set that does not include all the elements of the set to which it belongs.
What is the notation for a subset?
if X is a subset of Y
X = {1,2,4,6} , Y = {4,6,1,2}
This can be written as X ⊆ Y
What is the notation for a proper subset?
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}
What does A ⊆ B mean?
That subset A has fewer elements than or is equal to set B
What does A ⊂ B mean?
Subset A has fewer elements than set B
What is a set operation?
It defines the relationship between two or more different sets
What is membership?
A set operation used to check whether an element is a member of a particular set
What is the Union of two sets? And what is the symbol used to denote a Union?
- The union of two sets is the set that contains all the elements of these sets
- X U Y
What is the Intersection of two sets? And what is the symbol used to denote a intersection?
- The intersection of two sets is the set that contains only the elements which are in both sets
- X ∩ Y
What is the Difference of two sets? And what is the symbol used to denote a Union?
- The difference of two sets is the set that contains all the elements which are in one set but not both.
- X - Y
State the set of X U Y, where X = {1,2,4,6} and Y = {1,4,8,9,13}
X U Y = {1,2,4,6,8,9,13}
State the set of X ∩ Y, where X = {1,2,4,6} and Y = {1,4,8,9,13}
X ∩ Y = {1,4}
State the set of X - Y, where X = {1,2,4,6} and Y = {1,4,8,9,13}
X - Y = {2,6}
- It’s equal to the elements that are in set X but not set Y
State the set of Y - X, where X = {1,2,4,6} and Y = {1,4,8,9,13}
Y - X = {8,9,13}
- It’s equal to the elements that are in set Y but not set X
What is a regular expression?
An expression used to specify a set of strings that satisfy given conditions
Give some examples of what regular expressions can be used for in real life.
- To match patterns in text files (in a word processing program)
- By programmers to validate user input
What does a | symbolise in regular expressions?
It separates alternatives. It represents a boolean OR.
What does a ? symbolise in regular expressions?
It indicates that there are zero or one of the preceding element
What does a * symbolise in regular expressions?
It indicates that there are zero or more of the preceding element
What does a ⁺ symbolise in regular expressions?
It indicates that there are one or more of the preceding element
What are the matched strings for the regular expression: (Edward) | (Eddie) | (Ed)
Edward, Eddie and Ed are all accepted
What are the matched strings for the regular expression:
D|d) is (c|k
“Disc”, “disc”, “Disk” and “disk” are all accepted
What are the matched strings for the regular expression:
Dialog(ue)?
Dialog and Dialogue are all accepted
What are the matched strings for the regular expression:
ab*
a, ab, abb, abbb, abbb… are all accepted
What are the matched strings for the regular expression:
a⁺b
ab, aab, aaab, aaaab… are all accepted
What is a regular language?
Any language that can be represented by a regular expression, or a language accepted by a finite state machine
