Determine and prove whether each of the following languages is Context Free or not.
a. {0i1j | j = i2}.
b. The complement of {(0n1n)m | m,n > 0}.
c. {0i1i0j1j}, i,j > 0.
d. {0i1i0j1i}, i,j > 0.
e. The complement of {0i1i2i | i > 0}
2. Decision Algorithms
Describe algorithms to solve the problems below.
a. Does a given Deterministic Pushdown Automata generate (0+1)*?
b. Given a CFG and a string z in its language, does the string have 2 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.)
3. Closure Problems
a. Show that the intersection of a regular language and a CFL must be a CFL (i.e. CFL's are closed under intersection with regular sets). You can use an example to clarify your idea.
b. Show that the intersection of a regular language and a CFL is not necessarily regular (though it must be a CFL - see last problem). Hint: Consider the two sets {01n01n0} and {01n01m0}, and prove that the first one is not regular but is context free.
4. Parsing and the CYK Decision Algorithm
a. Exhibit the table you get by doing the CYK algorithm on the strings 00000 and 000000 for the grammar below.S --> AB | BC A --> BA | 0
B --> CC | 1 C --> AB | 0b. Write a NPDA that accepts exactly what the grammar above generates.
5. More Closure
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.
6.. Extra Credit:
Show that if every subset of a set is a CFL, then the set must be regular. (Hint: You can use the pumping lemma to prove that the set must be finite).7. Turing Machine Design - Make sure to comment your program explaining your idea.
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 $ inbetween. That is, it turns x into x$x.
c. Design a TM to
accept strings of the form ww. Use the copy routine from (b) if
you
think it will help.
8. Decidability Problems
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 2 CFG's are equal, is undecidable. Hint: Show that if you could solve this problem then you could also solve another problem that you know is undecidable. That is, reduce this to an undecidable problem.
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.
d. For each of the following undecidable problems determine whether the problem or its complement is partially decidable.
The language of all TM’s that accept nothing.
The language of all TM’s that accept everything.
The language of all TM’s that accept Regular sets.