Worked Solutions 1 - enumerability

Worked Solutions 1 - enumerability

Richard McKinley

March 13, 2005

1 Introduction

These are selected model answers to exercises from lecture handout 2. Each section corresponds to a slide from that handout.

2 Page 12

Exercise 2.1. If A, B and C are enumerable sets, the set of triples A ? B ? C = {(a, b, c) : a A, b Bc C}

is enumerable. Proof. The product of two enumerable sets is enumerable. Writing A ? B ? C as (A ? B) ? C, we see that it is the cartesian product of two enumerable sets: A?B and C. Since A and B are enumerable, A?B is enumerable So we see that A ? B ? C is the product of two enumerable sets, and hence enumerable. Exercise 2.2. If A1, . . . , Ak are enumerable sets, then A1 ? . . . ? Ak is enumerable. Proof. By induction. The base case (k = 1) is trivial.

Now suppose that, for any enumerable sets A1, . . . , An, the set A1 ? . . . ? An is enumerable. Then, given another enumerable set An+1, A1?. . .?An?An+1 = B ? A, where B = A1 ? . . . ? An is enumerable. B ? A is the cartesian product of two enumerable sets, and so is enumerable.

3 Page 13

Exercise 3.2. If B is enumerable and there is a total injective function A B, then A is enumerable. Proof. If B is enumerable, there is a coding of B - an total injective function f from B to N. We know we have a total injective function g : A B, and their composition f g is a function A N. This function is total and injective (you should check this, and in an exam we would expect you to prove it) and so A is enumerable.

1

4 Page 14

Exercise 4.1. The set Q+ is enumerable.

Proof. Let surjective,(

the for

function example,

f : N ? N Q+ take each rational number r

(a, b) has a

to

a b

form

.

This function

m n

where

m

and

is n

share no factors, and then (m, n) is a pre image for r) and we know that N ? N

is enumerable, (via Cantor's zig-zag or an encoding c((m, n)) = pn ? qm where p

and q are prime) so Q+ is enumerable.

Exercise 4.4. The set A of strings over an enumerable alphabet A is enumerable.

Proof. A is enumerable, and so we have an encoding cA : A N. We will give a total injective function A N ? N. This will be enough to show that A is enumerable (Why?).

A is enumerable, and so we have an encoding cA : A N. From a previous exercise, we know that for each n N there is an encoding cn : An N.

cn((a1, . . . , an)) = cN????N(cA(a1), . . . cA(an))

Regarding each string s of length n as an n-tuple, we have a function

cA : A N ? N,

cA (a1a2a3 . . . am) = (m, cm((a1, . . . , am))

This is injective and total, so we are done. (You should verify yourself that this function is injective and total, and in an exam you should prove these claims).

5 Page 25

Exercise 5.2. Suppose that we have a programming language, such that every program describes a function N N . Show that there must be functions N N that are described by no program.

Proof. Any program can be thought of as a finite string from a finite alphabet of letters. We can therefore infer that the set of programs is enumerable. By contrast, the set of all functions N N is non-enumerable (see lectures).

So there is no surjective map from programs to functions (if there were, then the set of functions would be enumerable). In particular, the map that takes programs to the function they compute is not surjective, and hence there are functions for which there is no program.

2

Worked Solutions 2 - finite automata

Richard McKinley March 16, 2005

1 Introduction

These are selected model answers to exercises from lecture handout 3. Each section corresponds to a slide from that handout.

Exercise 1.1. Give DFA's accepting the following languages over the alphabet {0, 1}.

1. The set of all strings ending in 00.

2. The set of all strings with two consecutive 0's (not necessarily at the end).

3. The set of strings with 011 as a substring.

Proof. For each part, we give a transition diagram which is a solution to the problem (and for the first, we give two alternative solutions). Following each diagram is a discussion of the meaning of the states of the machine; you should try to work this out for yourselves before reading.

1. The following is a "conceptually clean" solution, in the sense that each state corresponds to different ending of the string:

0

Start

00 0

1

0

0

0

1

01

0

1

1

0

10

1

1

0

1 11

1

1

An alternative solution is given below:

0 start

q0 1

1

0 q1 1

q2

0

q0 : String has no trailing zeroes. q1 : String has one trailing zero. q2 : String has two trailing zeroes.

2. Here is a machine which accepts the given language.

0 start

q0

1

1

0 q1

q2

0

1

q0 : String contains no 00, and the last symbol was a one

q1 : String contains no 00, and the last symbol was a zero

q2 :

String contains a 00

3.

start

0

q0

1

1 q1

0

0

1 q2

q3

0

1

q0 : String contains no 011, and the last symbol was a one

q1 : String contains no 011, and the last symbol was a zero

q2 : String contains no 011, and the string so far ends 01

q3 :

String contains 011

Exercise 1.2. Give a DFA accepting the following language over the alphabet {0, 1}: The set of all strings whose tenth symbol from the right is a 1. Proof. Main Idea: The states of the machine track the last 10 symbols read by the machine.

Q = {x1x2 . . . xn | 0 n 10, and xi {0, 1} for all i {1, . . . n}}

2

q0 = (the empty string) = {0, 1}

F (the accepting states) = {1x2 . . . x10 | xi {0, 1} for all i {2, . . . 10}}

(x1x2 . . . xn, y) =

x1x2 . . . xny if n < 10 x2 . . . xny if n = 10

Exercise 1.3. Consider the DFA with the following transition table:

01 A A B B B A

(1) Informally describe the language accepted by this DFA; (2)prove by induction on the length of an input string that your description is correct.

Proof. You should draw the transition graph before reading this answer; it will help with your understanding.

We claim that the language of the DFA is {w | w contains an odd number of 1's}. (Now you know about regular expressions, write this as a regular expression).

The proof is by induction, but the induction hypothesis is stronger than you might expect:

Claim:

^(A, w) =

A if w contains an even number of 1's B if w contains an odd number of 1's

Base case w = ^(A, ) = A, as has an even number of 1's

Inductive Step: We show the case for a string which ends in 1, and leave

the case of a string ending in 0 to the reader as an exercise.

^(A, w) = ^(A, v1) = (^(A, v1), 1) =

(A, 1) if v contains an even number of 1's (B, 1) if v contains an odd number of 1's

3

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download