TOC-As-1

Question 1

$a.\mathbb{Z}\times \mathbb{Z}iscountable$.

Construct a counting procedure as below:

Each pair corresponds to a unique natural number. Therefore $\mathbb{Z}\times \mathbb{Z}$is countalbe

$b.IfsetSiscountableandnisanaturalnumberconstant,then{S}^{n}iscountable$.

Case I

If $S$is a finite set with $m$element;

Then $|S^n|=m^n$which is finite. Therefore $S^n$is countable.

Case 2

If $S$is a infinite and countable set; Then there must be a bijection between $S$and $\mathbb{N}$.

And for 2 countable sets $A$$B$, $A\times B$is also a countable set.

For any element $(a,b)\in A\times B$, we can write $a=f(i)$and $b=g(j)$for some $i,j\in \mathbb{N}$.

Therefore, $(a,b)$corresponds to the pair $(f(i),g(j))$, which in turn corresponds to the natural number pair $(i,j)$.

To establish a one-to-one correspondence, we can use a pairing function that maps each pair $(i,j)$to a unique natural number k .

$$k=\frac{(i+j)(i+j+1)}{2}+j$$

Therefore, $A\times B$is countable.

Since $S^n=S\times S\times \cdots \times S$n times.

And $S\times S$is countable.

Therefore $S^n$is countable.

Solution:

$Bijection|\{a|a\in \mathbb{R}\wedge 0<a<1\}|\to \mathbb{R}:tan(\pi x-\frac{\pi }{2})$

$d.\{a|a\in \mathbb{R}\wedge 0<a<10\}$is uncountable.

Suppose a real number $a_i\in (0,10)$denote as $a_i=a_{i,1}{a}_{i,2}\dots$. Then we build the table as below:

Index	$a_n$	Digits
0	$a_0$	$a_{0,0}{a}_{0,1}{a}_{0,2}\dots$
1	$a_1$	$a_{1,0}{a}_{1,1}{a}_{1,2}\dots$
2	$a_2$	$a_{2,0}{a}_{2,1}{a}_{2,2}\dots$
$⋮$	$⋮$	$⋮$

Next we define a real number $a_x=a_{x,0}{a}_{x,1}\dots$such that $a_{x,i}=(a_{i,i}+2)mod10$. We can see a xis not in the list!

• $a_x$and $a_0$are different at digit 0.

• $a_x$and $a_1$are different at digit 1.

• $a_x$and $a_2$are different at digit 2.

• $a_x$and $a_3$are different at digit 3.$\dots$

Thus, $a_x$is not counted and set of reals in (0, 10) is uncountable.

$\{f|f:\mathbb{N}\to \{0,1\}\}$is uncountable

Assume that the set of functions from $\mathbb{N}$to $\{0,1\}$is countable.

Suppose all such functions can be listed as $f_1,f_2,f_3,\dots$.

Define a function $g$such that $g(n)=1-f_n(n)$. This ensures that $g$differs from each $f_i$at least at position $i$.

Since $g$is not equal to any $f_i$in the list, this contradicts the assumption that we have listed all possible functions.

Therefore, the set of functions from $\mathbb{N}$to $\{0,1\}$is uncountable.

Question 2

Prove the followings.(1 pt for each)

a

$Foragivenalphabet\mathrm{\Sigma },thenumberofDF{A}^{{}^{\prime }}over\mathrm{\Sigma }iscountable$

b

Two sets are isomorphic if they are of the same cardinality. Prove that the number of DFA's (without specifying $\mathrm{\Sigma }$) is countable up to set isomorphism.

Question 3

Let $\mathrm{\Sigma }=\{a,b\}.$Construct a DFA for each of the following languages. (10 pt for each)

a.$\{w|whasatleastonea\}$

Current State	$a$	$b$
$q_0$	$q_1$	$q_0$
$q_1$	$q_1$	$q_1$

b.$\{w|whasnomorethanthree{a}^{\prime }s\}$

Current State	$a$	$b$
$q_0$	$q_1$	$q_1$
$q_1$	$q_2$	$q_1$
$q_2$	$q_3$	$q_2$
$q_3$	$q_4$	$q_3$
$q_4$	$q_4$	$q_4$

c.$\{w|wdoesnothaveabasasubstring\}$

Current State	$a$	$b$
$q_0$	$q_1$	$q_2$
$q_1$	$q_1$	$q_3$
$q_2$	$q_1$	$q_2$
$q_3$	$q_3$	$q_3$

d. $\{w|wcontainsnorunsoflengthlessthanfor\}.$A run in a string is a substring of length at least one and consisting entirely of the same symbol. For example, $abbbaab$has four runs: $a,bbb,aa,b$.

Current State	$a$	$b$
$q_0$	$q_1$	$q_2$
$q_1$	$q_3$	$q_9$
$q_2$	$q_{10}$	$q_4$
$q_3$	$q_5$	$q_9$
$q_4$	$q_{10}$	$q_6$
$q_5$	$q_7$	$q_9$
$q_6$	$q_{10}$	$q_8$
$q_7$	$q_7$	$q_2$
$q_8$	$q_1$	$q_8$
$q_9$	$q_9$	$q_9$
$q_{10}$	$q_{10}$	$q_{10}$

Question 4

Let $M=(Q,\mathrm{\Sigma },\delta ,q_0,F)$be an arbitrary DFA. We construct a new DFA $M^{\prime }$as $M^{\prime }=(Q,\mathrm{\Sigma },\delta ,q_0,Q\setminus F)$. We need to prove that $\overline{L(M)}=L(M^{\prime })$.

Note:

• $Q\setminus F$is the set difference.

• $L(\bar{M})={\mathrm{\Sigma }}^{\ast }\setminus L(M)$is the set complement.

---

The goal $L(\bar{M})=L(M^{\prime })$is understood as set equality.
Thus, we need to prove $\mathrm{\forall }w\in {\mathrm{\Sigma }}^{\ast }$, $w\in L(\bar{M})⟺w\in L(M^{\prime })$.

($\Rightarrow$)
Assume $w\in L(\bar{M})$.
Then $w\notin L(M)$.
Thus, DFA $M$rejects $w$.
In other words, DFA $M$halts on a non-final state $q_x$by consuming all symbols in $w$.
By the construction of $M^{\prime }$, $q_x$is a final state of $M^{\prime }$.
Thus, $M^{\prime }$accepts $w$, and $w\in L(M^{\prime })$.

---

($\Leftarrow$)
Assume $w\in L(M^{\prime })$.
DFA $M^{\prime }$accepts $w$.
In other words, DFA $M^{\prime }$halts on a final state $q_y$by consuming all symbols in $w$.
By the construction of $M^{\prime }$, $q_y$is a non-final state of $M$.
Thus, $M$rejects $w$, so $w\notin L(M)$.
Thus, $w\in L(\bar{M})$. $L(\bar{M})=L(M^{\prime })$.