Home Page > > Details

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]

Contact Us(Ghostwriter Service)

- QQ：99515681
- WeChat：codinghelp
- Email：99515681@qq.com
- Work Time：8:00-23:00

- Ghostwriter Cs1b Spring 2024 Tth Hw08h... 2024-04-19
- Help With Managing Financial Risk Prob... 2024-04-19
- Ghostwriter Cs 0449 – Project 5: /Dev/ 2024-04-19
- Ghostwriter Elec 2141 Digital Circuit ... 2024-04-19
- Help With Csc171 — Videogame Projecthe 2024-04-19
- Help With Comp3411 Artificial Intellig 2024-04-19
- Help With Stat3061: Random Processes &... 2024-04-19
- Ghostwriter Accounting 452, Spring 202... 2024-04-19
- Ghostwriter Finc5001 Foundations In Fi... 2024-04-19
- Ghostwriter 7Ssmm712 – Topics In Appli 2024-04-19
- Help With Com 337 - Film Studies For T... 2024-04-19
- Ghostwriter Mes202tc - Digital Vlsi Sy... 2024-04-19
- Ghostwriter Geography 2041B Distance S... 2024-04-19
- Ghostwriter Ecos3006 International Tra... 2024-04-19
- Help With Fit5225 2024 Sm1 Creating An... 2024-04-19
- Help With Cit 593: Introduction To Com... 2024-04-19
- Help With Math 4931: Take Home Examgho... 2024-04-19
- Ghostwriter Csci 547|Info 533: Systems... 2024-04-19
- Ghostwriter Cs536-S24 Intro To Pls And... 2024-04-19
- Help With Fit5212 - Assignment 1Ghostw... 2024-04-19

Contact Us - Email：99515681@qq.com WeChat：codinghelp

© 2021 www.asgnhelp.com

Programming Assignment Help！