Need attached advanced maths assignment completed

COMP4141 Assignment 7 2020 Term 1

Due: Sunday, 19th April, 17:00

Submission is through WebCMS/give and should be a single pdf file, maximum size 4Mb. Prose should be typed, not handwritten. Use of LATEX is encouraged, but not required.

Discussion of assignment material with one other person is permitted, but the work submitted must be your own in line with the University’s plagiarism policy.

Problem 1 (12 marks) Let M = (Q, Σ, Γ, δ, q0, qaccept, qreject) be a Turing Machine, and x ∈ Σ∗ be a word of length n. We are interested in the problem of whether M will accept x using at most n tape cells. Let Σ′ = (Γ ∪ Q ∪{#}). A finite run (of r steps) of M on input x can be represented as a word over (Σ′)∗:

w = #C1#C2# · · ·#Cr #

where each Ci ∈ (Q ∪ Γ)n+1 represents a configuration of M indicating the current state, the tape head position, and the contents of n tape cells. We are interested in the language:

L = {w ∈ (Σ′)∗ : w represents an accepting run of M on input x}.

Note that L is either ∅ (if M does not accept x using at most n cells) or contains a single word representing the accepting run of x – so we have reduced our problem to determining if L contains 0 or 1 element.

The aim of this question is to show that an NFA with O(n|M|) states can recognise L = (Σ′)∗ \ L – regardless of whether L contains 0 or 1 element.

Remark

Compare this with the proof of Theorem 5.13 in Sipser.

There are four reasons why a word w ∈ (Σ′)∗ is not in L:

(I) w is not in the correct format to represent a run

(II) w does not begin with #q0 x#

(III) w = #C1#C2# · · ·#Cr # and there is an i such that Ci does not yield Ci+1

(IV) w does not end with #yqacceptz# where y, z ∈ Γ∗; |y|+ |z| = n; and |z| > 0

If we can define NFAs with O(n|M|) states that can identify each of these conditions, then we can construct an NFA with O(n|M|) states that can recognise L: for any word w /∈ L, simply make a non-deterministic e-transition to whichever NFA represents the condition that w meets.

Here is an NFA that recognises condition (II) (assuming the string is properly formatted):

1

· · ·# q0 x0 x1 xn−1 #

Σ′ \{#}

Σ′ \{q0} Σ′ \{x0} Σ′ \{x1} Σ′ \{#}

Σ′

Σ′

And here is an NFA that recognises condition (IV) (assuming the string is properly formatted):

y0 y1 y2 · · · yn−1 yn

z0 z1 z2 · · · zn−1 zn

# Γ Γ Γ Γ Γ

Σ′

#

Γ Γ Γ Γ Γ #

Σ′

Σ′ \ Γ Σ′ \ Γ Σ′ \ Γ Σ ′ \ Γ

Σ′ \{#}

Σ′

Σ′

qaccept qaccept qaccept qaccept

Σ′′

Σ′′ Σ′′ Σ′′

Here Σ′′ = Σ′ \ (Γ ∪{qaccept}). Intuitively this NFA will non-deterministically guess the second-last # symbol. It will then keep track of the number of symbols before qaccept is seen and the number of symbols afterwards, and it will accept if any of the following hold:

• qaccept is not seen exactly once;

• There are not n + 1 symbols between two #, of which n are tape symbols (elements of Γ); or

• There is not at least one tape symbol after qaccept

(a) Give an NFA with O(n|M|) states that recognises condition (I). Justify your answer. (6 marks)

(b) Give an NFA with O(n|M|) states that recognises condition (III). Justify your answer. (6 marks)

2

Problem 2 (8 marks) Show that the following problem is PSPACE-complete (Hint: Consider the complementary problem and use Problem 1):

EQNFA

Input: Two NFAs M and N

Question: Is L(M) = L(N)?

Problem 3 (10 marks) Consider the following decision problem:

2-SAT

Input: A boolean formula ϕ in CNF with at most 2 literals per clause

Question: Is ϕ satisfiable?

Show that PAT H ≤L 2-SAT.

Hint 1: Find a reduction first then check if it is log-space. Hint 2: The 2-CNF clause (¬x ∨ y) is logically equivalent to the expression (x → y).

3