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
