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.
1.
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).
1

TAKE ADVANTAGE OF OUR PROMOTIONAL DISCOUNT DISPLAYED ON THE WEBSITE AND GET A DISCOUNT FOR YOUR PAPER NOW!

Unlike most other websites we deliver what we promise;

  • Our Support Staff are online 24/7
  • Our Writers are available 24/7
  • Most Urgent order is delivered with 6 Hrs
  • 100% Original Assignment Plagiarism report can be sent to you upon request.

GET 15 % DISCOUNT TODAY use the discount code PAPER15 at the order form.

Type of paper Academic level Subject area
Number of pages Paper urgency Cost per page:
 Total: