Search the whole station

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

157

## 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. 

(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. 

(iv) Give a regular expression for L(D1). 

(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). 

(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.数学代码代写

(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). 

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

(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.数学代码代写

a) Show that if L1 and L2 are languages in NP then

L1L2 = {uv : u L1, v L2}

is in NP. 

(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. 

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

(iii) Prove that HugeClique is in NP. 

(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. 

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

The prev: The next:

### Related recommendations

• #### 应用数学计算代写 数学计算代写 数据分析代写 数学作业代写

520

Fall 2021 应用数学计算代写 Read these instructions carefully!!! This project involves predicting what happens to a mortgage loans that have been purchased by FNMA during the Read these instr...

View details
• #### 图论代写 Graph Theory代写 Assignment代写

665

MT4514 Graph Theory Assignment 1 图论代写 This assignment forms 5% of the assessment for this module. The assignment will be marked out of 20 marks. Please answer all questions, This assi...

View details
• #### 代写数学作业 MATH 7241代写 数学作业代写 数学课业代写

170

MATH 7241 代写数学作业 Problem Set #3 Reading: relevant background material for these problems can be found in the class notes, and in Rosenthal Chapter 3. Problem Set #3 代写数学作业 ...

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

342

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
1