COT-5310 Theory of Computation I
Assignment 2
Florida International University
Knight Foundation School of Computing and Information Sciences
1. (10 points) Find an equivalent NFA for the following regular expression in the alphabet
Σ = {0, 1}: (
0Σ+1(0 ∪ 10) ∪ 0(1 ∪ ε)Σ∗0
)∗
2. (10 points) Convert the DFA below into a regular expression that describes exactly the
same language. Eliminate states in the following order: q3, q1, q2. Show your work.
q0start q1
q2 q3
0
1 1
0,1
0
1
3. (35 points) Find a regular expression which recognizes each of the following languages
(in parts (b) and (c), assume that Σ is an a
itrary non-empty finite set of symbols
and n is an a
itrary positive integer):
(a)
{
w ∈ {a, b, c}∗|w contains at most two a’s and at most two b’s
}
(b)
{
w ∈ Σ∗| the length of w is at most n
}
(c)
{
w ∈ Σ∗| the length of w is not equal to n
}
(d) {w ∈ {a, b, c}∗| (every odd position of w is b or c) ∨ (every even position of w is a)}
(e) {w ∈ {0, 1}∗|w 6= 0100 ∧ w 6= 101}
4. (10 points) Use pumping lemma to show that {0n1m|0 ≤ n ≤ m} is not a regula
language.
5. (25 points) Are the following languages regular? (Prove your answers)
(a)
{
a(
n
2) ∈ {a}∗
∣∣∣ n ∈ Z≥2}
(b)
{
apbqa
√
pqc ∈ {a, b}∗
∣∣∣ p, q ∈ Z+}
1
(c)
{
apb2+qa2 ∈ {a, b}∗
∣∣∣ p, q ∈ Z+}
6. (10 points) Let f : R+ 7→ R+ be a differentiable function and
∀x ∈ R+, f ′(x) ≥ dxe.
Prove that {1df(n)e|n ∈ Z+} is not regular (Hint: use pumping lemma).
2
Computing Theory
COSC 1107/1105
Assignment 2: Computability
Assessment Type Individual assignment. Submit online via Canvas → As-
signments → Assignment 1. Marks awarded for meeting re-
quirements as closely as possible. Clarifications/updates may
e made via announcements
elevant discussion forums.
Due Date Week 12, Sunday 16th October 2022, 11:59pm
Marks 110 worth 25% of your final assessment
1 Overview
This assignment requires you to demonstrate your knowledge of the key concepts of
Turing machines, universality, computability and the Chomsky Hierarchy. You are also
equired to report on some further experiments with the Platypus game.
2 Assessment details
1. Computability (15 marks)
The generalised Platypus green game (GPGG) is defined as follows. Let M1 and
M2 be Turing machines, which share the same tape. The tape is initially all green.
The initial configuration of the two machines is as shown below.
As in the Platypus game, each machine takes turns to move (but there is no scoring
involved).
(a) Show that the halting problem for GPGG is undecidable. You may use any
eduction that you like. (6 marks)
(b) Suppose the GPGG is played on a Turing machine with a finite tape (making
the halting problem decidable), and that this problem has been shown to be
NP-complete. Given your above reduction from some problem A to the GPGG,
can this reduction be used to conclude that A is NP-complete? Why or why
not? Explain your answer. (2 marks)
(c) Seedout, a rather adventurous and reckless ho
it, has proposed the reduction
elow as a way of showing the Empty Language problem is undecidable by
educing the Halting Problem to it. Unfortunately there are two e
ors in this
eduction. Identify these e
ors, explain why these are inco
ect and how they
may be co
ected. (4 marks)
Seedout’s explanation is: ”Assuming the Empty Language problem is decid-
able (and hence the existence of a Turing machine Empty which decides the
problem), we can construct a solution to the Halting Problem as follows. First,
given the Turing machine M and input w, we use these to construct anothe
Turning machine M ′′ which deletes any input on the tape, writes w on the
tape and then acts as M would. So the language accepted by M ′′ is empty iff
M halts on w. See the diagram below for more details.”
(d) Undecidability results are often given in terms of Turing machines. Explain
how these results are relevant to modern programming languages, using three
examples of undecidable problems that occur in such languages. (3 marks)
2. Nondeterminism (8 marks)
Consider the incomplete NFA M0 below, whose alphabet is {0, 1}.
2
Use M0 to create three more NFAs M1, M2 and M3 according to the constraints
elow. Explain in one or two English sentences how you constructed each NFA.
Each of M1, M2 and M3 must contain at least 10 transitions (potentially but
not necessarily including λ-transitions) and must be an NFA but not a DFA.
Specifically there must be at least one combination of state and input (eithe
0 or 1) for which there are at least two possible states. Put another way,
emoving all λ-transitions must not result in a DFA.
Use JFLAP to transform M1, M2 and M3 into equivalent DFAs.
The sizes of the DFA resulting from the determinising algorithm must be as
elow. Note that the JFLAP implementation of this often omits an “e
or”
state, i.e. it may be necessary to add an extra state to the result from JFLAP
in order to account for this. The size constraints below assume a fully deter-
ministic DFA; one way to check for this is that if the DFA has k states, there
must be exactly 2k transitions (one for each of 0 and 1 in each state).
(a) The size of the DFA co
esponding to M1 is 2 or 3. (3 marks)
(b) The size of the DFA co
esponding to M2 is 5. (2 marks)
(c) The size of the DFA co
esponding to M3 is at least 9 (this may be harde
than you think!) (3 marks)
3. Pumping Lemma (20 marks)
(a) There are three e
ors in the statement of the Pumping Lemma for regula
languages below. Find all three, state how to co
ect them, and explain you
answers. (4 marks)
Let L be a regular language. Then ∃n ≥ 1 such that for any w ∈ L such that
|w| > n, ∃x, y, z such that w = xyz where
3
i. |xy| ≤ n
ii. x ̸= λ
iii. xyiz ∈ L for all i ≥ 1
(b) Galadriel, on her Elftiki tour of Middle-Earth in the Second Age, comes across
some scraps of parchment in the Hall of Records of Numenor. These scraps,
numbering 10 in all, are partly burned and not always legible, but contain some
ancient runes that not even Galadriel can decipher. But she can make some
educated guesses, and first must decide on the relevant order of the fragments,
efore choosing from potential translations for each of them, so that the overall
message makes sense.
The fragments are below, with the parts where there are alternative transla-
tions labelled with capital letters, like this:
(Translated text) A (Translated text)
A1: Alternative 1
A2: Alternative 2
A3: Alternative 3
1: As the Pumping Lemma requires xyiz ∈ L, this is a A
A1: paradox A2: problem A3: tautology A4: contradiction
2: so we have w ∈ L, |w| ≥ n and B, and so we have C for some 1 ≤ j ≤ n.
B1: |xy| < n B2: |xy| ≤ n B3: |xy| > n B4: |xy| ≥ n
C1: y = 0j C2: y = 1j C3: y = 0j1j C4: y = (012)j
3: D and xyiz ∈ L for all i ≥ 0
D1: |y| = 0 D2: |y| ≠ 0 D3: |y| > 1 D4: |y| = 1
4: Then ∃n ≥ 1 such that E and F,
E1: for all w ∈ L and |w| ≥ n E2: for all w ∈ L and |w| ≤ n E3: for some
w ∈ L and |w| ≥ n E4: for some w ∈ L and |w| ≤ n
F1: ∃x, y, z such that w = xyz, |xy| ≤ n F2: ∃x, y, z such that w = xyz, |xy| ≥
n F3: ∀x, y, z such that w = xyz, |xy| ≤ n F4: ∀x, y, z such that w =
xyz, |xy| ≥ n
5: and so we have shown that our assumption is false, i.e. that G.
G1: context-free G2: not regular G3: empty G4: regula
6: Beren’s tale: A proof that the language L = H is not I .
H1: {ww|w ∈ {0, 1, 2}∗} H2: {w2w|w ∈ {0, 1, 2}∗} H3: {w1w|w ∈ {0, 1, 2}∗}
H4: {w1w2w|w ∈ {0, 1, 2}∗}
I1: context-free I2: regular I3: empty I4: recursively enumerable
7: and so xyiz is J
J1: 1n+j21n J2: 0n+j0n J3: 0n−j10n20n J4: 1n+j11n20n
8: Let w be K.
K1: 0n10n20n. K2: 1n21n. K3: 1n11n20n. K4: 0n10n.
9: Assume L is L.
L1: not regular L2: regular L3: not context-free L4: context-free
4
10: Now consider M
M1: i = 0 M2: i = 1 M3: i = 2 M4: i = 3
Re-assemble the proof for Galadriel. (6 marks)
You do not need to write the proof out in full. You can submit you
final version on Canvas.
(c) The Pumping Lemma for regular languages states a necessary property fo
such languages. Is it possible that the same property is true for context-free
and context-sensitive languages? Explain your answer. (3 marks)
(d) Let L the language of a DFA with n states. Explain why either L = ∅ or there
is a string w ∈ L such that |w| < n. (3 marks).
(e) The Pumping Lemma for context-free languages is below.
Let L be a context-free language. Then there is an n ≥ 1 such that for any
string w ∈ L with |w| ≥ n there exists strings x, y, z, u, v such that w = xyzuv
and
i. |yzu| ≤ n
ii. |y|+ |u| > 0
iii. xyizuiv ∈ L for all i ≥ 0
Use this to show that the language L = {ai3 | i ≥ 2} is not context-free by
filling in the gaps below. (4 marks)
Proof: Assume . So the Pumping Lemma applies, and so fo
any string w ∈ L with |w| ≥ n there exist strings x, y, z, u, v such that w =
xyzuv and
i. |yzu| ≤ n
ii. |y|+ |u| > 0
iii. xyizuiv ∈ L for all i ≥ 0
Let . So w ∈ L and , and w = xyzuv, |yzu| ≤ n, |y| + |u| > 0
and xyizuiv ∈ L for all i ≥ 0. Now as , this means |yzu| = |y|+ |z|+
|u| ≤ n and so |y|+ |u| ≤ n.
Let i = 0 and consider |xy0zu0v| = |xzv| = −|y|−|u| = n3−(|y|+ |u|) ≥