Exam (elaborations)
COS3701 Assignment 2 Yearly Module 2022 (Unique Number: 830417)
- Course
- Institution
COS3701 Assignment 2 Yearly Module 2022
[Show more]
Seller
Follow
t0dd
Reviews received
Content preview
UnisaAssignHelpCOS3701
Assignment 2
Unique Number:
830417
, UnisaAssignHelp
Question 1
Build a DPDA to show that the language L = {(ab)naaa(ba)n−2 | n > 2} 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 three instances of ab (but do nothing to the stack). These are the leading abs that we can simply
get rid of because we know there should be exactly three of them.
2. Read in any other instances of ab and for each such instance push an X onto the stack. Here we are
essentially counting how many abs we have.
3. Read in aaa (but do nothing to the stack)
4. 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.
5. When a ∆ is popped from the stack then we know we have just read the ba that matches the three
abs that must be at the start of every string.
6. When the stack is empty then the DPDA must check that all of the bas have been read (ie there is no
additional input).
We can now build a PDA to do this.
The PDA is shown in Figure 1.
2
, UnisaAssignHelp
Figure 1: A DPDA to recognise L = {(ab)naaa(ba)n−2 | n > 2}
The six phases outlined above can be seen quite easily in the layout of the PDA.
3
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 t0dd. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $5.84. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
83430 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now