CS3331 – Assignment 3
due Nov. 26, 2024
2-day no-penalty extension until: Nov. 28, 11:59pm
1. (30pt) Construct a deterministic Turing machine M that, given as input a string w ∈ {0, 1}∗, if |w|
is even, then M does nothing, otherwise M finds and flips the middle letter of w. Here are some
examples of M ’s behaviour:
(s,) `∗M (h,); (s,0) `∗M (h,1); (s,110) `∗M (h,100); (s,0101) `∗M (h,0101).
Describe M in details using a directed graph whose edges are labelled by transitions (such as the
one in Example 17.2, p. 268 of textbook).
2. (20pt) Prove that the following languages are in D (if you need to define TMs, then clear English
description is sufficient):
(a) L = {| || > 10}.
(b) L = {|M accepts at least three strings starting with a within 10 steps}.
(c) L = {|M does not halt on w within |w| steps}.
(d) L = {|M1 halts on w before M2 does, within |w| steps}.
3. (30pt) Consider the prefix operation, pref(L) = {w ∈ Σ∗ | u = wv, for some u ∈ L, v ∈ Σ∗}.
(a) Is D closed under the prefix operation? Prove your answer.
(b) Is SD closed under the prefix operation? Prove your answer.
4. (20pt) Which of the properties below are true? Prove your answers.
(a) Any semidecidable language is a subset of a regular language.
(b) Any non-semidecidable language is a proper subset of a regular language.
(c) The intersection between a non-semidecidable language and a regular one is non-semidecidable.
(d) The union between a non-semidecidable language and a regular one is non-semidecidable.
Notes: !!! Submit your solution as a single pdf file; anything else receives 0pt. Solutions should
be typed but high-quality hand-written solutions are acceptable.
JFLAP: You are allowed to use JFLAP to help you solve the assignment. You still need to explain
clearly your solution. Also, make sure you understand what it does; JFLAP will not be available
during exams!
LLMs: You are allowed to use LLMs (Large Language Models), such as ChatGPT, but, again,
they will not be available during exams.
LATEX: For those interested, the best program for scientific writing is LATEX. It is far superior to
all the other programs, it is free, and you can start using it in minutes; here is an introduction:
https://tobi.oetiker.ch/lshort/lshort.pdf. It is also available online at https://www.overleaf.com/.