Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
COMP4141 Assignment
Due: Monday, 12th April, 12:00 (AEST) Submission is through WebCMS/give and should be a single pdf file, maximum size 2Mb. Prose should be typed, not handwritten. Use of LATEX is encouraged, but not required. Discussion of assignment material with others is permitted at a high level, but the work submitted must be your own in line with the University’s plagiarism policy. Problem 1 (10 marks) Suppose we define a deterministic two-stack PDA to be a machine with a finite stack alphabet, a finite set of control states, and two stacks. Such a machine is initialised by loading the input into one of the stacks (backwards, so that the left of the word sits at the top of the stack), and starting the machine in its initial state. It then computes at each step of computation reading the top of the two stacks, and deterministically performing a push or pop onto each of the stacks, and changing the control state. The machine has an accept and a reject state. Show that two-stack PDA’s are equivalent to Turing machines: a language L is accepted by some two-stack PDA iff it is accepted by some deterministic Turing Machine. Problem 2 (10 marks) Let Σ1 and Σ2 be disjoint sets. Say that a language L ⊆ Σ∗1 is decidably verifiable if there is a decidable language L′ ⊆ Σ∗1 × Σ∗2 such that L = {w : there exists c ∈ Σ∗2 such that (w, c) ∈ L′} (‡) (a) Show that if L is recursively enumerable, then it is decidably verifiable. (4 marks) (b) Show that if L is decidably verifiable, then it is recursively enumerable. (6 marks) Observation This is the “computable” analogue of the (polynomially) verifiable classification of NP. It is also worth noting the similarity with Problem 5 in Assignment 2: using the notation from that problem, condition (‡) can also be expressed as L = L′ ÷ Σ∗2 . Problem 3 (10 marks) Is the following language decidable, recursively enumerable but not decidable, or not recursively enumer- able? Justify your answer. Return to start Input: A Turing Machine M Question: Is there an input which will make M return to its start state? 1 Remark Partial marks can be obtained for a suboptimal answer (e.g. showing the problem is recursively enumerable without determining if it is decidable) Problem 4 (10 marks) Is the following language decidable, recursively enumerable but not decidable, or not recursively enumer- able? Justify your answer. NETM Input: A Turing Machine M Question: Is |L(M)| ≤ 1? Remark Partial marks can be obtained for a suboptimal answer (e.g. showing the problem is recursively enumerable without determining if it is decidable) Problem 5∗ (10 marks) Is the following language decidable, recursively enumerable but not decidable, or not recursively enumer- able? Justify your answer. SingletonTM Input: A Turing Machine M Question: Is |L(M)| = 1? Remark Partial marks can be obtained for a suboptimal answer (e.g. showing the problem is recursively enumerable without determining if it is decidable) 3 (Part B) 2021 Term 1 Due: Monday, 12th April, 12:00 (AEST) Submission is through WebCMS/give and should be a single pdf file, maximum size 2Mb. Prose should be typed, not handwritten. Use of LATEX is encouraged, but not required. Discussion of assignment material with others is permitted at a high level, but the work submitted must be your own in line with the University’s plagiarism policy. Problem 1 (10 marks) Suppose we define a deterministic two-stack PDA to be a machine with a finite stack alphabet, a finite set of control states, and two stacks. Such a machine is initialised by loading the input into one of the stacks (backwards, so that the left of the word sits at the top of the stack), and starting the machine in its initial state. It then computes at each step of computation reading the top of the two stacks, and deterministically performing a push or pop onto each of the stacks, and changing the control state. The machine has an accept and a reject state. Show that two-stack PDA’s are equivalent to Turing machines: a language L is accepted by some two-stack PDA iff it is accepted by some deterministic Turing Machine. Problem 2 (10 marks) Let Σ1 and Σ2 be disjoint sets. Say that a language L ⊆ Σ∗1 is decidably verifiable if there is a decidable language L′ ⊆ Σ∗1 × Σ∗2 such that L = {w : there exists c ∈ Σ∗2 such that (w, c) ∈ L′} (‡) (a) Show that if L is recursively enumerable, then it is decidably verifiable. (4 marks) (b) Show that if L is decidably verifiable, then it is recursively enumerable. (6 marks) Observation This is the “computable” analogue of the (polynomially) verifiable classification of NP. It is also worth noting the similarity with Problem 5 in Assignment 2: using the notation from that problem, condition (‡) can also be expressed as L = L′ ÷ Σ∗2 . Problem 3 (10 marks) Is the following language decidable, recursively enumerable but not decidable, or not recursively enumer- able? Justify your answer. Return to start Input: A Turing Machine M Question: Is there an input which will make M return to its start state? 1 Remark Partial marks can be obtained for a suboptimal answer (e.g. showing the problem is recursively enumerable without determining if it is decidable) Problem 4 (10 marks) Is the following language decidable, recursively enumerable but not decidable, or not recursively enumer- able? Justify your answer. NETM Input: A Turing Machine M Question: Is |L(M)| ≤ 1? Remark Partial marks can be obtained for a suboptimal answer (e.g. showing the problem is recursively enumerable without determining if it is decidable) Problem 5∗ (10 marks) Is the following language decidable, recursively enumerable but not decidable, or not recursively enumer- able? Justify your answer. SingletonTM Input: A Turing Machine M Question: Is |L(M)| = 1? Remark Partial marks can be obtained for a suboptimal answer (e.g. showing the problem is recursively enumerable without determining if it is decidable)