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