CS Problem Set 2

NOTE: Each problem set counts 15% of your mark, and it is important to do your own
work. You may consult with others concerning the general approach for solving problems on
assignments, but you must write up all solutions entirely on your own. Copying assignments
is a serious academic offense and will be dealt with accordingly.
DIRECTIONS: For each of the following languages A, determine whether A is semidecidable, and whether A is semidecidable. Justify your answers.
A1 = {hMi | M is a TM and M, starting with a blank tape,
eventually writes a nonblank symbol}
2. Let A2 be the set of all Turing Machine descriptions hMi such that M, during the
computation starting with a blank tape, never attempts to move its head left when its
head is on the left-most tape square. (Here we use the textbook’s convention that the
tape is one-way infinite to the right.)
3. Let A3 be the set of all hMi such that M is a Turing machine and L(M) contains
infinitely many even length palindromes. (Recall that these are strings of the form
wwR, where wR is w written backwards). Here we assume that Σ = {0, 1}.
4. A4 is the set of all hG1, G2i such that G1 and G2 are context-free grammars, and
L(G1) = L(G2).