100% satisfaction guarantee Immediately available after payment Both online and in PDF No strings attached
logo-home
COS3701 EXAM PACK 2023 $2.85   Add to cart

Exam (elaborations)

COS3701 EXAM PACK 2023

 21 views  1 purchase
  • Course
  • Institution
  • Book

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!!

Last document update: 1 year ago

Preview 3 out of 351  pages

  • November 10, 2021
  • October 15, 2023
  • 351
  • 2022/2023
  • Exam (elaborations)
  • Questions & answers
avatar-seller
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

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 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 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.85. You're not tied to anything after your purchase.

Can Stuvia be trusted?

4.6 stars on Google & Trustpilot (+1000 reviews)

62491 documents were sold in the last 30 days

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

Start selling
$2.85  1x  sold
  • (0)
  Add to cart