Search the whole station

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

303

## 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 question or part-question.

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 D1 given by ({q0, q1, q2}, {a, b}, δ1, q0, {q1}), where δ1 is

(i) Draw the diagram of D1. [2]

(iii) Prove that L(D1) 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(D1). [2]

(b) Consider the regular expression R = a(aab + c2) . 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 D2 = (Q, Σ, δ2, s0, T) be a DFA, and let a ∈ Σ. Assume that δ2(q, a) = q for all q ∈ Q. Prove that either {a}⊆ L(D2) or {a}∩ L(D2) = . [2]

### 2.数学代码代写

(a) Consider the language

L1 = {w ∈ {a, b} : no initial subword of w has more as than bs}.

Design a PDA P such that L(P) = L1. (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]

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

(i) L1 = {M : M accepts at least two words}.

(ii) L2 = {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 L1 and L2 are languages in NP then

L1L2 = {uv : u L1, v L2}

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, kClique if and only if〈f(G)〉 ∈HugeClique. [2]

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

The prev: The next:

### Related recommendations

• #### 离散数学作业代写 MACM 201代写 D100 AND D200代写

1175

MACM 201 - D100 AND D200 ASSIGNMENT #8 离散数学作业代写 Instructions Answer all questions on paper or a tablet using your own handwriting. Put your name, student ID number and page number at th...

View details
• #### 数学统计作业代写 数学作业代写 统计作业代写 数学代写

467

Homework 3 数学统计作业代写 Instructions: Solve the problems in the spaces provided and save as a single PDF. Then upload the PDF to Canvas Assignments by the due date. Instructions: Solve t...

View details
• #### 数学考试代做 Math 2415代写 数学期末代写 数学作业代写

500

Math 2415 Final Exam 数学考试代做 To get full credit you must show ALL your work. The problems must be solved without any assistance of others or the usage of unauthorized material To get fu...

View details
• #### 模块和表示论代写 MATH 5735代写 数学作业代写 数学代写

657

MATH 5735 - Modules and Representation Theory Assignment 1 模块和表示论代写 1. (9 marks) Recall that an integral domain is a commutative ring (with unity) that has no zero divisors. (a) Pro...

View details
1