## 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