代做program、代写Python/Java程序语言

日期：2024-02-13 10:23

Theories of Computation: Summative Assignment 1

due on Mon 12 Feb, 15:00

Exercise 1. Consider the following εNFA:

(A) Give the NFA that is achieved by removing the above εNFA’s ε-transitions (using the algorithm taught),

[2 points]

(B) Give the DFA that is achieved by determinising your answer to (A), [2 points]

(C) Give the minimal DFA that is achieved by minimising your answer to (B). [2 points]

Exercise 2. Consider the language L of those words matched by a

?

(ba)

?

that contain twice as many a’s as b’s (e.g.

aba, aababa are accepted, but not aaba or baa). Show that this language is not regular. [4 points]

Exercise 3. For any regular expression E and n ∈ N, we write En as an abbreviation for the regular expression

n times

z }| {

E . . . E .

In particular, considering the alphabet {x}, we have the regular expressions A = x

3 and B = x

7

, where A only

accepts the word xxx and B only accepts the word xxxxxxx. It turns out that for every natural number n > 11, we

can express x

n by only concatenating the expressions A and B (e.g. x

12 = AAAA and x

38 = BABBBB).

(A) Show that this is the case for x

13 and x

14

, [2 points]

(B) Prove that this is the case for all n > 11 by using (course-of-values) induction. [3 points]

1