COS3701 - Theoretical Computer Science III (COS3701)
Institution
University Of South Africa (Unisa)
COS3701 Assignment 2 Solutions A+ Guaranteed. Contact us if you have any queries. Note do not submit the file as it is, to avoid plagiarism use this document as a guide for your own assignment .
, QUESTION 1
Build a DPDA to show that the language
is deterministic context free.
The smallest word in this language is when n= 3. This word is abababaaaba. All words in this
language start with three or more abs and end with one or more bas where there are always
two more abs than bas.
The trick to showing that this language is context free is to use the PDA to "match" the
occurrences of ab to the occurrences of ba which appear later in the string. We should also
take care of the fact that there have to be two more abs than bas but there has to be at least
one ba (and three abs).The aaa string in the middle is a separator and does not affect the
decision of whether or not the language is context free.
Our PDA can thus be outlined as
1. Read two instances of ab (but do nothing to the stack). These are the extra abs that we can
simply get rid of because we know there should be exactly two of them.
2. Read in one instance of ab (this matches with the one required ba).
3. Read in additional instances of ab and for each such instance push an X onto the stack.
Here we are essentially counting how many abs we have.
4. Read in aaa (but do nothing to the stack).
5. Read in the one required ba.
6. Read in instances of ba and for each instance pop an X off the stack. Here each ba is ticked
off against an ab that was read at the beginning of the string.
7. When all of the bas have been read then check that the input string and the stack are both
empty. We can now build a PDA to do this. The PDA is shown in diagram below.
2
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 MyAssignments. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $14.35. You're not tied to anything after your purchase.
