COS3701 Latest exam pack questions and answers and summarized notes for exam preparation. Updated for 2024 exams . For assistance Whats-App.0.6.7..1.7.1..1.7.3.9 . All the best on your exams!!
Exam (elaborations) COS1501 Assignment 2 (COMPLETE ANSWERS) 2024 (653506) - 14 June 2024 • Course • Theoretical Computer Science I (COS1501) • Institution • University Of South Africa (Unisa) ...
Exam (elaborations) COS1501 Assignment 2 (COMPLETE ANSWERS) 2024 (653506) - 14 June 2024 • Course • Theoretical Computer Science I (COS1501) • Institution • University Of South Africa (Unisa) ...
Exam (elaborations) COS1501 Assignment 2 (COMPLETE ANSWERS) 2024 (653506) - 14 June 2024 • Course • Theoretical Computer Science I (COS1501) • Institution • University Of South Africa (Unisa) ...
All for this textbook (27)
Written for
University of South Africa (Unisa)
Theoretical Computer Science (COS3701)
All documents for this subject (1)
1
review
By: ahmadsardar • 1 month ago
Well the questions and answeres are not in Order
Seller
Follow
iStudy
Reviews received
Content preview
COS3701
EXAM PACK
FOR ASSISTANCE WITH THIS MODULE +27 67 171 1739
,Question 1
Build a DPDA to show that the language L = {(ab)n(ba)naa | n > 0} is deterministic
context free.
Solution
For this DPDA we have
∑ = {a, b, Λ}
Г = {X, Λ}
In this DPDA the first ab substring (which must exist by the definition of the
language) is read and an X is pushed onto the stack.
Then subsequent ab substrings are read (each time pushing an X onto the stack)
until the first b in the first ba substring is read. At this point the second part of the
DPDA starts working to recognise the ba substrings.
An X is popped off the stack for each ba found.
When the first a of the aa substring is read the DPDA reads the next a, then reads a
blank a and then checks that all the Xs have been popped off the stack. If there were
still any Xs on the stack then the number of ab and ba substrings would not have
been the same and the word would not be in the language.
Suppose we are given the word ababbabaaa. The first a and the first b will be read
by the two Reads before the Push. Then a X will be pushed onto the stack. Then the
next ab will be read before pushing another X onto the stack. At this point the stack
contains two Xs – one for each ab substring.
Then a b is read an the DPDA starts processing the ba substrings (this is done by
the loop in the middle of the figure). As each ba is read an X is popped off the stack.
When an a is read then the DPDA expects another a and then so it reads that.
After two as the input tape and the stack must both be empty and so the DPDA
checks both of these.
Check using other words in the language that the DPDA is correct.
The following Figure 1 shows a DPDA which recognises the language.
, Figure 1
Question 2
Prove that the language L = {anb3nan} is non-context free. Use the pumping lemma
with length.
Solution
The first step is to assume that the language L = {anb3nan | n = 1; 2; 3; ...}
actually is context free. This means that there exists a CFG in Chomsky
Normal Form (CNF) with, say, p live productions which generates the
language. Because we assume that the language is context free, we may
apply the pumping lemma.
According to the pumping lemma with length any word w in L with more than
2p characters can be broken up into five parts, i.e. the word can be written as
w = uvxyz, with
length(vxy) ≤ 2p and
length(x) > 0 and
, length(v) + length(y) > 0
and where all words of the form uvnxynz with n > 1 are also in the language.
1. We should next choose a suitable word from L which is long enough. The
word a2pb3.2pa2p seems a good choice: it is in L and it has more than 2p
characters. Let us examine all the different ways in which the word a2pb3.2pa2p
can be divided up into five parts. Remember that vxy cannot have more than
2p characters. This means that there are five ways in which vxy can occur in
the word:
(a) fully from the first 2p characters (thus consists of as only),
(b) covering some of the first as and also some of the bs,
(c) fully from the group of bs,
(d) covering some characters of the group of bs and some characters of
the final group of as,
(e) fully from the second group of as.
We now examine each of these five possibilities. We are going to show that
the pumped word will in none of these cases be of the form anb3nan.
(a) Suppose vxy consists of as only from the first group of as. According to the
pumping lemma with length the word uvvxyyz must also be in the language L.
This word will now have more than 2p as at the beginning of the word followed
by b3.2pa2p and will not be of the form anb3nan. Such a word is not in L.
(b) Suppose vxy consists of as followed by bs. According to the pumping lemma
with length the word uvvxyyz must also be in the language L. What will this
(pumped) word look like? Well, there are several possibilities.
• If v consists of as only and y consists of bs only, the pumped word will
have more than 2p as at the beginning of the word followed by more than
3.2p bs, followed by a2p. The word is not of the form anb3nan and is thus not
in L.
• If v consists of as and bs, and y of bs only, the pumped word will have
more than 2p as followed by more than 3.2p bs, followed by 2p as. There
will also be more ab-substrings than allowed. The word is not of the form
anb3nan and thus not in L.
• The same problem will occur if v consists of as only and y consists of as
and bs, because the pumped word will have more than 2p as, followed by
more than 3.2p bs and more than 2p as followed by a2p. There will also be
more ab-substrings than allowed. The word is not of the form anb3nan and
thus not in L.
• In any of the above mentioned three possible cases either v or y may be
empty (both cannot be empty – are you able to explain why not?), but still
the pumped word will not be a permissible word in L.
(c) Suppose vxy consists of bs only. According to the pumping lemma with length
the word uvvxyyz must also be in the language L. This word will now have 2p
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 iStudy. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $2.84. You're not tied to anything after your purchase.
