COS2601 previous assignment solutions and study guide

COS2601/201/0 /2022




Tutorial letter 201/0/2022

Theoretical Computer Science II
COS2601
Year Module

School of Computing




Discussion of Assignment 1

, COS2601/201/0/2022

Dear student

Solutions to the questions of assignment 1 are provided in this tutorial letter.

COS2601 regards

Question 1

Question:
Who created the subject of mathematical models for the description of languages in an attempt to
answer questions such as:
• What is language in general?
• How could primitive humans have developed language?
• How do people understand language?
• How do children learn language?
• How do people construct sentences from the ideas in their minds?

Options: David Hilbert
Noam Chomsky
Kurt Gödel
Alan Turing

Answer: Noam Chomsky

Discussion: We investigate what role Hilbert, Chomsky, Turing and Gödel played in the history of the
subject of computer theory:

Noam Chomsky

Noam Chomsky created the subject of mathematical models for the description of languages in an
attempt to answer the questions provided in the question statement. His theory developed and later
shed light on the study of computer languages. Refer to Cohen, page 6, paragraph 2. This option should
be regarded as the correct one.

David Hilbert
Hilbert wanted the confusion around set theory to be resolved – he wanted a precise axiomatic system
built for set theory. Hilbert not only believed that every mathematical provable result should be true, he
also presumed that every true result was provable and he wanted a methodology that would show
mathematicians how to find this proof. The language of algorithms that Hilbert required evolved into
the language of computer programs. Hilbert did not attempt to answer the questions provided in the
question statement. Refer to Cohen, page 3, last paragraph, and page 4, paragraphs 1 - 6.

Alan Turing
One of the mathematical problems Church, Kleene, Post, Markov, Von Neumann and Turing worked
independently on was to determine which mathematical statements have proofs and how to generate
these proofs. Independently these people developed similar versions of a universal model for
algorithms. The development of the Turing Machine and the proof which Turing provided that there
were mathematically definable fundamental questions about the Turing Machine itself that the machine
could not answer, destroyed all hope of ever achieving Hilbert’s program of mechanizing mathematics.
2

, COS2601/201/0/2022

Turing was involved in the construction of the machine that was used in breaking the German secret
code. Turing did not attempt to answer the questions provided in the question statement. Refer to
Cohen, page 5, paragraphs 1 - 3.

Kurt Gödel
Gödel proved that there was no algorithm to provide proofs for all true statements in mathematics.
Gödel did not attempt to answer the questions provided in the question statement. Refer to Cohen,
page 4, paragraph 7.

Question 2

Question:
Let S = {a b} and let T= {a b bb}. Which one of the following statements is true?

Options: S+ = S*
S* = S**
S  S*
S* ≠ T*

Answer: S* = S**

Discussion: Firstly, we should remember that for any sets A and B, A = B iff A  B and B  A.
(A  B iff each element of A is also an element of B.)

S* = S**
If S = {a b} then
S** = {a b}**
= {Λ a b aa bb ab ba aaa bbb abb bba aab baa …}*
= {Λ ΛΛ ΛΛΛ … Λa ΛΛa … Λb … a b aa bb ab ba aaa bbb abb bba aab baa …}
= {Λ a b aa bb ab ba aaa bbb abb bba aab baa …}
= S*.
(From Theorem 1, p. 18 of Cohen, S* = S**.)
The statement in this option is true and should be the option chosen.

S+ = S*
If S = {a b} then
S* = {a b}* = {Λ a b aa bb ab ba aaa bbb abb bba aab baa …}, comprising all possible concatenations of
a’s and b’s, together and separately, and Λ is also a word in S*.
S+ is the language S* without the word Λ, i.e. S+ = S* – {Λ} i.e. S+ ≠ S*.
The statement in this option is not true.

S  S*
If S = {a b} then S* = {Λ a b aa bb ab ba aaa bbb abb bba aab baa …},
thus every element of S, namely a and b, are also elements of S*,
that is, S is a subset of S*.
The statement in this option is not true.




3

, COS2601/201/0/2022

S* ≠ T*
Consider S = {a b} and T = {a b bb}.
S* = {a b}*, and
T* = {a b bb}* = {a b}* = {Λ a b aa bb ab ba aaa bbb abb bba aab baa …}
Thus S* = T*.
The statement in this option is not true.




Question 3

Question:
Which one of the following statements is true?

Options: if s = {a ab} and t = {a ba}, then s* = t**
if s = { a} and t = {a}, then s*  t*
if s = { a }, then s+ = {a}
if s = {a}, then s** = { a aa aaa …}

Answer: if s = {a}, then s** = { a aa aaa …}

Discussion:

if s = {a ab} and t = {a ba}, then s* = t**
It is not the case that S* = T** if S = {a ab} and T = {a ba}. By the theorem on page 18 of Cohen, T** = T*.
We provide a counterexample to prove that S*  T*: ab  S and thus also ab  S*, but ab  T*. Thus
this statement is not true and is not the correct option.

if s = { a} and t = {a}, then s*  t*
If S = { a} and T = {a}, then S* = { a}* = {a}* = T*. Thus, the statement is not true.

if s = { a }, then s+ = {a}
If S = { a }, then S+ = {a} is not true because S+ = { a aa aaa …}

if s = {a}, then s** = { a aa aaa …}
If S = {a}, then S* = { a aa aaa …} = S**, so this statement is true, and should be selected as the correct
option.




4