Description
Question 1[10 points]
Write a regular expression for the set of all strings over the alphabet {a, b}
in which each a is immediately preceded and immediately followed by a b.
Question 2[10 points]
Give an algorithm to decide whether the language accepted by a DFA is
Σ
∗
. Your algorithm description should be high-level and does not need to
go into any details. For example you can say “minimize” or “determinize”
without explaining how these algorithms work.
Question 3[20 points]
One of the following questions is decidable and the other is undecidable.
1. Given a CFL L and a regular language R, is L ∩ R = ∅?
2. Given a CFL L and a regular language R, is L ∩ R = Σ∗
?
For the one that is decidable give an algorithm, for the other give an undecidability proof.
Question 4[15 points]
Consider the language L = a
n
b
mc
n+m with n, m ≥ 0. Classify this as one
of the three following:
1. regular,
2. context-free but not regular,
3. recursive but not context-free.
You have to prove each asssertion. For example, if you say that it is regular,
you must give an NFA to recognize it; of course, in this case it is obvious
that it does not belong to the other two classes. Similarly, if you claim that
it is context-free, but not regular, you have to give a context-free grammar
and a proof that it is not regular, but, of course you will not have to
prove that it is recursive. If you claim that it belongs to the last class, you
must show that it is not context-free (it is then immediate that it is not
regular) and give an algorithm to recognize it.
Final Take-Home Examination COMP 598 2
Question 5[15 points]
The set F IN = {hMi|M halts on finitely many inputs}. Explain why this
set is not decidable [2 points]. Explain why this set is not CE, use a reduction
to some known non-CE set like EMPTY. EMP T Y = {hMi|M never halts on any input}.
[13 points].
Question 6[20 points]
Recall that a set is called cofinite if its complement is finite. Thus if we
are talking about the natural numbers the set of numbers bigger than 17
is cofinite and the set of odd numbers is infinite but not cofinite. For this
question the alphabet is fixed as {a, b}.
1. Is is decidable whether a regular language is cofinite? Assume that
the regular language is defined by giving you its recognizing DFA.
2. Is it decidable whether a context-free language is cofinite?
3. Is it decidable whether a language described by a Turing machine is
cofinite?
Please give short answers. Long answers will be penalized even if they are
correct. You may invoke known theorems from the class, but not random
theorems that you found on the internet.
Question 7[10 points]
Are the following statements true or false? No explanations are needed.
1. The intersection of two context-free languages can be regular.
2. The intersection of two context-free languages must be recursive.
3. Given G1 and G2 context-free grammars, it is undecidable whether
L(G1) ⊂ L(G2).
4. It is decidable whether a regular language is equal to Σ∗
.
5. All programs written in Python are guaranteed to halt.
