Read Chapter 0 and 1.1 of the text by Monday 26 Janaury.

Review the following concepts:

  • Set (\(S\)): collection of unordered distinct objects

  • Power Set (\(2^S\)): set of all subsets of \(S\)

  • Alphabet (\(\Sigma\)): finite set of symbols

  • String (\(w\)): finite sequence of symbols from an alphabet

  • Language (\(L\)): set of strings over an alphabet, a subset of \(\Sigma^*\) (all strings over \(\Sigma\))

Note that while \(\Sigma^*\) contains finite length strings, it is an infinite set since there is no upper bound on the length of the strings. \(L=\Sigma^*\) is called the universal language over \(\Sigma\), and is an infinite language. \(L=\emptyset\) is called the empty language.

Relations

A relation \(R\) is a subset of the Cartesian product \(A \times B\). If \((a, b) \in R\), we say that \(a\) is related to \(b\) by \(R\), written \(a R b\). The \(a R b\) notation is used by the book, but I tend to just list the pair \((a, b) \in R\) when writing about relations.

A relation is:

  • Reflexive: for all \(a \in A\), \((a, a) \in R\)

  • Symmetric: for all \(a\in A\) and \(b \in B\), if \((a, b) \in R\), then \((b, a) \in R\)

  • Transitive: for all \(a \in A\), \(b \in B\), and \(c \in C\), if \((a, b) \in R\) and \((b, c) \in R\), then \((a, c) \in R\)

An equivalence relation is a relation that is reflexive, symmetric, and transitive. Consider the realation \(\equiv_{3}\) on the integers defined by: for all integers \(a\) and \(b\), \(a \equiv_{3} b\) if and only if \(a - b\) is divisible by 3. Show that \(\equiv_{3}\) is an equivalence relation.

Consider the relation \(R = \{(a, b) | a, b \in \mathbb{Z} \text{ and } a \leq b\}\). Is \(R\) reflexive. Is it symmetric? Is it transitive? Justify your answers.

Functions

A function \(f\) from set \(A\) to set \(B\) is a binary relation \(R\) such that for every \(a \in A\), there is exactly one \(b \in B\) such that \((a, b) \in R\). We write \(f: A \to B\) to denote that \(f\) is a function from \(A\) to \(B\). If \((a, b) \in f\), we write \(f(a) = b\).

The possible set of inputs (elements of \(A\)) is called the domain of the function, and the possible set of outputs (elements of \(B\)) is called the codomain of the function. The set of actual outputs (elements of \(B\) such that there exists an \(a \in A\) with \(f(a) = b\)) is called the range of the function.

Are the following functions, relations, or neither? Consider, \(a,b \in \mathbb{Z}\).

  • \(\{(a,b)| b = a^2\}\)

  • \(\{(a,b)| a \geq b\}\)

  • \(\{(a,b)| b^2 = a\}\)

We often classify functions as one-to-one (injective), onto (surjective), or bijective.

A function \(f: A \to B\) is one-to-one if for all distinct elements \(a, a' \in A (a \neq a')\), \(f(a) \neq f(a')\). Note this implies \(|A| \leq |B|\).

A function \(f: A \to B\) is onto if for every \(b \in B\), there exists at least one \(a \in A\) such that \(f(a) = b\). Note this implies \(|A| \geq |B|\).

A function \(f: A \to B\) is bijective if it is both one-to-one and onto. Note this implies \(|A| = |B|\).

Refer to the "potato drawings" to visualize these concepts.

Inverses

The inverse of a binary relation \(R \subseteq A \times B\) is the relation \(R^{-1} \subseteq B \times A\) defined by: for all \(a \in A\) and \(b \in B\), \((b, a) \in R^{-1}\) if and only if \((a, b) \in R\). The inverse of a relation is always a relation.

Is the inverse of a function a relation? Is it a function? What if the function is one-to-one? Onto? Bijective? Justify your answers.

Automata

Our primary goal in this course is to design computational devices called automata that can recognize languages. An automaton \(M\)takes as input a string \(w\) over some alphabet \(\Sigma\) and either accepts or rejects the string. If the automaton accepts the string, then the string is in the language \(L(M)\) recognized by the automaton \(M\); otherwise, the string is not in the language.

Given a language \(L\) over an alphabet \(\Sigma\), our goal is to design an automaton \(M\) such that \(L(M) = L\).