[SOLVED] comp2022 A3

• This assignment is due in Week 10 and should be submitted to Gradescope.
• All work must be done individually without consulting anyone else’s solutions in accordance with the University’s “Academic Dishonesty and Plagiarism” policies.
• Go to the last page of this document and read the Submission Instructions. For clarifications and updates, monitor “Assignment FAQ”.

• Transition Rules:

0 _ _ L 1 0 * * R 0 1 b _ L 2 2 a _ L 3 1 _ _ * halt_accept 3 _ _ R 0 3 * * L 3 

• (a) (5 marks) State five strings that are in $L(M)$ , and five that are not. The strings should be over Σ.
• (b) (5 marks) Provide a low level description in Morphett notation of a (1 - tape deterministic) Turing Machine for the language that has time complexity at most $5n + 5$ .

• Transition Rules:

0 _ _ * halt-reject 0 a a r 0 0 b b r 0 0 b x l 1 1 x x l 1 1 a x r 2 1 b x r 2 1 _ _ r 4 2 x x r 2 2 a x r 3 2 b x r 3 2 _ _ * halt-reject 3 x x r 3 3 a x l 1 3 b x l 1 3 _ _ * halt-reject 4 x x r 4 4 a a * halt-reject 4 b b * halt-reject 4 _ _ * halt-accept 

• (a) (5 marks) State five strings that are in $L(N)$ , and five that are not. The strings should be over Σ.
• (b) (5 marks) Provide a low level description in Morphett notation of a (1 - tape deterministic) Turing Machine for the language.

For each of the following languages over the input alphabet $sum = {a, b, c}$ , provide a low level description in Morphett notation of a (1 - tape deterministic) TM for the language.

• (a) If the input is a Turing machine $M$ that accepts some input, the output should be any string $x$ that $M$ accepts.
• (b) If the input is a Turing machine $M$ that does not accept any input, the output should be any string $x$ . (There still must be an output, i.e., the machine satisfying this specification must halt.) Prove or disprove whether there exists a Turing Machine that halts on every input and satisfies this specification.

• Problems 1, 2, 3 and 4 are autograded. Ensure submission is formatted correctly for the autograder. An incorrectly formatted submission for a question will receive zero marks for that question. A scaffold will be provided on Ed with the file names the autograder expects.
• Problem 1.1, 2.1 format: The first line of each answer should contain a comma separated sequence of five strings that are in the language, and the second line should contain a comma separated sequence of five strings that are not in the language.
• Problem 1.2, 2.2, 3, 4 format (TMs): All TMs should be deterministic, single - tape, and doubly - infinite. Use Morphett’s format for low - level descriptions. The initial state must be 0. Include an explicit transition to halt - reject when rejecting a string.
• Problem 5 format: Problem 5 is handgraded. Submit a single typed pdf (no pdf containing text as images, no handwriting). Type your student ID at the top of the first page of each pdf. Do not type your name. Do not include a cover page. Submit only your answers to the questions. Do not copy the questions. Your pdf must be readable by Turnitin.