Theory of Automata

Exercises:

Formally define an injection that proves each of the following statements. The first two are worked for you. If you are unsure what notation to use to define a function, you may use Python.

1. |N {(0,1)}| |N|

For each x in N {(0,1)} let

f(x) =

x+1 if x N;

0 otherwise

in Python:

def f(x):

if isinstance(x,int): return x+1

return 0

2. |N {(0,0),...,(0,19)}| |N|

For an ordered pair u we will write u1 the first coordinate of u, and u2 for the second coordinate of u. Now, for each x in N {(0,0),...,(0,19)} let

f(x) =

x + 20 if x N;

x2 otherwise

in Python:

def(x):

if isinstance(x,n): return x+20

return x[1]

3. |N {0} N{1}| |N|

4. |N N| |N|

5. |N N {1..6}| |N|

for each (i,j,k) in N N {1..6}

let f(i,j,k) = 2i3j5k

6. |N NN| |N|

7. A set S is countable if |S| |N|. Is the set of all finite strings of ascii characters countable? If so, define an injection that demonstrates this. If not, give a proof.

def listStrings(S) -- calculate a number for each string so that no two strings are

mapped to the same number.