Exam (elaborations)
Theoretical Computer Science II(COS2601 Exam pack 2023)
- Course
- Institution
Theoretical Computer Science II(COS2601 Exam pack 2023) Questions and accurate answers with assurance that they are in the exam.
[Show more]
Seller
Follow
gabrielmusyoka940
Reviews received
Content preview
COS2601 EXAMPACK 2023
QUESTIONS AND
ANSWERS
For assistance contact
Email:gabrielmusyoka940@gmail.com
, COS2601/202/2
Dear student
Solutions to the questions of assignment 2 are provided in this tutorial letter.
For this assignment, the following questions were used for calculating a mark for the
assignment.
Question 1 11marks
Question 2 12 marks
Question 3 5 marks
Question 5 7 marks
TOTAL 35 marks
The rest of the questions were only commented on, and not allocated a mark. Remember
to do the “Automata” and “Pumping lemmas” tutorials which are available on a CD that
you should have received.
Everything of the best with your studies!
Regards
COS2601 team
Question 1
A recursive definition for the language AtLeast3EndBB over the alphabet ∑ = {a b} must be
compiled where AtLeast3EndBB has as elements all words that have at least three characters
and end with a bb-substring.
Give (i) an appropriate universal set,
(ii) the generator(s) of AtLeast3EndBB, and
(iii) an appropriate function on the universal set, and then
(iv) use these concepts to write down a recursive definition of the language
AtLeast3EndBB.
Answer 1
(i) The set { a b}* will be suitable because it contains, along with other words, all the words
that are in the language AtLeast3EndBB.
(ii) The generators are abb and bbb. Note that the generator(s) is/are always the shortest
word(s) in a language.
(iii) The function CONCAT as defined in learning unit 3, will be suitable. You can see how this
function has been used in Activity 3.1 in learning unit 3.
(iv) We give two possible recursive definitions. Note that we need to ensure that when we
concatenate strings to form new words that we do not generate words that end with a
2
, COS2601/202/2
single isolated bor an a– this would result in words ending on an ab- or a-substring, and
these words are not in AtLeast3EndBB.
We give two possible recursive definitions.
AtLeast3EndBB is the smallest subset of { a b}* such that
abb, bbb AtLeast3EndBB
and if w AtLeast3EndBB, then also
CONCAT( a, w), CONCAT( b, w), CONCAT( w, b) AtLeast3EndBB.
or
Rule 1: abb, bbb AtLeast3EndBB
Rule 2: If w AtLeast3EndBB, then also
CONCAT( a, w), CONCAT( b, w), CONCAT( w, b) AtLeast3EndBB.
Rule 3: Only words generated by rules 1 and 2 are in AtLeast3EndBB.
Question 2
This question has three parts and tests mathematical induction.
(i) Provide a recursive definition for the set P of all positive integers greater than 0,
(ii) formulate the appropriate induction principle, and then
(iii) apply the induction principle to prove that for each integer n > 0,
n 2 n(n + 1)( 2n + 1)
j =
j =1 6
.
Answer 2
(i) P is the smallest subset of R such that 1 P and if k P then also
k+1 P.
Another correct recursive definition for P is:
Rule 1: 1 P
Rule 2: If k P, then also k+1 P
Rule 3: Only elements generated by the above rules are in P.
(ii) The applicable induction principle is:
If a subset A of P is such that 1 A and if k A then also k+1 A, then A = P.
(iii) Define A ⊆ P as follows:
n 2 n(n + 1)(2n + 1)
A = {n | n P and j
j =1
=
6
}
We want to prove that this subset A of P is actually equal to P. The first step is to find out
whether the element 1 is in A. We do it as follows:
3
, COS2601/202/2
1 2
LH: j =1 RH: 1(1 + 1)( 2(1) + 1)
j =1 6 =1
Because LH = RH = 1 - the element 1 does indeed have the necessary property that
qualifies it to belong to A.
Thus 1 A.
We have achieved our first goal. Secondly, we assume thatk A. If k A and we can prove
that k + 1 A then it follows that A = P. We therefore assume we have some k A such
that
k 2 k (k + 1)(2k + 1)
j
j =1
=
6
Now we should try to show that k+1 A, i.e. we must prove that
k +1 2 (k + 1)((k + 1) + 1)(2(k + 1) + 1)
j
j =1
=
6
PROOF
k +1 2 k (k + 1)(2k + 1)
j
j =1
=
6
+ (k + 1)2
…………from our assumption
k (k + 1)(2k + 1) + 6(k + 1) 2
=
6 …………6 as denominator for all terms
(k + 1)[k (2k + 1) + 6(k + 1)]
=
6 …………(k + 1) is a common factor
(k + 1)[(2k 2 + k ) + 6k + 6]
=
6 ………….simplify
(k + 1)[(2k 2 + 7k + 6]
=
6 ………….simplify
(k + 1)(k + 2)(2k + 3)
=
6 ………….factorise trinomial
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 gabrielmusyoka940. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $2.50. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
78075 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now