Chapter 0: Introduction, Math Review Flashcards
What is a theorem?
A statement that has been proven to be true
What is a proof?
A convincing, logical argument that a statement is true
Explain (& differentiate between) this relationship:
Symbols → Alphabet → String → Language
- Symbols are members of an alphabet
- An alphabet is a finite, nonempty set of symbols
- A string is a finite sequence of symbols over an alphabet
- A language is a set of strings over an alphabet
What is proof by induction?
- Method used to show that all elements of an infinite set have a specified property
- Always consists of two parts: basis & induction step
- The basis proves that P(1) is true.
- The induction step proves that for each i ≥ 1, if P(i) is true, then so is P(i + 1).
If you take the cross (Cartesian) product of two sets A and B in both orders (A x B and B x A), under what conditions would you get equivalent results?
- If A = B
- If one or both are the empty set
- If every element is the same
What is a tuple?
A finite sequence of elements.
A sequence with k elements is a k-tuple.
- (1, 2, 3) is a 3-tuple
- (1, 4) is a 2-tuple or ordered pair
What is a proper subset?
A subset that is not equal to the superset.
E.g., if set A is a proper subset of set B, then set A is not equal to set B.
What is an empty language?
- A language without strings; an empty set: Ø or { }
- Size is zero: | Ø |
- Do not confuse with the empty string, which is not in the empty language. ϵ ≠ ∅ and ϵ ∉ ∅.
What is an alphabet (Σ)?
Any non-empty, finite set of symbols.
Can you have an empty language?
YES. An empty language is a set without strings (size zero, an empty set: Ø or { } )
What is proof by contradiction?
- An argument where we assume that the theorem is false and then show that this assumption leads to an obviously false consequence, called a contradiction
Example: proof that 2 is irrational by starting with the claim that 2 is rational instead
What does it mean for A to be a subset of B?
If every member of A is also a member of B.
What is a language?
- A set of strings over an alphabet Σ
- if Σ = {0, 1}, then possible languages might be:
{00, 11, 0011} or {01, 10, 1001} …
• The syntax of a language constrains the set of strings that are part of that language to satisfy certain properties.
What is the length of a string?
The number of symbols in a string
• if w = 101, then |w | = 3
What is a statement?
- An unambiguous, precise description of some property that an object has
- May be true or not
What is an infinite set?
A set containing infinitely many elements (e.g., natural numbers, integers).
What is an unordered pair?
A set with two members.
What is the Cartesian product of sets A and B?
A x B = the set of all ordered pairs wherein the first element is a member of A and the second element is a member of B.
What is a sequence?
A list of objects in some order.
• Order & repetition matter
(1, 1, 2, 3) ≠ (1, 2, 3)
What are 5 ways we could use to define a language?
-
Listing all possible strings:
{01, 0011, 000111, … } -
Describing how to construct a typical string:
{ 0k1k | k > 0 } - Describing how to test a string for membership:
{ x over {0,1} | x has the same number of 0’s and 1’s, has at least one 0, and all 0s precede all 1s } - Defining a machine/program that accepts all strings in a language
- Defining a machine/program that generates all strings in a language
Can you have an empty alphabet?
NO. An alphabet is a finite, nonempty set of symbols.
What is a string?
A finite sequence of symbols over an alphabet Σ.
• E.g., if Σ1 = {0,1}, then 01001 is a string over Σ1
What is proof by construction?
- A proof which demonstrates how to construct an object in question
- Useful for proving theorems which state that a particular type of object exists
Example: For each even number n greater than 2, there exists a 3-regular graph with n nodes.
What is a set?
- A group of objects (elements or members) represented as a unit
- May contain any kind of object (e.g., numbers, symbols, other sets)
- Order is irrelevant
- Cannot have repetition
