CSC 384 - Theory of Computation

Professor Simonson

Assignment 4 (40 points)

Due: Last Day of Class

1. Context Free or Not (6 points)

Determine and prove whether each of the following languages is Context Free or not.
a. {0ⁱ1^j| j = i²}.
b. The complement of {(0ⁿ1ⁿ)^m | m,n > 0}.
Hint: Use non-determinism. The set {(0ⁿ1ⁿ)^m | m,n > 0} is not context free, and since DCFLs are closed under complement, if the complement of {(0ⁿ1ⁿ)^m | m,n > 0} is context free it must be non-deterministic.
c. {0ⁱ1ⁱ0^j1^j}, i,j > 0.
d. {0ⁱ1ⁱ0^j1ⁱ}, i,j > 0. Hint: Note that the intersection of {0ⁱ1ⁱ0^j1ⁱ} and 0*1*01* = {0ⁱ1ⁱ01ⁱ}.
e. The complement of {0ⁱ1ⁱ2ⁱ| i > 0}. Use non-determinism.
f. {0ⁱ1^j0^j1ⁱ}, i,j > 0.

2. Not Context Free but Satisfies Pumping Lemma (2 points)

The set of strings 0ⁿ1^m2^p where p < min(m,n) is not context free, and neither is 0ⁿ1^m2^p where p > max(m,n). The pumping lemma is not powerful enough to prove this, because both these sets happen to satisfy the pumping lemma even though they are not context free. Choose either set and prove that it satisfies the pumping lemma. That is, show that for any string z in the set that is longer than k symbols, you can always partition z into 5 parts z=uvwxy, where vwx has no more than k symbols, vx is not empty, and uvⁱwxⁱy is also a string in the set, for every i >= 0.

(Notice that we usually use the pumping lemma to prove that a set does not have the pumping property. Here you show that the set has the pumping property. So now, the roles are reversed. Your opponent picks any string, and you choose the way to partition it, your opponent pumps it as much as they want to, and you show it is still in the language.)

3.   Regular or Context Free (4 points)

        Let L = 0*, M = (0+1)*, and E = (0ⁿ1ⁿ) for n >0. Prove that each of the following concatenation of sets is context free. Determine and prove whether or not each is regular.

                a. LE
                b. EM
                c. LEM

4. Decision Algorithms (2 points)

Describe algorithms to solve the problems below.

a. Does a given Deterministic Pushdown Automata generate (0+1)*? (Hint: Consider the complement of the machine).
Note that in class we proved that the same problem for a non-deterministic machine is undecidable.
b. Given a CFG and a string z in its language, does the string have at least two distinct derivation trees? (Note: your algorithm does not test whether or not the grammar is ambiguous! For that you would have to test every string.)

5. Closure Problems (2 points)

The intersection of a regular language and a CFL must be a CFL (i.e. CFL's are closed under intersection with regular sets).

a. Give an example of two CFL's whose intersection is not a CFL.

b. Give an example of two non-regular CFL's whose union and intersection is regular.

6. More Closure (2 points)

Let L be some regular set in which all strings happen to have length divisible by 3, and let's define Twist3(L) to be the set of all strings in L where every 3 symbols are reversed. For example if L = {011, 011011, 101100111 ...} then Twist3(L) = {110, 110110, 101001111 ...}.
Explain how to build a PDA for Twist3(L) given an FSM for L. Use an example to clarify your idea.

7. Turing Machine Design (6 points)
Make sure to include comments explaining your idea. For convenience, you may assume that the tape has a $ symbol on the left end of the input.

        a. Design a Turing Machine program to take a binary integer n as input, and replace it with the binary string with value n+1.
        b. Design a TM subroutine which takes a binary string and copies it to the right of the input with a $ in between. That is, it turns x into x$x.
        c. Design a TM to accept strings of the form ww.

8. Decidability Problems (10 points)

a. Prove that the PCP problem is decidable for strings over the alphabet {0}.
b. Prove that the problem of determining if the languages generated by two CFG's are equal, is undecidable. Hint: Reduce from the undecidable problem of whether the language of a CFG equals everything.
c. Consider the language of all TM’s that given no input eventually write a non-blank symbol on their tapes. Explain why this set is decidable.
That is, explain how to answer the question: Given a TM and a blank tape, whether or not it ever prints a non-blank symbol.
Hint: Consider the configurations of the TM. The number of configurations for such a TM is finite.
d. Prove that the language of all TM's that accept Regular sets is undecidable. That is, the question: whether or not the language accepted by a given TM is regular, is undecidable.
     Hint: Reduce from the Halting problem where you are given a machine M and an input x. Have the transformed program M' ignore its input and run M on x. If M halts on x, then M' reads its input w and accepts iff the input w is 0ⁿ1ⁿ. This is a special case of Rice's Theorem.
e.   For each of the following undecidable problems determine whether the problem is partially decidable and/or whether its complement is partially decidable.
    i. Does a given TM accept nothing.
    ii. Does a given TM accept everything.
   iii. Is the set of strings accepted by a given TM regular?

9. Reductions (6 points) - In the Book

The Dominating Set problem gives an undirected graph G and an integer k, and it asks whether or not there is a set of k or fewer nodes in G such that every node not in the set is adjacent to some node in the set.
Dominating Set is just like Vertex Cover, except that your set of nodes is covering nodes instead of edges. Notice that it generally takes fewer nodes to form a dominating set in comparison to a vertex cover.

        a. Page 195: 7, 9.
            Hints: For 7: Consider the nodes not in the vertex cover. For 9: Add "dummy" nodes to pad the domination and reduce from the Dominating Set problem.

        b. Reduce the Vertex Cover problem to the Dominating Set problem.

Extra Credit:

Show that if every subset of a set is a CFL, then the set must be regular. Hint: Use the pumping lemma to prove that the set must be finite.

back

shai@stonehill.edu