Chapter 0: Introduction, Math Review

Question 1

What is a theorem?

Answer 1

A statement that has been proven to be true

Question 2

What is a proof?

Answer 2

A convincing, logical argument that a statement is true

Question 3

Explain (& differentiate between) this relationship:

Symbols → Alphabet → String → Language

Answer 3

• 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

Question 4

What is proof by induction?

Answer 4

• 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).

Question 5

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?

Answer 5

• If A = B
• If one or both are the empty set
• If every element is the same

Question 6

What is a tuple?

Answer 6

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

Question 7

What is a proper subset?

Answer 7

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.

Question 8

What is an empty language?

Answer 8

• 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 ϵ ∉ ∅.

Question 9

What is an alphabet (Σ)?

Answer 9

Any non-empty, finite set of symbols.

Question 10

Can you have an empty language?

Answer 10

YES. An empty language is a set without strings (size zero, an empty set: Ø or { } )

Question 11

What is proof by contradiction?

Answer 11

• 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

Question 12

What does it mean for A to be a subset of B?

Answer 12

If every member of A is also a member of B.

Question 13

What is a language?

Answer 13

• 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.

Question 14

What is the length of a string?

Answer 14

The number of symbols in a string

• if w = 101, then |w | = 3

Question 15

What is a statement?

Answer 15

• An unambiguous, precise description of some property that an object has
• May be true or not

Question 16

What is an infinite set?

Answer 16

A set containing infinitely many elements (e.g., natural numbers, integers).

Question 17

What is an unordered pair?

Answer 17

A set with two members.

Question 18

What is the Cartesian product of sets A and B?

Answer 18

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.

Question 19

What is a sequence?

Answer 19

A list of objects in some order.

• Order & repetition matter

(1, 1, 2, 3) ≠ (1, 2, 3)

Question 20

What are 5 ways we could use to define a language?

Answer 20

1. Listing all possible strings:
   {01, 0011, 000111, … }
2. Describing how to construct a typical string:
   { 0^k1^k | k > 0 }
3. 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 }
4. Defining a machine/program that accepts all strings in a language
5. Defining a machine/program that generates all strings in a language

Question 21

Can you have an empty alphabet?

Answer 21

NO. An alphabet is a finite, nonempty set of symbols.

Question 22

What is a string?

Answer 22

A finite sequence of symbols over an alphabet Σ.

• E.g., if Σ₁ = {0,1}, then 01001 is a string over Σ₁

Question 23

What is proof by construction?

Answer 23

• 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.

Question 24

What is a set?

Answer 24

• 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

Question 25

What is the power set of any set?

Answer 25

• The set of all subsets of a set (including the empty set and set itself).
• Creates all possible subsets of a set
• Cardinality will always be 2^|A| for powerset of set A
  
  • E.g., if A has 3 elements, |A|=3, and |P(A)| = 2³ = 8

Question 26

What is the empty string ϵ ?

Answer 26

• A string with no symbols
• Length zero: | ϵ | = 0
• Part of every alphabet
• Not necessarily part of every language