1

Proof by contradiction works because

$$\left[P \land \left[P \land \neg Q \implies \text{false}\right] \right] \implies Q$$

Naïve axioms of set theory

1. Sets and objects can be defined and can be identified using the definition
2. For any object and any set, we can determine if the object is in the set ($x \in A$)
3. Sets can be formed by specifying the elemetns of the set, e.g. $X = \left{ \text{people with blue eyes} \right} or $A = \left\{ x \in \R : x^2 \ge 9 \right\}$

#proof:

SFAC, 1-3 are true.

let $B = \left\{x | x \text{ is a set and }x \not\in x \right\}$

By ax. 2, we can determine if $B \in B$ or $B \not\in B$.

Claims:

$B \not\in B$ SFAC $B \in B$, then $B$ is a set and $B$ is an element of itself, but $B$ should not contain sets which are elements of themselves. So $B \not\in B$. Contradiction

Since $B \not\in B$, then $B$ is a set and $B \not\in B$. So, by def of $B$, $B \in B$. Contraction. So at least one of our assumptions is not true.

Formal Languages

#def:

In CSC 310 the term language is defined to be "a set of strings of characters"

Syntax - form taken by various valid expressions
Semantics - meaning associated with those valid expressions

In this class, our goal is to know which words are associated with certain formal languages.

#def:

• Alphabet - A finite set of symbols (characters)
  • $\{a, b, c, \dots, x, y, z\}$
  • $\{0, 1, \dots, 8, 9\}$
  • Alphabets must not be infinite
• Word - a valid string of characters
  • Valid is defined by the language def

How can we precisely define an infinite language?

• Using English (bad)
• Listing enough examples to establish a pattern (bad)
• Using mathematical expressions to represent how many times a particular character should be repeated (not generalisable)

Using English

"All odd length strings of 1s"

English is often vague and/or ambiguous

#Side Note:

$\Lambda$ used to represent the empty string

List enough to establish a pattern

For "all odd length string of 1s":

$$L_1 = \{1, 111, 11111, \dots\}$$

For "all even length string of 1s":

$$L_2 = \{\Lambda, 11, 1111, 111111, \dots\}$$

• How many examples should be listed?
• At what point does the pattern become "obvious"?

Using mathematical expressions

for "all even length strings of 1s"

$$L_1 = \left\{1^{2N} \text{ for } N = 0, 1, 2, 3, \dots\right\}$$

but then notations must be explained

$1^{2N}$ is not mathematical (in this case), the exponent is the number of times the character must be repeated

Operations

• length
• concat: Notations: $\text{CONCAT}(\alpha, \beta)$, $\alpha \cdot \beta$, $\alpha \, \beta$
  • non-commutative

#def:

Closure of a language under concatenation is the set of all strings that can be derived from applying the concatenation operation to the characters int he alphabet in all possible combinations

For an alphabet $\Sigma$, we generally denote this closure language as $\Sigma^\ast$, sometimes called "Sigma Star" or "Kleene Star"

Ex: given $\Sigma = \{a\}$, then $\Sigma^\ast = \{\Lambda, a, aa, aaa, \dots\}$

Ex: given $\Sigma = \{a, b\}$, then $\Sigma^\ast = \{\Lambda, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, \dots\}$

#ex:

If $S = \{a, bb\}$, find $S\ast$.

$S^\ast = \{\Lambda, a, aa, bb, aaa, abb, bba, aaaa, abba, bbaa, aabb, bbbb, \dots\}$

#ex:

If $S = \{ab, b\}$, find $S\ast$.

$S^\ast = \{\Lambda, b, ab, bb, bab, bbb, abb, bbab, bbbb, babb, abbb, abab \dots\}$

Proving that a word is in a language

"Constructive Proof/Algorithm"

Prove by constructive algorithm that "abba" is a word in $S^\ast$ where $S = \{a, bb, ba, ba\}$

1. By definition of the $\ast$ operator, $S\ast$ contains all words that can be constructed from the underlying factors of $S$.
2. "abba" is thus a word in $S\ast$ because "abba" can be constructed by the concatenation seq (ab) (ba).

#def:

Modified Kleene closure using $+$ as superscript:

For $S = \{a, b\}$

$S^\ast = \{\Lambda, a, b, aa, ab, ba, bb, \dots\}$
$S^+ = \{a, b, aa, ab, ba, bb, \dots\}$

#ex:

Prove by constructive algorithm that for $S = \{xx, xxx\}$ that $S^+$ contains all words of the form $x^N$ for $N > 1$

In general, any word in the form $x^N$ where $N > 3$ can be constructed from $(x^{N-2})(xx)$

This

a

#def: (Axiom of extension)

Two sets are equal iff they have the same elements.

#proof: (Prove that $(A \cup B) \cap (A \setminus B) = A \setminus B$)

Let $x \in (A \cup B) \cap (A \setminus B)$. So by def of intersection, $x \in A \cup B$ and $x \in A \setminus B$. So $x \in A \setminus B$ which shows $(A \cup B) \cap (A \setminus B) \subseteq A \setminus B$ Let $x \in A \setminus B$. Then $x \in A$ and $x \in B$. Since $x \in A$, then $x \in A \cup B$. So $x\in A \cup B$ and $x \in A \setminus B$. So $x \in (A \cup B)\ap (A \setminus B).

[there's more that I don't feel like writing ...]

#thm: (For any set of strings $S$, $S^\ast = S^{\ast\ast}$)

Recursive Definitions of Languages

Recursive definitions can be used to define lnaguages

Each recursive language definition consists of three parts

1. We explicitly define some elements of the set (base case)
2. We provide one or more rules for constructing additional elts of the set from known elts
3. We specify that no other words are allowed

Example

Consider language $L_1$ which can be defined in English as "all strings of x's length one or greater"

Here is a recursive def:

1. "x" is a word in $L_1$
2. If $Q$ is a word in $L_1$ the concat("x", $Q$) is also a word in $L_1$
3. $L_1$ contains only those words that can be generated from rules 1 and 2

RegExp

• * as superscript = {0,}
• + as superscript = {1,}
• + without superscript is or (| in my world)

Definition

Every individual character when bold is a regex, $\Lambda$ when written in boldface is a regex

If $R_1$ and $R_2$ are regexps then so are:

1. $(R_1)$ - define scope
2. $R_1R_2$ - concat
3. $R_1 + R_2$ - or
4. $R_1^*$ - {0,}