CSE396 Final Exam Answer Key Spring 2016

Open book, open notes, closed neighbors, 170 minutes. The exam has six problems and totals 267
pts., subdivided as shown.

(1) (50 pts.)

Classify each of the following languages L1 , . . . , L10 by whether it is [currently known to be]

(a) regular;

(b) a DCFL but not regular;

m
(c) a CFL but not a DCFL;

er as
co
(d) in P but not a CFL;

eH w
(e) in NP, but not in P unless NP = P.

o.
rs e
(f) decidable, but not in NP unless NP = co-NP.
ou urc
(g) r.e. but not decidable.

(h) not r.e.—i.e., not recognizable.

o
aC s

You need not justify your answers, but brief justifications may help for partial credit–especially with
vi y re

some “close” answers. The languages are:

1. L1 = { hGi : G is a context-free grammar and L(G) 6= ∅ }. Answer: (d) In P but not a CFL;
essentially the complement of ECF G .
ed d

2. L2 = { hGi : G is a context-free grammar and L(G) 6= Σ∗ }. Answer: (g) R.e. but not decidable;
ar stu

essentially the complement of ALLCF G ; is c.e. because ACF G is decidable and one can guess a
string that G doesn’t derive.
sh is

3. L3 = { hφi : The Boolean formula φ is not a tautology }. Answer: (e) In NP and complete since
it is essentially the complement of TAUT, which is equivalent to SAT.
Th

4. L4 = { hN i : N is an NFA and L(N ) = Σ∗ }. Answer: (f) Decidable but not in NP unless

NP = co-NP, since its complement was shown NP-hard on PS10.

