# In-Class Exercises for 335: Theory of Computing

## Class 1
1. Let $A$ be the subset of all real numbers in $[0,1]$ (i.e. between $0$ and $1$) with decimal representation only using the digit "4" (e.g., $0.4, 0.44, 0.44444 \dots, \dots$ ) . Is $A$ countable or uncountable?
*Extra*: What if we consider all positive real numbers, not just those restricted to $(0,1)$ (i.e., numbers of the form $4.4, 444.4444 \dots, 0.44, \dots$)?

Answer by stating the claim (as a theorem), and provide proof.

## Class 2

#### 1. DFA: ####
Let the alphabet $\Sigma_{DNA}=\{A, C, G, T \}$. The amino acid $\text{Lysine}^*$ corresponds to the substring "AAA" or "AAG". The goal is to design a DFA that given an DNA sequence over the alphabet $\Sigma_{DNA}$ detects the amino-acid Lysine. This DFA accepts the given string if it contains "AAA" or "AAG" as a substring.
${ }^*$ Such a DFA would have helped implement the "Lysine contingency" in Jurassic Park :).

#### 2. Diagonalization: ####
Let $B$ be the subset of all real numbers in $(0,1)$ with decimal representation only using the digits "4" and 5" (e.g., $0.4, 0.444544554\dots,0.5555 \dots$) . Is $B$ countable or uncountable?

Answer by stating the claim (as a theorem), and provide proof.