ICS 804 /
P58/76159/2012 /
John Nganga /
11/8/2012 /
Assignment 01 /
ASSIGNMENT ONE [30 mks]
a) In a group of 500 people 400 can speak English and 300 can speak Swahili. If all the people
can speak at least one of the two languages, find:
(i). how many can speak both languages?
200
(ii). how many can speak exactly one language
300
100 / 200 / 300 / 400 / 500English
Swahili
English only / Both Eng & Swa / Swahili only
b) Classify each of the following functions as injective or not injective, as surjective or not
surjective and also as bijective or not bijective
(i). f: N → N
f(n) = n div 3
since :
injective function or an injection is a function that preserves distinctness: it never maps distinct elements of its domain to the same element of its codomain.
A bijection (or bijective function or one-to-one correspondence) is a function giving an exact pairing of the elements of two sets. Every element of one set is paired with exactly one element of the other set, and every element of the other set is paired with exactly one element of the first set. There are no unpaired elements
a function f from a set X to a set Y is surjective (or onto), or a surjection, if every element y in Y has a corresponding element x in X so that f(x) = y. Multiple elements of X might be turned into the same element of Y by applying f.
it is injective
it is bijective
it is not surjective
(ii). g: N → N
g(n) = n2+ 2n + 1
it is not injective
it is not bijective
it is surjective
(iii). h: Σ* → Σ* where Σ = {a, b}
h (w) = ana(w)
it is not injective
it is not bijective
it is surjective
c) Prove that if f(n) and g(n) are both O(h(n)), the f(n) + g(n) is O(h(n)) as well. [5 mks]
(sorry Sir, the prove I will have to send to you on email. I cannot find a scanner near by)
d) Design a Turing machine that computes the number theoretic function f(n) = n2. [5 mks]
This is implemented using two tapes. Tape one has the value for n and tape two will have the n2 values.
first the '1' is erased and the remaining 1's are copied to tape two once.
then erase again the left most 1 and append a copy of the others in tape two.
if still more 1's in tape one, repeat the above.
When done, append a 1 in tape two for number theoretic encoding of the square value.
e) Present the state diagram of a Turing machine that accepts by terminal state the language of
words over Σ {a , b}, whose length is 3 or more. [3 mks]
f) Design a Turing Machine that accepts by terminal state the language {anbam|n, m≥0}. [3
mks]
g) Design a Turing machine M with one-way-infinite tape that reverses any input word w over
input alphabet Σ{a,b}, When M halts, its read/write head should be scanning tape square
immediately to the right of left end marker λ on which square should appear the leftmost
symbol of wR. [4 mks]
Final tape configuration: