/Users/billy/gits/moc-2021/problem-sets/ps08.dvi
School of Computing and Information Systems
COMP30026 Models of Computation Problem Set 8
13–17 September 2021
Content: regular languages, DFAs, NFAs, subset construction, minimisation
P8.1 Draw DFAs recognising the following languages. Assume that the alphabet Σ = {0, 1}.
(i) {w | w is not empty and contains only 0s or only 1s}
(ii) {w | w has length at least 3 and its third symbol is 0}
(iii) {w | the length of w is at most 5}
(iv) {w | the length of w is a multiple of 3}
(v) {w | every odd position of w is a 1}
(vi) {w | w contains at least two 0s and at most one 1}
(vii) {w | the last symbol of w occurs at least twice in w}
(viii) All strings except the empty string
P8.2 Each of the following languages is the intersection of two simpler languages. First construct
the DFAs for the simpler languages, then combine them using the construction from T8.3 to
create a DFA for the intersection language
(a) {w | w has at least three as and at least two bs}
(b) {w | w has an odd number of as and ends with b}
(c) {w | w has an odd number of as and has even length}
P8.3 Each of the following languages is the complement of a simpler language. Again, the best
way to proceed is to first construct a DFA for the simpler language, then find a DFA for
the complement by transforming that DFA appropriately. Throughout this question, assume
that the alphabet Σ = {a, b}.
(a) {w | w does not contain the substring bb}
(b) {w | w contains neither the substring ab nor ba}
(c) {w | w is any string not in A∗ ◦ B∗, where A = {a}, B = {b}}
(d) {w | w is any string not in A∗ ∪ B∗, where A = {a}, B = {b}}
(e) {w | w is any string that doesn’t contain exactly two as}
(f) {w | w is any string except a and b}
P8.4 The language
L = {w | the length of w is a multiple of 2 and is not multiple of 3}
is the difference of two simpler languages. First construct DFAs for the simpler languages,
then construct a DFA for L. Assume the alphabet Σ = {a, b}.
P8.5 A language is regular iff it is recognised by some DFA. Prove that for any languages L,K ⊆ Σ∗
(i) If L is regular then Lc is regular
(ii) If L and K are both regular and then L ∩K is regular
(iii) If L and K are both regular and then L \K is regular
Another way to say this is “The class of regular languages is closed under intersection, com-
plement and difference”. You have demonstrated this already for some example languages.
For this exercise you should specify how this works in general, using the formal definition of
a DFA. Hint: Your proof for (iii) can be much shorter.
P8.6 Use the subset construction method to turn this NFA into an equivalent DFA:
1 2 3
4 5
a ǫ
ǫ a
b a
b
b
P8.7 Use the subset construction method to turn this NFA into an equivalent DFA:
0
1 2 3
4
a
b
a
a
a
a
a
P8.8 Construct a minimal DFA equivalent to this one:
1 2
3 4
b
a
a
ba
b
b
a
P8.9 Construct a minimal DFA equivalent to this one:
2
51
3
4
a
b
a
a
b
b
b
a
a
b