COS3701 Latest exam pack questions and answers and summarized notes for exam preparation. Updated for October November 2023 exams . For assistance Whats-App.0.6.7..1.7.1..1.7.3.9 . All the best on your exams!!
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
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 EFT, 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 this summary 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 this summary for R50,00. You're not tied to anything after your purchase.
