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 A) 2021 Term 1

Due: Monday, 12th April, 12:00 (AEST)

Submission is through WebCMS/give and should consist of up to three text files: TM1.txt,

TM2.txt, and TM3.txt. Each text file should define a Turing Machine, using the syntax of

http://morphett.info/turing/turing.html, maximum size 1Mb each. Submissions will be automarked

and feedback provided immediately.

Note

You can test the output of a single Turing Machine by submitting a single file, but your final

submission should consist of all machines you have defined, in separate files.

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 (25 marks)

Recall from Assignment 2 the definition of the function bin : {0, 1}∗ → N that treats a word of {0, 1}∗

as the binary representation of a non-negative integer, with the last symbol being the least-significant. So

bin(110) = bin(00110) = 6 and bin(e) = 0.

Design a Turing Machine, TM1, that decides the following language:

{x#y#z : x, y, z ∈ {0, 1}∗ and bin(x) + bin(y) = bin(z)}

Sample inputs and expected outputs

Input Expected output Comments

1#1#10 Accept 1 + 1 = 2

1000#0101#1101 Accept Simple addition

100010#101#100111 Accept Alignment check

101010#10#101100 Accept Simple carry

101010#1010#110100 Accept Simple carry

101010#1111#111001 Accept Advanced carry

#101#101 Accept Syntax corner case

101##101 Accept Syntax corner case

1000#0101#1001 Reject Addition error

1111#0101#1010 Reject Addition error

1001#1001 Reject Syntax error

1001#1001#100010# Reject Syntax error

#1001#1001#100010 Reject Syntax error

1

Problem 2 (10 marks)

Design a Turing Machine, TM2, that decides the following language:

{02n : n ∈N}

Sample inputs and expected outputs

Input Expected output

e Reject

0 Accept

00 Accept

000 Reject

0000 Accept

Problem 3 (15 marks)

Consider the following variant of the grammar used in Assignment 2, given by G = (V,Σ, R, E) where

• V = {E,K, I}

• Σ = {+, &, !, 0, 1, a, b, c, d, e, f}

• R consists of the rules:

E → +EE | &EE | !E | K | I

K → 0 | 1

I → a | b | c | d | e | f

G is the grammar that defines Boolean expressions over the variables Var = {a, b, c, d, e, f}, in Polish

Notation, where:

• + represents ∨ (OR)

• & represents ∧ (AND)

• ! represents ¬ (NOT)

• 0 represents false, and

• 1 represents true

For example !&&a!1+0b corresponds to the Boolean expression ¬((a∧ ¬true) ∧ (false∨ b)).

Given a map v : Var → {false, true} that assigns truth values to the elements of Var, we extend v to

assign truth values to elements of L(G) in the natural way: that is, the same way that eval was defined in

Assignment 2.1

Design a Turing Machine TM3 that decides the following language:

{ϕ ∈ L(G) : There exists v : Var→ {false, true} such that v(ϕ) = true}

1Details will be released when submission of Assignment 2 is complete.

2

Notes

• You may assume that the inputs to TM3 will be properly formatted elements of L(G).

• An example of a Boolean expression evaluator (for Boolean expressions in Reverse Polish

notation) is given in the examples here. You may incorporate this code into your solution if

needed.

Sample inputs and expected outputs

Input Expected output Comments

&1+01 Accept Because (true∧ (false∨ true)) = true

&1&01 Reject Because (true∧ (false∧ true)) = false

&a!a Reject Because no assignment will make (a∧ ¬a) equal true

!&&a!1+0b Accept (a, b) 7→ (true, true) will satisfy ¬((a∧ ¬true) ∧ (false∨ b))

+&&ab!c+&&a!bc&&!abc Accept (a, b, c) 7→ (true, true, false) satisfies

(a∧ b∧ ¬c) ∨ (a∧ ¬b∧ c) ∨ (¬a∧ b∧ c)

&a&+!a!c&+ce+!e!a Reject No assignment satisfies a∧ (¬a∨ ¬c) ∧ (c∨ e) ∧ (¬e∨ ¬a)

&b&+!a!c&+ce+!e!a Accept (a, b, c, e) 7→ (false, true, true, false) satisfies

b∧ (¬a∨ ¬c) ∧ (c∨ e) ∧ (¬e∨ ¬a)

Submission requirements and assessment

• Turing Machines must meet the following requirements:

– Deterministic, single two-way infinite tape

– Start state is 0

– Accept state is halt-accept

– Reject state is halt-reject

• The code used to parse and simulate submitted Turing Machines can be found here:

https://www.cse.unsw.edu.au/∼cs4141/21t1/turing.py. This should behave the same as the on-

line tool with the above settings (without breakpoints), please contact me if this is not the case.

• Marks are awarded based on number of test cases passed. The examples provided here form part

of the test suite, as well as a number of tests with undisclosed inputs. You should design your own

test cases to test your submission.

• No marks are awarded for code readability/commenting/etc, but submissions may still be exam-

ined.

• No marks are awarded for efficiency, but wildly inefficient submissions that exceed the time bounds

will not receive marks.

3

学霸联盟

Due: Monday, 12th April, 12:00 (AEST)

Submission is through WebCMS/give and should consist of up to three text files: TM1.txt,

TM2.txt, and TM3.txt. Each text file should define a Turing Machine, using the syntax of

http://morphett.info/turing/turing.html, maximum size 1Mb each. Submissions will be automarked

and feedback provided immediately.

Note

You can test the output of a single Turing Machine by submitting a single file, but your final

submission should consist of all machines you have defined, in separate files.

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 (25 marks)

Recall from Assignment 2 the definition of the function bin : {0, 1}∗ → N that treats a word of {0, 1}∗

as the binary representation of a non-negative integer, with the last symbol being the least-significant. So

bin(110) = bin(00110) = 6 and bin(e) = 0.

Design a Turing Machine, TM1, that decides the following language:

{x#y#z : x, y, z ∈ {0, 1}∗ and bin(x) + bin(y) = bin(z)}

Sample inputs and expected outputs

Input Expected output Comments

1#1#10 Accept 1 + 1 = 2

1000#0101#1101 Accept Simple addition

100010#101#100111 Accept Alignment check

101010#10#101100 Accept Simple carry

101010#1010#110100 Accept Simple carry

101010#1111#111001 Accept Advanced carry

#101#101 Accept Syntax corner case

101##101 Accept Syntax corner case

1000#0101#1001 Reject Addition error

1111#0101#1010 Reject Addition error

1001#1001 Reject Syntax error

1001#1001#100010# Reject Syntax error

#1001#1001#100010 Reject Syntax error

1

Problem 2 (10 marks)

Design a Turing Machine, TM2, that decides the following language:

{02n : n ∈N}

Sample inputs and expected outputs

Input Expected output

e Reject

0 Accept

00 Accept

000 Reject

0000 Accept

Problem 3 (15 marks)

Consider the following variant of the grammar used in Assignment 2, given by G = (V,Σ, R, E) where

• V = {E,K, I}

• Σ = {+, &, !, 0, 1, a, b, c, d, e, f}

• R consists of the rules:

E → +EE | &EE | !E | K | I

K → 0 | 1

I → a | b | c | d | e | f

G is the grammar that defines Boolean expressions over the variables Var = {a, b, c, d, e, f}, in Polish

Notation, where:

• + represents ∨ (OR)

• & represents ∧ (AND)

• ! represents ¬ (NOT)

• 0 represents false, and

• 1 represents true

For example !&&a!1+0b corresponds to the Boolean expression ¬((a∧ ¬true) ∧ (false∨ b)).

Given a map v : Var → {false, true} that assigns truth values to the elements of Var, we extend v to

assign truth values to elements of L(G) in the natural way: that is, the same way that eval was defined in

Assignment 2.1

Design a Turing Machine TM3 that decides the following language:

{ϕ ∈ L(G) : There exists v : Var→ {false, true} such that v(ϕ) = true}

1Details will be released when submission of Assignment 2 is complete.

2

Notes

• You may assume that the inputs to TM3 will be properly formatted elements of L(G).

• An example of a Boolean expression evaluator (for Boolean expressions in Reverse Polish

notation) is given in the examples here. You may incorporate this code into your solution if

needed.

Sample inputs and expected outputs

Input Expected output Comments

&1+01 Accept Because (true∧ (false∨ true)) = true

&1&01 Reject Because (true∧ (false∧ true)) = false

&a!a Reject Because no assignment will make (a∧ ¬a) equal true

!&&a!1+0b Accept (a, b) 7→ (true, true) will satisfy ¬((a∧ ¬true) ∧ (false∨ b))

+&&ab!c+&&a!bc&&!abc Accept (a, b, c) 7→ (true, true, false) satisfies

(a∧ b∧ ¬c) ∨ (a∧ ¬b∧ c) ∨ (¬a∧ b∧ c)

&a&+!a!c&+ce+!e!a Reject No assignment satisfies a∧ (¬a∨ ¬c) ∧ (c∨ e) ∧ (¬e∨ ¬a)

&b&+!a!c&+ce+!e!a Accept (a, b, c, e) 7→ (false, true, true, false) satisfies

b∧ (¬a∨ ¬c) ∧ (c∨ e) ∧ (¬e∨ ¬a)

Submission requirements and assessment

• Turing Machines must meet the following requirements:

– Deterministic, single two-way infinite tape

– Start state is 0

– Accept state is halt-accept

– Reject state is halt-reject

• The code used to parse and simulate submitted Turing Machines can be found here:

https://www.cse.unsw.edu.au/∼cs4141/21t1/turing.py. This should behave the same as the on-

line tool with the above settings (without breakpoints), please contact me if this is not the case.

• Marks are awarded based on number of test cases passed. The examples provided here form part

of the test suite, as well as a number of tests with undisclosed inputs. You should design your own

test cases to test your submission.

• No marks are awarded for code readability/commenting/etc, but submissions may still be exam-

ined.

• No marks are awarded for efficiency, but wildly inefficient submissions that exceed the time bounds

will not receive marks.

3

学霸联盟