5. L5 = { x ∈ { a, b }∗ : #a(x) ≥ #b(x) }. Answer: (b) DCFL but not regular: DCFL because a
DPDA can maintain the count of #a(y) − #b(y) for prefixes y of x by pushing either a or a
character meaning “IOU an a” if the string starts with a b, for instance. Not regular by S = a∗
using “wlog. m < n” given x = am and y = an taking z = bm+1 .

6. L6 = { x ∈ { a, b }∗ : #a(x) − #b(x) is a multiple of 4 }. Answer: (a) Regular since a DFA with

4 states can keep track of the congruences.

7. L7 = { ai bj ak : i 6= k ∨ j 6= k }. Answer: (c) CFL but not a DCFL: CFL since union of two
DCFLs seen in class; not CFL since complement (when intersected with the regular set a∗ b∗ c∗ )
is { an bn cn }—or at least has the same CFL Pumping Lemma proof as seen in class.
https://www.coursehero.com/file/23404690/CSE396S16finalkey/
 8. L8 = { Java programs P : on some input x, P (x) prints “Hello World!” }. Answer: (g) R.e. but
not decidable; transparently equivalent to N ET M .

9. L9 = { Java programs P : for all inputs x, P (x) prints “Hello World!” }. Answer: (h) Not r.e.,
in fact neither r.e. nor co-r.e., since transparently equivalent to ALLT M .

10. L10 = { hM1 , M2 i : M1 and M2 are DFAs and L(M1 ) ∩ L(M2 ) = ∅ }. Answer: (d) In P but not
a CFL: in P via Cartesian product and EDF A algorithm, not a CFL since uses encodings.

(2) 6 × 6 = 36 pts. True/false with justifications. You must write out the word true or false
in full (3 pts.), and then write a brief justification—it need not be a proof (3 pts.).

(a) True/false?: For every DPDA D that does not accept , there is a context-free grammar G in

m
Chomsky normal form such that L(G) = L(D). Answer: True, since every DPDA recognizes a

er as
CFL and every CFL has a grammar in ChNF (with special allowance for  if needed).

co
(b) True/false?: The intersection of two CFLs is always a CFL. Answer: False—e.g. {an bn cn } can

eH w
arise this way.

o.
rs e
(c) True/false?: The generally quickest way to tell if a given string x matches a given regular
ou urc
expression α is to convert α into an equivalent DFA Mα and then run Mα (x). Answer: False
because this can have exponential blowup; better is to convert the regexp to an NFA N as in
class then simulate N (x) directly as on PS10.
o

(d) True/false?: The union of two regular languages is always a DCFL. Answer: True because it is
aC s

regular and every regular language is a DCFL.

vi y re

(e) True/false?: It is possible to write a “version 2.0” of Turing Kit such that whenever the user
draws a DFA M , there is an efficient menu option to tell whether L(M ) = Σ∗ . Answer: True
because EDF A has a polynomial-time (indeed, truly efficient) algorithm.
ed d

(f) True/false?: It is possible to write a “version 3.0” of Turing Kit such that whenever the user
ar stu

draws a deterministic Turing machine M , there is an efficient menu option to tell whether
L(M ) = Σ∗ . Answer: False because ET M is undecidable.
sh is
Th

(3) 11 × 5 = 55 pts. Multiple Choice: Circle clearly the one best answer for each. This time no
justifications are needed, though they could help for partial credit.

1. In a Myhill-Nerode proof that the language L = { a2n b2n : n ≥ 0 } is non-regular, the proof can
begin with:
(a) Take S = a∗ b∗ ;
(b) Take S = (aa)∗ ;
(c) Take S = (bb)∗ ;
(d) Take S = (aa ∪ bb)∗ .

Answer: (b)—anything allowing x = (bb)m and y = (bb)n will fail.

https://www.coursehero.com/file/23404690/CSE396S16finalkey/
 2. In a Myhill-Nerode proof that the same language L = { a2n b2n : n ≥ 0 } is non-regular, suppose
we took S = a∗ instead—this is slightly inferior but workable. Suppose the “adversary” gives
you x = am , y = an where m and n are odd. Then your next step can be:
(a) Take z = bm .
(b) Take z = b2m ;
(c) Take z = abm+1 ; or
(d) Take z = a(bb)m .

Answer: (c) need the extra a to make an even number m + 1 of as.

3. To prove a language B is NP-complete, after first showing B ∈ NP, we could:

(a) Show SAT ≤pm B.
(b) Show TAUT ≤pm B.

m
er as
(c) Show ATM ≤pm B;

co
(d) Show B ≤pm ATM .

eH w
Answer: (a)—the others allow or force B not to be in NP.

o.
rs e
4. The union of two non-regular DCFLs can possibly be:
ou urc
(a) Regular;
(b) A non-regular DCFL;
o

(c) A CFL that is not a DCFL;

aC s

(d) Any of the above.

vi y re

Answer: (d)—D ∪ D̃ = Σ∗ is an example of (a), the complement of {an bn cn } an example of (c).

5. For every language A, the concatenation A∗ A∗ equals:

ed d

(a) (AA)∗ ;
ar stu

(b) Σ∗ ;
(c) A∗ ;
(d) None of the above.
sh is

Answer: (c) The  in A∗ keeps all “singles.”

Th

6. For every language A, the concatenation (A ∪ {}) · (Ã ∪ {}) equals:

(a) AA;
(b) Σ∗ ;
(c) A∗ ;
(d) None of the above.

Answer: (b)—again  allows every word in A and à to pass thru.

7. If M1 , M2 , and M3 are DFAs with 100 states each, then L(M1 ) ∩ L(M2 ) ∩ L(M3 ) is:
(a) Always empty;
(b) Always recognized by a DFA with 100 states;
https://www.coursehero.com/file/23404690/CSE396S16finalkey/
 (c) Possibly non-regular;
(d) Always regular, but the smallest DFA that recognizes it might need 1 million states.

Answer: (d)—and the limit is reached when L = {x : #a(x), #b(x), #c(x) all ≡ 0 (mod 100)}.

8. In the CFG G = S −→ aS | bS | a | b :
(a) The string abb is ambiguous;
(b) The string aba is ambiguous;
(c) The empty string  is ambiguous;
(d) No string in L(G) is ambiguous.

Answer: (d)—this is the basic unambiguous (“right-linear”) list grammar.

9. The language { hGi : G is a CFG and  ∈ L(G) } is (known to be):

m
er as
(a) In P;

co
(b) NP-complete;

eH w
(c) Equal to {  };

o.
(d) Undecidable.
rs e
ou urc
Answer: (a)—by the same basic algorithm as for ECF G .

10. In a proof that {ai bj ck : i < j < k} is not a CFL, upon being given a “pumping length” p, you
o

can start by taking:

aC s

(a) s = ap bp cp ;
vi y re

(b) s = ap bp+1 cp+2 ;

(c) s = ap b2p c3p ;
(d) Any of the above—they all work.
ed d
ar stu

Answer: (b)—string (a) isn’t in the language and string (c) can’t work when the “adversary”
picks vxy = c.

11. The undecidability of the Halting Problem, noting also the Church-Turing thesis, means that:
sh is

(a) Extraterrestrial civilizations may be able to build computers that can solve it, even though
Th

human beings cannot;

(b) There is no program that solves every given instance of the Halting Problem with a yes/no
answer;
(c) Human beings should not even bother to try to solve any instances of the Halting Problem;
(d) Turing machines are too weak a model of computation to solve it; random-access machines
or quantum computers are needed to solve it.

Answer: (b)—not (a) since the Church-Turing thesis is “universal”; not (c) since projects to
solve tough halting problems have succeeded; not (d) because those models are equivalent to
TMs in computability.

https://www.coursehero.com/file/23404690/CSE396S16finalkey/
 (4) (39 pts.)
A person who likes to keep poSitive and N egative values separate once wrote the following context-
free grammar G = (V, Σ, R, S) with V = { N, S } and rules:

S −→ S + S | N + S | S − (N ) | 0 | 1
N −→ −(S) | (N − S)

(a) Give a derivation tree for the string 1+0-(-(1+1)) . (6 pts.)

(b) Is it true that for every x ∈ L(G), the substring +- does not occur in x? If so, prove it by
structural induction; if not, demonstrate the existence of strings in L(G) that do have this
substring.
(c) Same question as (b) for the substring -- .

m
(d) A hint: at least one of your answers in (b,c) will be “no”—that is, the substring can occur. But

er as
it is possible to change one rule in R such that neither substring can occur, in any x ∈ L(G),

co
and without using more than one pair of parentheses in any rule. Make the change to obtain a

eH w
new grammar G0 , and then prove this fact about your G0 .

o.
rs e
Important Note: You may and should make liberal but reasonable use of the phrase “This case is
ou urc
similar to a previous one” in order to shorten the proof(s). Parts (b)–(d) total 33 pts., but saying how
they are subdivided would give too much away.
o

Answer: (a) The tree has S =⇒ S − (N ) at the root. The N derives −(S), which shows how the
leading - sign can come in. The two S-es then derive 1+0 and 1+1, respectively.
aC s
vi y re

(b) It can occur: S =⇒ S + S =⇒ S + N + S =⇒ S + −(S) + S and so on.

(c) This can occur too: S =⇒ N +S =⇒ (N −S)+S =⇒ (N −N +S)+S =⇒ (N −−(S)+S)+S. . .
(d) The two main ways were to change N → −(S) into N → (−S) or to add parens around the
ed d

right-hand side N + S (or just around the N ). The latter main one gives this G0 :
ar stu

S −→ S + S | (N + S) | S − (N ) | 0 | 1
N −→ −(S) | (N − S)
sh is
Th

With reference to the new grammar, define:

• PS = “Every x I derive has no +- or -- and begins and ends with a parenthesis or constant.”
• PN = “Every y I derive has no +- or -- and ends with a parenthesis.” (Notes: It does not
matter if you vacuously added, “or constant.” If you did the N → (−S) change instead then
PN ≡ PS . It was also enough to say “. . . does not begin/end with an operator.”)

Doing three rules is (more than) enough to make the picture plain:

• S → (N + S): Suppose S =⇒∗ x utrf. Then x = (y + z) where N =⇒∗ y and S =⇒∗ z. By IH PS

on RHS, z does not begin with -, and by both PS and PN on RHS, neither y nor z has internal
substring issues. This covers all ways +- or -- could possibly occur. That x immediately begins
and ends with parentheses upholds the added clause of PS as well.
https://www.coursehero.com/file/23404690/CSE396S16finalkey/
 • S → S − (N ): Suppose S =⇒∗ x utrf. Then x = y − (z) where S =⇒∗ y and N =⇒∗ z. By IH
PS on RHS, y begins with ‘(’ hence so does x. The other extra point needed is that by PS on
RHS, y cannot end in - or +.

• N → (N − S): Suppose N =⇒ y utrf. Then y = wz where N =⇒∗ w and S =⇒∗ z. By IH

PN on RHS, w ends in ). As before, z does not begin with - (or +)—so any new danger is
averted—and y has external parentheses which upholds the added clause of PN .

This covers all three “danger cases,” and the safety of the other rules is entirely similar.

(5) (15 + 6 + 6 + 24 = 51 pts.)

Let A = { an bn : n ≥ 1 }. Define E to be the language of strings that differ in at most one place

m
from a string in A. An example of a string in E is aaba, since changing the last a to b gives a string

er as
in A. Note that E contains A, and that the strings in E have the same lengths as strings in A. Define

co
G to be the context-free grammar ({ S, T, U }, { a, b }, R, S), where the rules in R are:

eH w
S −→ aSb | aT U | U T b

o.
rs e T −→ aT b | 
ou urc
U −→ a | b.

(a) For each of the following strings, say whether it belongs to E, and if so, give a parse tree or
o

leftmost derivation for it in G: (i) , (ii) bb, (iii) aaabb, (iv) aaaabb.
aC s

(b) Can any string x that begins with b and ends with a belong to E? Justify your answer briefly.
vi y re

(c) If x ∈ E and x = awa or x = bwb for some string w, then what must be true about w?

(d) Prove by induction that E ⊆ L(G). In fact the languages are equal, but you only need to prove
ed d

the containment. Your answers to (b) and (c) may help you simplify the induction.
ar stu

Answer: (a) (i) no,  ∈/ L(G) since every rule for S has a terminal; (ii) yes: S =⇒ U T b =⇒ bT b =⇒
bb; (iii) no: the length is odd; (iv) yes: S =⇒ aSb =⇒ aaSbb =⇒ aaaT U bb =⇒ aaaU bb =⇒ aaaabb.
sh is

(b) No: it requires changing at least those two characters to match the a+ b+ form required for A,
Th

and that is one change too many. [Note that it was incorrect to say that the grammar couldn’t derive
it; we have not yet established that G is comprehensive.]
(c) Since x = awa and x = bwb each use up the one allowed “error,” w must have no more errors:
it must either belong to A or be the empty string.
(d) Prove (∀n)P (n), where P (n) ≡ for each x ∈ {a, b}n , if x ∈ E then S =⇒∗ x. From the answer
to part (c) we see that T drives exactly the strings in A ∪ {} = {an bn : n ≥ 0}. We can use that as
a “lemma” to avoid braiding T into the induction, and since U obviously derives just either a or b,
we can leave it out too. So no “enhanced P 0 (n)”—just go with the old P (n). Note that P (0) holds
vacuously since  ∈/ E, and P (n) is also vacuous for odd n. So we can think of n = 2 as the “real
basis.”
Basis (n = 2): The strings aa, ab, bb all belong to E. We derives bb above and get S =⇒ aT U =⇒
aU =⇒ aa and S =⇒ aT U =⇒ aU =⇒ ab for the other two. So P (2) holds.
https://www.coursehero.com/file/23404690/CSE396S16finalkey/
 Induction (meaningfully n ≥ 4): Assume (IH) the statements P (m) for all m < n (again noting
that P (m) for odd m are vacuous but don’t hurt anything). Let x ∈ E with |x| = n. Then considering
the first and last chars of x we have that for some string w ∈ Σ∗ , |w| = n − 2, either (i) x = awa, (ii)
x = awb, or (iii) x = bwb. Note that x = bwa is ruled out by part (b), and in all cases w 6=  since
n ≥ 4.
Case (i) x = awa: Then w ∈ A ∪ {} by part (c), so by the “lemma” for T , T =⇒∗ w. Then we
build the derivation S =⇒ aT U =⇒∗ awu =⇒ awa = x. So S =⇒∗ x in this case.
Case (ii) x = awb: Then w ∈ E and |w| = n − 2 < n, so P (n − 2) applies inductively to give
S =⇒∗ w. So we build: S =⇒ aSb =⇒∗ awb = x.
Case (iii) x = bwb: Similarly to case (i), we get T =⇒∗ w by part (c) and the “lemma” LT = A∪{}.
So S =⇒ U T b =⇒ bT b =⇒∗ bwb = x.
Since we get S =⇒∗ x in each of three cases that are mutually exhaustive for the language E, we

m
deduce P (n), so (∀n)P (n) follows by strong induction. This shows E ⊆ L(G). [The soundness of

er as
these rules is pretty transparent, so E = L(G) does follow.]

co
eH w
o.
(5’) (36 pts.)

rs e
[Spring 2017: This alternative problem was considered for last year’s exam and is more represen-
ou urc
tative for you.] Let Σ = { a, b }. Consider the following two languages, both of which are nonregular.

A = { x ∈ Σ∗ : #a(x) > #b(x) },

o

B = { x ∈ Σ∗ : #a(x) < #b(x) }.

aC s
vi y re

(a) Give an example of a string z of length 8 such that there is exactly one way to write z = xy
with x ∈ A and y ∈ B. (That is, there is a unique way to break z into a string x that has more
a’s than b’s followed by a string y that has more b’s than a’s. (6 pts.)
ed d

(b) Give an example of a string z of length 8 such that there are 7 different ways to write z = xy
ar stu

with x ∈ A and y ∈ B. (6 pts.)

(c) Let D = A · B. Prove that D is non-regular. (Note: I do not know how to do this with the
version of the “Pumping Lemma” given in the text, but it is possible with a careful Myhill-Nerode
sh is

argument that applies some of the ideas from your answers to (a) and/or (b). 24 pts.)
Th

Answer: (a) z = abbbbaaa = a · bbbbaaa. Also good is abbababa = a · bbababa, but z = abbbbaaa is
intuitively the most extreme case and suggests the proof in part (c).
(b) z = aaaabbbb. Any one of the internal breakpoints works.
(c) Take S = ab+ . Let any x, y ∈ S, x 6= y, be given. Then there are numbers m, n ≥ 1
where wlog. m < n such that x = abm and y = abn . Take z = an−1 (which is well-defined because
n ≥ 1). Then yz = abn an−1 is in A · B—indeed with the unique breakdown shown in part (a). But
xz = abm an−1 ∈ / A · B because n − 1 ≥ m, so no suffix has more b’s than a’s. Thus L(xz) 6= L(yz),
and sinze x, y ∈ S are arbitrary, L is non-regular by the Myhill-Nerode Theorem.

https://www.coursehero.com/file/23404690/CSE396S16finalkey/
 (6) (6 + 24 + 6 = 36 pts.)
Consider the following decision problem:
Instance: A deterministic Turing machine M .
Question: Do there exist strings x, y ∈ Σ∗ such that M accepts x but M does not accept y?

(a) Using set notation, formalize this problem as a language L.

(b) Prove that L is undecidable, by reduction from a known undecidable problem such as AT M or
K.

(c) Is L recognizable? Justify your answer briefly. (A full proof using another reduction is worth 6
pts. exam extra-credit.) End of Exam.

m
er as
Answer: (a) L = { hM i : L(M ) 6= ∅ ∧ L(M ) 6= Σ∗ }.

co
eH w
(b) Given any instance x = hM, wi of the Acceptance Problem, define f (x) to be the code of a TM
M 0 that works as follows on any input y: “Simulate M (w) open-endedly. If and when M (w) halts,

o.
accept y if and only if y 6=  [or, to tie this in to PS10, iff y = 0n 1n for some n ≥ 1].” (If x is not a
rs e
valid code, map it to some TM M0 such that L(M0 ) = ∅ so hM0 i ∈ / L. Or ignore this issue.) Then:
ou urc
hM, wi ∈ AT M ≡ M (w) ↓= 1 L(M 0 ) = (Σ∗ \ {}) (or = {0n 1n })
o

=⇒
L(M 0 ) 6= ∅ ∧ L(M 0 ) 6= Σ∗ =⇒ f (x) = hM 0 i ∈ L;
aC s

=⇒
vi y re

hM, wi ∈
/ AT M =⇒ L(M 0 ) = ∅ =⇒ f (x) = hM 0 i ∈
/ L.

So AT M ≤m L, so L is undecidable. (The only hitch was realizing that the simple “all-or-nothing
switch” fails because it jumps into the “= Σ∗ ” clause. Reductions testing x == w also worked fine.)
ed d
ar stu

(c) L is not recognizable. The intuitive reason is that it still involves checking some kind of “all.”
To prove that L is in fact neither c.e. nor co-c.e., it suffices to show DT M ≤m L. This actually follows
by the solution to PS10, problem (1), as in fact did part (b).
sh is
Th

https://www.coursehero.com/file/23404690/CSE396S16finalkey/

Powered by TCPDF (www.tcpdf.org)