CS3331: Foundations of Computer Science – Fall 2020

– Final Exam –

1. (20pt) Remember to solve only your version Vi ; calculate correctly your i = student number mod 4.

Construct a deterministic Turing machine M that performs the action indicated at your Vi below. M starts with the initial configuration (s,  w) and halts with the configuration (h,  w). Describe M using the macro language (the one that looks like this: R ,a −→  aRbL¬ ).

V0 : Σ = {a, b}; M replaces any occurrence of aba in the input with aca.

V1 : Σ = {0, 1}; M adds 2 to its input, seen as a binary number.

V2 : Σ = {a, b}; M moves the leftmost a (if any) to the end of the input, then closes the hole where a was.

V3 : Σ = {a, b, c}; M replaces the input with the number of a’s in the input, written in unary (using 1’s).

2. (20pt) Describe in clear English a Turing machine that semidecides the language L given below:

V0 : L = {<M> | M rejects at least two strings}

V1 : L = {<M> | M accepts at least one string starting with a}

V2 : L = {<M> | M accepts the empty string and at least one string of odd length}

V3 : L = {<M> | M accepts at least two strings of different lengths}

3. (20pt) Prove your answers to the questions below ((a) – 6pt, (b) – 5pt, (c) – 9pt: 3pt for each (i)-(iii)):

V0 : (a) Is it possible that L ∈ D and L ∩ ¬L 6∈ SD − D?

(b) If we modify an FSM to allow infinitely many states, then we can easily accept any language, e.g., we can build a path to accept every string in the language. That means, we can accept also non-SD languages. Does this contradict Church’s thesis?

(c) Can the union L1 ∪ L2, for L1 ∈ SD, L2 ∈ ¬SD be in: (i) D, (ii) SD − D, (iii) ¬SD?

V1 : (a) Is it possible that L is regular and ¬(L ∩ ¬L) 6∈ SD − D?

(b) Is it possible to design a new mechanism (that would have a finite description) such that the languages it accepts are precisely the non-SD languages, thus contradicting Church’s thesis?

(c) Can the intersection L1 ∩ L2, for L1 ∈ SD, L2 ∈ ¬SD be in: (i) D, (ii) SD − D, (iii) ¬SD?

V2 : (a) Is it possible that L is context-free and L − ¬¬L 6∈ SD − D?

(b) Is it possible to define a new mechanism that uses a Turing Machine but accepts exactly when the TM does not; such a mechanism would then accept languages such as ¬H, which is not in SD, thus contradicting Church’s thesis?

(c) Can the difference L1 − L2, for L1 ∈ SD, L2 ∈ ¬SD be in: (i) D, (ii) SD − D, (iii) ¬SD?

V3 : (a) Is it possible that L 6∈ SD and L ∪ ¬L ∈ D?

(b) Let’s define a new class of languages, which is obtained as the closure of SD under complement. This new class would strictly include SD, as it would include, for instance, ¬H. Does this contradict Church’s thesis?

(c) Can the intersection L1 ∩ L2, for L1 ∈ ¬SD, L2 ∈ SD be in: (i) D, (ii) SD − D, (iii) ¬SD?

4. (30pt) Consider an alphabet Σ such that all languages below are over Σ.

(i) (18pt) For each of the languages below, prove, without using Rice’s theorem, whether it is in D, SD − D, or ¬SD. Explain first intuitively why you think it is in D, SD − D, or ¬SD, then prove your assertion rigorously.

(ii) (12pt) Explain whether Rice’s Theorem applies or not to each of these languages.

V0 : (a) L1 = {<M1, M2> | M1 accepts at least two strings and M2 rejects at least one string}

(b) L2 = {<M> | M accepts only the string aba}

(c) L3 = a ∗

V1 : (a) L1 = {<M1, M2> | M1 accepts at least one string in a ∗ and M2 rejects at least one string in b ∗}

(b) L2 = {<M> | |L(M)| ≤ 10}

(c) L3 = {ε}

V2 : (a) L1 = {<M1, M2> | M1 accepts a and L(M2) is not empty}

(b) L2 = {<M> | M accepts finitely many even-length strings}

(c) L3 = ∅

V3 : (a) L1 = {<M1, M2> | M1 accepts at least one string and M2 rejects at least one string}

