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
1#1#10 Accept 1 + 1 = 2
100010#101#100111 Accept Alignment check
101010#10#101100 Accept Simple carry
101010#1010#110100 Accept Simple carry
#101#101 Accept Syntax corner case
101##101 Accept Syntax corner case
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
&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
3 