Hello,
I'm excited to share a valuable resource for your COS3701 exam preparation - a merged and easily searchable PDF of Questions and Answers. This tool is especially useful if your exam allows open-book format, as it enables you to quickly navigate and find the information you need.
I pers...
COS3701 exam - Jan 2001
Question 1
(a) Find a CFG for the language consisting of words of odd length over
the alphabet ∑={a,b} that start and end with different letters.
(b) Convert the following CFG to Chomsky Normal Form (CNF):
S 🡪 AA
A 🡪 B | BB
B 🡪 abB | b | bb
Question 2
Draw a deterministic PDA that accepts the language
L = { (ba) (ab) | n 0 } over the alphabet ∑={a,b}
Question 3
The pumping lemma with length for context-free languages (CFLs) can be
stated as follows:
Let L be a CFL generated by a CFG in CNF with p live productions. Then
any word w in L with length(w) > 2 can be broken into 5 parts:
w = uvxyz
such that
length(vxy) ≤ 2
length(x) > 0
length(v) + length(y) > 0
and such that all words uvⁿxyⁿz with n {2,3,4,…} are also in the
language L.
Use the pumping lemma with length to prove that the language
L = { a b a b | n, m = 1, 2, 3...}
over the alphabet ∑={a,b} is NOT context-free.
Question 4
Give an informal justification by means of grammars to show that the
context-free languages are closed under product.
Question 5
Draw a TM that accepts all words ending in aaa, crashes on all words
ending in baa, and loops on all other words over the alphabet Σ = {a,
b}.
Question 6
Consider the non-context-free language L over the alphabet Σ = {a, b},
which is defined as
L = { a b a | n = 1, 2, 3...}
(i) Explain in words how you would build a 2PDA that accepts the
language L. Do NOT draw a machine.
,(ii) Can you build a 3PDA that accepts L? Justify your answer without
attempting to give a 3PDA or an algorithm.
(iii) Can you build a TM that accepts L? Justify your answer without
attempting to give a TM or an algorithm.
(iv) Can you build a PDA that accepts L? Justify your answer without
attempting to give a PDA or an algorithm.
Question 7
What are Accept(T), Loop(T), and Reject(T) of the following TM T?
Question 8
a) When is a language regular? Give your answer in terms of
machines.
b) When is a language context-free? Give your answer in terms of
machines.
c) When is a language recursively-enumerable? Give your answer in
terms of TMs.
d) When is a language recursive? Give your answer in terms of TMs.
e) Explain the idea of the encoding of a TM.
Question 9
(a) What does it mean for a function to be computable?
(b) Prove that the predecessor function defined by
PREDECESSOR(N) = n - 1 for all n ≥ 1
is computable. Use unary encoding.
, Solutions
Question 1a
Assuming that the FA is correct, Cohen’s Theorem 21 can be applied,
which results in the following CFG:
S 🡪 aX | bP
X 🡪 aY | bY
Y 🡪 aX | bZ
Z 🡪 aY | bY | /\
P 🡪 aQ | bQ
Q 🡪 aR | bP
R 🡪 aQ | bQ | /\
Question 1b
Step 1 - Kill all /\ productions:
There are no /\ productions, so none of the non-terminals is nullable.
The CFG remains unchanged.
Step 2 - Kill all unit productions:
The only unit production is A 🡪 B, where the B can be replaced with
all B’s non-unit productions (i.e. all of them).
The new CFG, without unit productions, is:
S 🡪 AA
A 🡪 BB | abB | b | bb
B 🡪 abB | b | bb
Step 3 - Replace all mixed strings with solid nonterminals.
, Create extra productions that produce one terminal, when doing the
replacement.
The new CFG, with a RHS consisting of only solid nonterminals or one
terminal is:
S 🡪 AA
A 🡪 BB | XYB | b | YY
B 🡪 XYB | b | YY
X 🡪 a
Y 🡪 b
Step 4 - Shorten the strings of nonterminals to length 2.
Create new, intermediate nonterminals to accomplish this.
The new CFG, in CNF is:
S 🡪 AA
A 🡪 BB | RB | b | YY
B 🡪 RB | b | YY
R 🡪 XY
X 🡪 a
Y 🡪 b
Question 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 ExamMasteryHub. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $20.56. You're not tied to anything after your purchase.
