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.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- acrostic poem adjective word list young wife s guide
- acknowledging children s positive behaviors
- solutions to problem set 3 people eecs at uc berkeley
- character traits from a to z
- a to z of positive words augusta county public schools
- academic word list positive and negative connotations
- find and circle the words from positive promotions
- alphabet of stress management and coping skills
- worked solutions 1 enumerability
- top 100 list of positive affirmations 3 simple steps to
Related searches
- worked with synonym
- worked with synonym resume
- another phrase for worked with
- another way to say worked with
- another word for worked together
- synonyms for worked closely with
- worked on thesaurus
- another term for worked with
- another word for worked with
- synonym for worked together
- synonyms for being worked on
- another word for worked on