xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

程序代写案例-COMP4141-Assignment 3

时间：2021-04-02

COMP4141 Assignment 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)

2

学霸联盟

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)

2

学霸联盟