this is automata assignment

COMP4141 Assignment 8 2020 Term 1

Due: Tuesday, 28th 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 (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 = ε and q ∈ F; or

• w = aw′ 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)

1