Final Examination COMP 330
Question 1 [15 points]
Classify the following language as either
- regular or
- context-free but not regular or 3. decidable but not context-free
You must prove your answer as explained below.
19th-22nd April 2021
L consists of even length non-empty strings 1 over the alphabet {a, b}, so every word in L can be written as w1w2 with |w1| = |w2| (i.e. w1 and w2 have the same length); we require that w1 starts with a and w2 starts with b. Here are some examples of words in L: aaabaa, abbb, aababbaa, ab.
If you think it is regular it is sufficient to give an NFA2. If you think that it is context-free but not regular you have to give a PDA or CFG and a pumping lemma proof that it is not regular; you do not have to prove that your CFG or PDA is correct but the description should be clear. For the last case you need to give a pumping lemma proof that it is not context-free as well as an algorithm for deciding whether a given string is in the language.
Question 2 [15 points]
Suppose that I am given two regular languages R1 and R2 from the same fixed two-letter alphabet. Describe in outline how you would algorithmically test whether R1 ⊆ R2. You can assume that you are given explicit descriptions of DFA’s to recognize the languages. You have to describe in outline the steps you could take to answer the question. The algorithm has to work without any special assumptions about the languages beyond the fact that they are regular. Your description should be high-level: for example, if you are going to say as some stage that you are testing whether an accept state is reachable from the start state you can just say that, you do not have to give the details of an algorithm to test reachability. Similarly if you want to say that you want to test something about R∗ you need not give an explicit description of how you construct a DFA to recognize R∗. I am not suggesting that either of these steps is part of the required answer; they are just examples.
Question 3 [15 points]
One of the following sets is CE and the other is co-CE. - {M : |L(M)| ≤ 330},
- {M : |L(M)| ≥ 330},
where M is a Turing machine description, L(M) means the language recognized by M and |L(M)|
is the size of this language. Identify which set is CE and which is co-CE and give proofs for both.
1Anyone who asks whether ε is in the language will not be answered. 2I will not answer if you ask me whether a DFA is OK.
1
Final Examination COMP 330 19th-22nd April 2021 There is no credit for guessing, you must give the proofs. You can take it for granted that neither set is decidable.
Question 4 [15 points]
One of the following questions is decidable, the other is undecidable. For the decidable question give an outline of an algorithm to solve it. For the undecidable question give a short proof of undecidability by showing that it is is equivalent to a question that we know to be undecidable. Here R is a regular language and L is a context-free language specified however you prefer and the question in each case is whether the indicated inclusion holds.
•R⊆L • L⊆R
Question 5 [40 points]
Here are 10 multiple-choice questions; each question has 4 choices. In every case, exactly one statement is correct. You must indicate the correct answer. You are not required to give any reasons for your answer. Each question is worth 4 points. Please just write the letter corresponding to your choice for each question. Do not write any explanations.
- The size of the smallest DFA to recognize a regular language R (a) depends on the number of words in R.
(b) depends on whether the empty string is in R.
(c) depends on whether the language is infinite or not.
(d) None of the above. - Consider the DFA shown below.
start q0
bb bb
a
q1
q2
q3
a
a
a
This DFA accepts the language in which there are (a) an even number of a’s and an odd number of b’s (b) an odd number of a’s an even number of b’s
(c) an odd number of a’s and an odd number of b’s
2
Final Examination COMP 330 19th-22nd April 2021 (d) an even number of a’s and an even number of b’s
- The regular expression for the language accepted by the automaton above is
(a) ((aa)∗(bb)∗)∗.
(b) (abba)∗(ba∗b)∗a∗.
(c) it is not possible to write a regular expression for this language.
(d) It is possible to write a regular expression but our angelic professor would never make us do such an awful problem on the final. None of the answers given in (a), (b) or (c) are correct. - The intersection of two deterministic context-free languages (a) can fail to be context free.
(b) must be context free but not necessarily deterministic. (c) must be regular.
(d) can never be context free. - An infinite context-free language
(a) must contain an infinite regular subset.
(b) need not contain any infinite regular subsets.
(c) must never contain an infinite regular subset.
(d) None of the above. - If L1 and L2 are languages over the same alphabet then
(a) it is possible that L1 ∩ L2 is context-free even though neither L1 nor L2 are context free.
(b) if L1 ∩ L2 is context-free then at least one of them must be context free.
(c) if L1 ∩ L2 is context-free then at least one of them must be regular and the other has to be context-free.
(d) if L1 ∩ L2 is context-free then both L1 and L2 must be context free. - We are interested in the question of whether two Turing machines (TM for short) accept any words in common. In symbols: given TM descriptions ⟨M1⟩ and ⟨M2⟩ we want to answer the question L(M1) ∩ L(M2) = ∅? This question is
(a) decidable (computable).
(b) undecidable but computably enumerable (CE).
(c) undecidable but coCE. (d) neither CE nor coCE.
3
Final Examination COMP 330 19th-22nd April 2021
- Consider the set FOO = {⟨M⟩||L(M)| < ∞}. Here we are using our standard notation, ⟨M⟩
means the encoding of a Turing machine. The language FOO defines
(a) the set of Turing machine descriptions that accept only finitely many inputs
(b) the set of Turing machine decriptions that accept all their inputs.
(c) the set of Turing machine descriptions that accept infinitely many different inputs. (d) the set of Turing machines that accept only their own description as input. - The validity problem for first-order logic (FOL) is the following: given a formula φ of FOL we want to know if this formula is true in all interpretations. This problem is
(a) decidable since we can always negate the formula and decide either φ or ¬φ.
(b) undecidable but computably enumerable since we can search through all proofs for a
proof of φ.
(c) not decidable or CE but it is co-CE since we can search for an interpretation that shows
that it is not valid.
(d) Neither CE nor coCE. - The halting problem can be solved by
(a) asking the Internet, which has the answer to all questions.
(b) guessing at random, your answer will be correct with probability greater than zero. (c) using deep learning.
(d) There is no algorithm to solve the halting problem.
4