100% satisfaction guarantee Immediately available after payment Both online and in PDF No strings attached
logo-home
COS2601 EXAM PACK 2023 $2.83   Add to cart

Exam (elaborations)

COS2601 EXAM PACK 2023

1 review
 71 views  5 purchases
  • Course
  • Institution

COS2601 EXAM PACK 2023 QUESTIONS WITH ANSWERS

Preview 4 out of 230  pages

  • June 22, 2023
  • 230
  • 2022/2023
  • Exam (elaborations)
  • Questions & answers

1  review

review-writer-avatar

By: terence21 • 5 months ago

avatar-seller
COS2601
EXAM PACK
2023
QUESTIONS WITH ANSWERS
EMAIL: musyokah11@gmail.com

,COS2601 EXAM
PACK 2023
LATEST QUESTIONS
AND ANSWERS
For queries or any assignment help
Email: musyokah11@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

The benefits of buying summaries with Stuvia:

Guaranteed quality through customer reviews

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

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

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 mulah11. Stuvia facilitates payment to the seller.

Will I be stuck with a subscription?

No, you only buy these notes for $2.83. You're not tied to anything after your purchase.

Can Stuvia be trusted?

4.6 stars on Google & Trustpilot (+1000 reviews)

67866 documents were sold in the last 30 days

Founded in 2010, the go-to place to buy study notes for 14 years now

Start selling
$2.83  5x  sold
  • (1)
  Add to cart