数学代码代写 MT4512代写 自动机、语言和复杂性代写

MT4512 Automata, Languages and Complexity

数学代码代写 EXAM DURATION: 2 hours EXAM INSTRUCTIONS: Attempt ALL questions. The number in square brackets shows the maximum marks obtainable for that

EXAM DURATION: 2 hours

EXAM INSTRUCTIONS: Attempt ALL questions.

The number in square brackets shows the maximum marks obtainable for that question or part-question.

Your answers should contain the full working required to justify your solutions.

INSTRUCTIONS FOR ONLINE EXAMS:

Each page of your solution must have the page number, module code, and your student ID number at the top of the page. You must make sure all pages of your solutions are clearly legible.

1. 数学代码代写

a) Consider the DFA D₁ given by ({q₀, q₁, q₂}, {a, b}, δ₁, q₀, {q₁}), where δ₁ is

	aq2	b
q0	q1	q0
q1	q2	q1
q2	q0	q2

(i) Draw the diagram of D₁. [2]

(iii) Prove that L(D₁) is the set of words over the alphabet {a, b} that contain a number of as that is congruent to 1 modulo 3. [4]

(iv) Give a regular expression for L(D₁). [2]

(b) Consider the regular expression R = a^∗(aab + c²)^∗ . Give the diagram of an NFA N such that L(N) = L(R). (You do not need to prove that N accepts the right language). [3]

(c) Let D₂ = (Q, Σ, δ₂, s₀, T) be a DFA, and let a ∈ Σ. Assume that δ₂(q, a) = q for all q ∈ Q. Prove that either {a}^∗⊆ L(D₂) or {a}^∗∩ L(D₂) = ∅. [2]

2. 数学代码代写

(a) Consider the language

L₁ = {w ∈ {a, b}^∗ : no initial subword of w has more as than bs}.

Design a PDA P such that L(P) = L₁. (You do not need to prove that P accepts the right language). [3]

(i) Write down the configurations that can be reached by M on input ab, and on input abb. [3]

(ii) Does M halt on all input? Justify your answer. [4]

(b) For each of the following languages, say whether it is Turing decidable. Justify your answer in each case.

(i) L₁ = {〈M〉 : M accepts at least two words}.

(ii) L₂ = {〈M〉 : M’s read/write head never moves past the first 30 tape cells, for every input word w}. [4]

4. 数学代码代写

a) Show that if L₁ and L₂ are languages in NP then

L₁L₂ = {uv : u ∈ L₁, v ∈ L₂}

is in NP. [4]

(b) The language HugeClique is {〈G〉 : G is a finite graph with a clique of size at least |V (G)|/2}.

You may assume that graphs are encoded as in lectures, so that the length of the encoding is proportional to the square of the number of vertices.

(i) Draw an example of a graph with 4 vertices that is in HugeClique. [1]

(ii) Draw an example of a graph with 5 vertices and 5 edges that is not in HugeClique [1]

(iii) Prove that HugeClique is in NP. [2]

(iv) Fix an integer k. Construct a map f from the set of all finite graphs to the set of all finite graphs with at least 2k vertices such that 〈G, k〉∈Clique if and only if〈f(G)〉 ∈HugeClique. [2]

(v) Prove that Clique is polynomial-time reducible to HugeClique. [3]

(vi) Is HugeClique NP-complete? Justify your answer. [1]

更多代写：澳洲cs代考靠谱吗  托福作弊被抓  英国Chemistry化学网课exam代考  term paper写作指南  中文文献mla格式  金融工程作业代写

合作平台：essay代写 论文代写 写手招聘 英国留学生代写