Plan
School of Computing and Information Systems COMP30026 Models of Computation Tutorial Week 8
23–25 September 2020
This week’s exercises cover formal languages, DFAs, NFAs, and minimization. Exercises 65-67 are important because they teach you a systematic approach to building DFAs for intersection, complements and differences of languages.
Some of the exercises on automata come from Sipser, Introduction to the Theory of Computation. Chapter 1, on regular languages, is available on Canvas under Readings Online. The book has many examples and it contains many more exercises, plus answers to selected exercises.
The exercises
63. For two languages L1 = {ab, c}, L2 = {ca, c}, construct a language:
(a) L1 ∪ L2 (b) L1 ◦ L2
( c ) L ∗1
(d) L∗1\L∗2
64. Draw DFAs recognising the following languages. Assume that the alphabet Σ = {0, 1}.
(a) {w|wbeginswitha1andendswitha0}
(b) {w | w is not empty and contains only 0s or only 1s}
(c) {w | w contains the substring 0101} (so w = x0101y for some strings x and y) (d) {w | w has length at least 3 and its third symbol is 0}
(e) {w|thelengthofwisatmost5}
(f) {w | the length of w is a multiple of 3}
(g) {w | w is any string except 11 and 111} (h) {w | every odd position of w is a 1}
(i) {w | w contains at least two 0s and at most one 1}
(j) {w | the last symbol of w is occured at least twice in w} (k) {ε,0}
(l) The empty set
(m) All strings except the empty string
65. 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 following idea: If the set of states for DFA D1 is Q1 and the set of states for D2 is Q2, we let the set of states for the combined DFA D be Q1 × Q2. We construct D so that, having consumed a string s, D will be in state (q1,q2) iff D1 is in state q1, and D2 is in state q2 when they have consumed s. Throughout this question, assume that the alphabet Σ = {a, b}.
(a) {w | w has at least three as and at least two bs}
(b) {w|whasanevennumberofasandoneortwobs} (c) {w|whasanoddnumberofasandendswithb}
(d) {w | w has an odd number of as and has even length}
66. 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|wisanystringnotinA∗◦B∗,whereA={a},B={b}} (d) {w|wisanystringnotinA∗∪B∗,whereA={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}
67. The following language is the difference of two simpler languages. First construct DFAs for simpler languages. Assume that the alphabet Σ = {a, b}.
{w | the lenght of w is a multiple of 2 and is not multiple of 3}
68. (An example from Lecture 7). Use the subset construction method to turn this NFA into an
equivalent DFA:
01
0
00
ε
69. Use the subset construction method to turn this NFA into an equivalent DFA: 1a2ε3
11
0
ε
S
1
23
1
b
εaa 4b5b
70. Use the subset construction method to turn this NFA into an equivalent DFA:
a
04
aaaa 1b2a3
71. Find a minimal DFA which is equivalent to this one:
b
12
aaab
b
34
b
72. Find a minimal DFA which is equivalent to this one:
b
2
a
aab a
1b4 5 a
a bb
3