(b) L2 = {<M> | M accepts two palindromes and nothing else}

(c) L3 = {ab}

5. (10pt) Answer your version of the PCP question below:

V0 : PCP over one letter (that is, all strings are from 1∗ ) is decidable, because we work with numbers instead of strings. If PCP over one letter is decidable, and we can always encode any number of letters into a single letter (e.g., a = 1, b = 11, c = 111, d = 1111, etc.), explain how is it possible that PCP over an arbitrary alphabet is undecidable?

V1 : Explain what is wrong with the following proof that PCP is decidable. Denote the top and bottom strings by (x1, x2, . . . , xn) and (y1, y2, . . . , yn), resp. Considering all possible subsets of all possible per-mutations of these blocks, we obtain 2n! possibilities. If we denote the maximum length of a string by m = maxi=1..n(max(|xi |, |yi |)), this means the shortest solution, if any, must be of length at most m2 n! . The PCP is then decided by checking all potential solutions up to this length.

V2 : Show that the following restricted version of PCP is decidable: PCPr = {((x1, x2, . . . , xn),(y1, y2, . . . , yn)) | n ≥ 1, xi , yi ∈ {a, b} +, max(|xi |, |yi |) ≤ 4, for all 1 ≤ i ≤ n}.

V3 : Given a positive number n, construct a PCP problem over {a, b} whose shortest solution has n blocks. Explain why your answer is correct.

CS3331: Foundations of Computer Science – Fall 2021

– Final Exam –

1. (20pt) Consider the context-free language of balanced parentheses of three kinds:

L = {w 2 {(, ), [, ], {, }}* | all parentheses in w are properly balanced} .

Place ¬L correctly in the correct area of the map. Prove your answer.

2. (20pt) Answer the following questions with True or False; prove your answers:

(a) (2pt) Any regular language is context-free.

(b) (2pt) Some context-free languages are regular.

(c) (8pt) Any regular language can be generated by an unambiguous context-free grammar.

(d) (6pt) Any context-free grammar generating a regular language is unambiguous.

(e) (2pt) For any non-semidecidable language L, we have that " 2 L*.

3. (20pt) Consider the following language:

