- Read [Sip12] Chapter 0; you may need to review the prerequisite materials in discrete mathematics to have sufficient
working knowledge for this course. - Do [Sip12] Chapter 1, exercise 1.18 (h) and (i) (in exercise 1.6). Justify your solutions by properly structuring
and annotating your regular expressions. - Do [Sip12] Chapter 1, exercise 1.29 (b).
- Do [Sip12] Chapter 1, problem 1.53.
- Prove or disprove that the following languages are regular.
(a) {uvur
| u, v ∈ (0 ∪ 1)+}.
(b) {uurv | u, v ∈ (0 ∪ 1)+}. - Using the closure properties of regular sets and the fact that the language {a
nb
n | n ≥ 0} is not regular, prove
that the language {w ∈ {a, b}
∗
| #a(w) 6= #b(w)} is not regular. This part is not graded since it was covered in
lecture. Do the part below.
Prove that the above language L is non-regular by a direct application of Pumping Lemma. - Consider the following two languages over the alphabet {0, 1}:
L1 = {1
nx | x ∈ {0, 1}
∗
and x contains at least n 1s, for n ≥ 1},
L2 = {1
nx | x ∈ {0, 1}
∗
and x contains at most n 1s, for n ≥ 1}
Study the regularity of the languages L1 and L2. - For each of the following languages, construct a context-free grammar generating the language; briefly and precisely
describe the strings generated by each variable in the grammar. Notes: You should aim to give the simplest
grammars possible, and offer brief explanations about how your grammars work.
(a) {a
i
b
j
| i, j ≥ 1, and |i − j| ≤ 3}.
(b) {a
i
b
j
| i, j ≥ 0, and i 6= j}.
(c) {x1x2cy | x1, x2, y ∈ {a, b}
∗
, and there exists x ∈ {a, b}
∗ with x1xx2 = y
r}.
(d) {w ∈ {0, 1}
∗
| the number of 0s in w is a multiple of 3, and w is a palindrome}.
Sample Solution
