The University of Melbourne
School of Computing and Information Systems COMP30026 Models of Computation
Sample Answers to Tutorial Exercises, Week 8
63. For languages L1 = {ab, c} and L2 = {ca, c}:
(a) L1 ∪ L2 = {ab, ca, c}
(b) L1 ◦ L2 = {abca, cca, abc, cc}
(c) L∗1 = {ε,ab,c,abab,abc,cab,cc,…} (d) L∗1\L∗2 = {ab, abab, abc, cab, . . .}
64. (a) {w|wbeginswitha1andendswitha0}
DFA 081 are allincluded 10
Tonio a
0O 041 To
1
o
0
0
to
1
o i
won’tbeaccepted o Everynodehastwodirections 0,1
I II a
(b) {w | w is not empty and contains only 0s or only 1s}
1 1
0 0 001
Tait’s Theyaneallthesame or
O
o
(c) {w | w contains the substring 0101} nm
0 sointegratetogether 0 I0,1
o
1
1
😯 0 Oil 0
0,1
8o op8
(d) {w | w has length at least 3 and its third symbol is 0}
OH
o
0,1 0,1
T 0,1
it TEg8ttafyfdb K8 4State
o oto TO
on
1
0 0,1
FkE
011
0 0
1
(e) {w | the length of w is at most 5}
0,1 0,1 0,1
(f) {w | the length of w is a multiple of 3}
C
ooo
4
EEE A AcceptState
(g) {w | w is any string except 11 and 111}
POTO
OF
(h) {w|everyoddpositionofwisa1} 04
11 0
001 0
(i) {w | w contains at least two 0s and at most one 1}
0
0,1
0700 0020
(j) {w | the last symbol of w is occured at least twice in w}
00
(k) {ε,0}
Do 0001 0
0
0,1 1 0,1
1 0
EYE
0 111
to 0 D0 it if
00
0
0 800 0020 I1
1 0 0,100
FIT
1
0,1 0,1
T
0,1 11
0,1
3h
G T 0,1 0,1
0,1
Eoka8517
0,1
0,1
0,1
0
01 0,1
0,1 0,1
1
1
1
1
Noaccept state 0,1
(l) The empty set
(m) All strings except the empty string
0,1
0,1
bbba,b a a a,b aaa bb
65.
Notempty
(a) {w | whas at least three as}∩{w | whas at least two bs}
1234 123
1,1a2,1a3,1a4,1 a bbbb
1,2a2,2a3,2a4,2 a bbbb
1,3a2,3a3,3a4,3 a,b
bbb
(b) {w|whasanevennumberof as}∩{w|whasoneortwobs}
bb aaa
a
12 1234
a,b
bbb
a
1,1 b 1,2 b 1,3 b 1,4 b aaaaaaaa
2,1 b 2,2 b 2,3 b 2,4 b
(c) {w | whas an odd number of as}∩{w | wends with b}
bbab ab
1212
aa
1,1 b 1,2 b
a aa
a
b 2,2 b 2,1
(d) {w | whas an even length}∩{w | whas an odd number of as} 2,30
1,1
a
a
2,2
bb a
a,b 1212
bb bb a
a
a a,b Reverse a
a,b
66. (a) {w | w does not contain the substring bb}
2,1
1,2
a
a,b
bb bb
=⇒ aa
(b) {w | w contains neither the substring ab nor ba} aa
aa b b =⇒ b b
b a a,b b a a,b (c) {w|wisanystringnotinA∗◦B∗,whereA={a},B={b}}
a b a,b a b a,b ba ba
=⇒
(d) {w|wisanystringnotinA∗∪B∗,whereA={a},B={b}}(compareto(b)!)
aa aa
b b =⇒ b b
b a a,b b a a,b
(e) {w | w is any string that doesn’t contain exactly two as}
b b b a,b b b b a,b
aaa aaa
=⇒
(f) {w|wisanystringexceptaandb} aa
b a,b =⇒ b a,b
a,b a,b a,b a,b
67. {w | the lenght of w is a multiple of 2 and is not multiple of 3} 0,1
12
0,1
0,1 0,1
1 2 3 =⇒ 1 2 3
0,1 0,1
0,1
0,1
1,1 0,1 2,2 0,1 1,3 0,1 2,1 0,1 1,2 0,1 2,3 0,1
68. From this DFA:
11
0
01
1,2
10 10
01 01
1
a
1 234 145 b
ε
0
1
0
S,0,2 1,3
S
we get:
0,2
ε
23
1 00
0,3
69. From this NFA:
a
b 35 b a b
∅ a 5 b 45
b 1a2ε3 a
b
ε a a weget: 4b5b
a,b
a b
3
a
70. From this NFA:
a
04
aaa a
1b2a3 we end up with the following DFA:
a,b
71. This is the minimal DFA:
72. This is the minimal DFA:
a
01
aa bb
∅ b 2 b 01
a bb
a
034
a 014
a,b 12
b
a
a,b a,b 123a
b