Mathematics homework help
Mathematics homework help. 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 (10 marks)
An alternating finite automaton (AFA) is a tuple A = (Q, Σ, l, δ, q0, F) where
• Q is a finite set of states
• Σ is a finite input alphabet
• l : Q → {∃, ∀} is a labelling of the states
• δ ⊆ Q × Σ × Q is the transition relation
• q0 ∈ Q is the start state
• F ⊆ Q is the set of final states.
A word w is accepted from a state q if and only if:
• w = e and q ∈ F; or
• w = aw0 and
– if l(q) = ∃ then there exists q
such that (q, a, q
) ∈ δ and w
is accepted from q
; or
– if l(q) = ∀ then for all q
such that (q, a, q
) ∈ δ we have w
is accepted from q
.
The language accepted by an AFA is defined to be the set of words accepted from q0.
Show that the class of languages accepted by AFAs are precisely the regular languages.
Problem 2 (10 marks)
Define ARE to be the class of languages accepted by Alternating Turing Machines.
Prove or disprove: ARE = RE.
Problem 3 (10 marks)
(a) Show that if SAT ∈ BPP then SAT ∈ RP. Hint: Try to build a truth assignment using the fact that ϕ(x) is
satisfiable if and only if ϕ(true) or ϕ(false) is satisfiable. (6 marks)
(b) Show that if NP ⊆ BPP then RP = NP. Hint: Use (a) (4 marks)