L = {<G1, G2 >| G1, G2 context-free grammars such that L(G1) \ L(G2) = {"}} .

Here is an algorithm that decides L:

1. if " 62 L(G1), then reject

2. if " 62 L(G2), then reject

3. k1 the k-constant in pumping theorem for G1

4. k2 the k-constant in pumping theorem for G2

5. k max(k1, k2)

6. for all w 2 L(G1) − {"} with |w|  k do

7. if w 2 L(G2) then reject

8. for all w 2 L(G2) − {"} with |w|  k do

9. if w 2 L(G1) then reject

10. accept

The main idea of the algorithm is that we can check membership for finitely many strings. Therefore, the difficulty arises in the case when both languages are infinite. We know from pumping theorem that, if a language has strings longer than k, then it has also strings shorter than k (we “pump out” to reduce the length, while staying in the language). The algorithm uses this idea with k the larger of the two individual k’s of each language, to ensure the strings longer than k are long enough for both languages.

Is the above algorithm corect? Explain your answer.

4. (20pt) Consider an alphabet ⌃ such that all languages below are over ⌃. For each of the languages below, prove, without using Rice’s theorem, whether it is in D, SD − D, or ¬SD.

(a) L1 = {<M>| M Turing machine, the complement of L(M) is semidecidable}.

(b) L2 = {<M>| M nondeterministic finite automaton such that, for any nondeterministic finite automaton M' with L(M0 ) = L(M), M has the same number of states as M0 or fewer}.

(For L2, any finite automaton M can be encoded as <M> using any of the methods we studied, for instance, the one for Turing Machines. The way the encoding is done is irrelevant for the question.)

(c) L3 = {<M>| M Turing machine, both L(M) and ¬L(M) are infinite}.

(d) L4 = {<M,w>| on input w, M begins by moving right one square onto w, then it never moves outside w, i.e., outside the |w| tape cells occupied by w at the beginning}.

(All Turing machines are single-tape deterministic.)

5. (20pt) Recall that TILES = {<T >| any finite surface on the plane can be tiled with the tile set T}? (Recall that tiles cannot be rotated or flipped and adjacent sides of joined tiles must have the same colour.)

(a) (6pt) Is the set of tiles below in TILES? Explain your answer.

(b) (6pt) If your answer above is negative, then is it possible to add a single tile that makes the new set (of four tiles) in TILES? Explain your answer.

(c) (2pt) Which of TILES and ¬TILES is harder? No proof is required.

For this question, “harder” means (strictly) higher in the hierarchy: D < SD − D < ¬SD, that is, ¬SD is harder than SD − D, which is harder than D; also, no class is harder than itself.

(d) (6pt) Given a language L such that ¬L is harder than L, is it possible that L is in: (i) D, (ii) SD − D, (iii) ¬SD? Explain your answer. You can use examples studied in class without proof.

CS3331: Foundations of Computer Science – Fall 2023

– Final Exam –

1. (20pt) Consider the language of imbalanced strings of parentheses:

imBal = {w 2 {(, )}⇤ | not all parentheses in w are properly matched} .

Here are some examples of strings in imBal: ), )(, ()(()().

(a) (4pt) Is (()(()()(()(()))(()))(()(()))()(()))(()()(()))(()()) in imBal?

(b) (8pt) Is #imBal$ context-free?

(c) (8pt) Is imBal regular?

For (b) and (c), negative answers require proof, positive answers require only correct construction. That means, you don’t have to formally prove that your grammar or automaton works correctly.

2. (20pt) A grammar is ambiguous if it generates a string with two di↵erent parse trees.

(a) (8pt) Give an example of an ambiguous context-free grammar. Prove your answer.

(b) (12pt) We say that a context-free grammar is increasing if the right-hand side of each production rule has length at least 2. Consider the following language:

Lambig = {<G>| G is an increasing context-free grammar and G is ambiguous} .

The following algorithm attempts to decide Lambig:

1. Input: context-free grammar <G> (encoded as a string)

2. if G is not increasing then reject

3. k the k-constant in pumping theorem for G

4. for all strings w 2 ⌃⇤ of length k or less do

5. if w 2 L(G) then

6. compute all parse trees in G for w

7. if more than one tree is found then accept

8. reject

The reject in step 8 is based on the fact that, for strings in L(G) that are longer than k, we can use the pumping theorem to pump out a pair of substrings in order to obtain a shorter string that is still in L(G), thus eventually reducing the problem to the previous case, of strings shorter than k, which we already checked in steps 4-7 and found no ambiguity involving them.

Is the above algorithm correctly deciding Lambig? Explain your answer briefly but very clearly.

3. (20pt) Given a regular language R and a context-free language C:

(a) (10pt) Can you construct a mapping reduction from R to C?

(b) (10pt) Can you construct a mapping reduction from C to R?

Prove your answers.

4. (20pt) For each of the following languages, prove, without using Rice’s theorem, whether it is (i) in D, (ii) in SD but not in D, (iii) not in SD:

(1) (4pt) L1 = {<M>| {a, b} ✓ L(M)}.

(2) (4pt) L2 = {<M>| L(M) ✓ {a, b}}.

(3) (4pt) L3 = {<M>| L(M) − {a, b} is infinite}.

(4) (4pt) L4 = {<M>| L(M) \ {a, b} is finite}.

(5) (4pt) L5 = {a, b}.

5. (20pt) Consider a generalization of the Post Correspondence Problem, where blocks contain strings from given SD languages. An instance of this problem is:

PCP(Ltop, Lbot) = {u v | u 2 Ltop, v 2 Lbot},

for some Ltop, Lbot 2 SD. A solution is defined as usual, as a finite concatenation of blocks such that the strings on the top and on the bottom are the same.

(a) (8pt) Consider L1 = {w 2 {a, b}⇤ | w = ", |w| even }, L2 = {w 2 {a, b}⇤ | |w| odd}. Some examples of blocks from PCP(L1, L2) are: ab a, aabb bab, aa bbbbb. Does PCP(L1, L2) have a solution?

(b) (12pt) Consider the language corresponding to the generalized PCP:

PCPSD = {<Mtop,Mbot >| Mtop,Mbot are Turing machines and PCP(L(Mtop), L(Mbot)) has a solution} .

Is PCPSD semidecidable? Prove your answer.