100% satisfaction guarantee Immediately available after payment Both online and in PDF No strings attached
logo-home
Previously searched by you
Previously searched by you
logo
COS3701 Assignment 2 [Unique No:830417] 2022 R250,00   Add to cart
Quickly navigate to
Preview
  2.  
  3. University Of South Africa (Unisa)
  4.  
  5. COS3701 - Theoretical Computer Science III (COS3701)

Exam (elaborations)

COS3701 Assignment 2 [Unique No:830417] 2022

1 review
 103 views  7 purchases

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 .

Preview 2 out of 14  pages

Document information

  • July 5, 2022
  • 14
  • 2021/2022
  • Exam (elaborations)
  • Questions & answers

Subjects

Written for

All documents for this subject (44)

1  review

review-writer-avatar

By: donellawalsh99 • 2 year ago

Seller

avatar-seller
MyAssignments

Reviews received

Content preview

For Assistance with other modules
Call or Whatsapp +27682021794
www.myassignments.co.za




COS3701
Assignment 02
2022

Due date
7 July 2022,
11:00 PM

UNIQUE NUMBER:
830417

+27682021794 www.myassignments.co.za [AUTHOR NAME]

, 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

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 EFT, 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 this summary 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 this summary for R250,00. You're not tied to anything after your purchase.

Can Stuvia be trusted?

4.6 stars on Google & Trustpilot (+1000 reviews)

66579 documents were sold in the last 30 days

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

Start selling
R250,00  7x  sold
  • (1)
  Buy now