Other
COS2601 previous assignment solutions and study guide
- Course
- Institution
COS2601 previous assignment solutions with a study guide.
[Show more]
Seller
Follow
PotatoArmor
Content preview
COS2601/201/0 /2022Tutorial 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
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller PotatoArmor. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $3.33. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
53068 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now