Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: zz-x2580
COMP4141 Assignment
Due: Monday, 7th March, 12:00 (AEDST)
Submission is through WebCMS/give and should be a single pdf file, maximum size 2Mb. Prose should
be typed, not handwritten. Use of LATEX is encouraged, but not required.
Discussion of assignment material with others is permitted at a high level, but the work submitted must
be your own in line with the University’s plagiarism policy.
Problem 1 (20 marks)
Show that the following languages over Σ = {0, 1} are regular:
(a) {02m+113n : m, n ∈N}
(b) {w ∈ Σ∗ : w does not contain 011 as a substring}
(c) {w ∈ Σ∗ : w contains an even number of occurrences of 0011 as a substring}
(d) {w ∈ Σ∗ : w contains the same number of occurrences of 01 as 10 }
Problem 2 (10 marks)
For each of the following pairs of representations of regular languages, prove that they define different
languages.
(a) The language accepted by the following DFA:
0
1
1
0
0
1
0
1
and the language defined by the following NFA:
1
0, 1
1
1
0
1
(b) The language accepted by the following NFA:
0, 1
0
and the language defined by the regular expression(
(0∪ 1)0(0∪ 1))∗
Problem 3 (10 marks)
For a language L ⊆ Σ∗, define
odd(L) := {w ∈ L : |w| is odd}
(a) Show that if L is regular then odd(L) is regular.
(b) Prove or disprove: if odd(L) is regular then L is regular.
Problem 4 (20 marks)
For an NFA A = (Q,Σ, q0, δ, F), define L∀(A) to be the set of words w ∈ Σ∗ such that for all runs q0, . . . , q
of A on w, the last state q is in F. (Compare with the definition of L(A), which is the same, except that
it uses “for some" in place of “for all".) Intuitively, this definition amounts to a change of the acceptance
condition for NFA’s. Show that it does not actually make a difference to the set of languages that can be
accepted. That is, show that for all languages L, there exists an NFA A such that L = L(A), if and only if
there exists an NFA B such that L = L∀(B).
Problem 5 (20 marks)
Let Σ be a finite alphabet.
(a) Give a (recursive) definition of a function rev : Σ∗ → Σ∗ that reverses a word in Σ∗. So for example
rev(abbab) = babba; rev(aaab) = baaa. (6 marks)
(b) Consider the following (recursive) definition of a function REV : REΣ → REΣ:
REV(∅) = ∅ REV(R1 ∪ R2) = REV(R1) ∪ REV(R2)
REV(e) = e REV(R1 · R2) = REV(R2) · REV(R1)
REV(a) = a for all a ∈ Σ REV(R∗) = (REV(R))∗
2
Prove that for all regular expressions E ∈ REΣ,
L(REV(E)) = {rev(w) ∈ Σ∗ : w ∈ L(E)}.
(8 marks)
(c) Show that the following language is not regular:
{w · rev(w) : w ∈ {a, b}∗}
(6 marks)
Problem 6 (10 marks)
Let Σ = {0, 1} and for i ∈N>0, let Li be the language:
Li = {w ∈ Σ∗ : The i-th last symbol in w is 1}
(a) Show that Li can be accepted by an NFA with i+ 1 states. (4 marks)
(b) Show that a minimal DFA that accepts Li needs at least 2i states. (Hint: consider the Myhill-Nerode
equivalence classes of all words of length i) (6 marks)
Problem 7 (10 marks)
Let L1 = {01i01j01j : i, j > 0} and L2 = {w ∈ {0, 1}∗ : w contains 00}.
(a) Show that L = L1 ∪ L2 satisfies the Pumping Lemma with pumping length 3. (4 marks)
(b) Prove that L = L1 ∪ L2 is not regular using the Myhill-Nerode theorem. (6 marks)
