Description
1. [12 marks] This question develops your ability to devise regular expressions, given an explicit definition of a
language. For each of the following languages, prove they are regular by giving a regular expression which
describes them.
Justify your answers.
(a) L = {x | x begins with a 0 and ends with a 1}.
(b) L = {x | x contains at least four 0’s}.
(c) L = {1, 11, }.
(d) L = {x | the length of x is at most 3}.
(e) L = {x | x doesn’t contain the substring 110}.
(f) L = {x | |x| > 0, i.e. x is non-empty}.
2. [20 marks] This question tests your understanding of how to translate a regular expression into a finite automaton. Using the construction of Lemma 1.55, construct NFAs recognizing the languages described by the
following regular expressions.
(a) [5 marks] R = ∅
∗
.
(b) [15 marks] R = (0 ∪ 1)∗111(0 ∪ 1)∗
.
3. [15 marks] This question tests your understanding of how to translate a finite automaton into a regular expression. Consider DFA M = (Q, Σ, δ, q, F) such that Q = {q1, q2, q3}, q = q1, F = {q1, q3}, and δ is given
by:
δ 0 1
q1 q2 q2
q2 q2 q3
q3 q1 q2
Draw the state diagram for M, and then apply the construction of Lemma 1.60 to obtain a regular expression
describing L(M).
4. [15 marks] This question allows you to practice proving a language is non-regular via the Pumping Lemma.
Using the Pumping Lemma (Theorem 1.70), give formal proofs that the following languages are not regular:
(a) L =
www | w ∈ {0, 1}
∗
.
(b) L = {1
n0
m1
n | m, n ≥ 0}.
(c) L =
x | x ∈ {0, 1}
∗
is not a palindrome
. Recall a palindrome is a string that looks the same forwards
and backwards. Examples of palindromes are “madam” and “racecar”.
1
5. [4 marks + 4 marks bonus] This question reveals important subtleties of the Pumping Lemma. Let B =
0
kx0
k
| k ≥ 1 and x ∈ Σ
∗
.
(a) [4 marks] Consider the following argument, which claims to prove that B is not regular.
Assume B2 is regular, and let p be the pumping length. Consider string s = 0p10p ∈ B2, and decompose
it as s = xyz with x = , y = 0p
, z = 10p
. Then, pumping s down by setting i = 0 yields string
s
0 = xyi
z = xy0
z = 10p 6∈ B2. Hence, by the Pumping Lemma, we have a contradiction. We conclude
that B2 is not regular.
The question is: What is wrong with this proof?
(b) [4 marks, bonus] Prove that, in fact, B is regular.
2