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]