The Australian National University Semester 2, 2020 Research School of Computer Science Tutorial 8 and
Foundations of Computation
The tutorial contains a number of exercises designed for the students to practice the course content. During the lab, the tutor will work through some of these exercises while the students will be responsible for completing the remaining exercises in their own time. There is no expectation that all the exercises will be covered in lab time.
Covers: Lecture Material Week 8
At the end of this tutorial, you will be able to
• minimise FSAs;
• construct Non-Deterministic Finite Automata from (ε-) Non-Deterministic Finite Automata;
• build Regular Expressions given a language;
• construct an equivalent Deterministic Finite Automaton from a Non-Deterministic Finite Automaton; • construct an equivalent (ε) Non-Deterministic Finite Automaton from a Regular Expression.
Exercise 1 NFA to DFA conversion
1. Construct a non-deterministic finite state automaton that accepts the language of binary strings that begin and end with the same bit. Try to use as few states as you can. (Note that strings that are one letter long satisfy this predicate, and so should be accepted).
Solution.
0,1
? S1
Q0
06Q
Q
Q
sQ 0,1 Q
– S0 – S3 3
1
? 1
S2
6
0,1
2. Use the subset construction algorithm to construct an equivalent deterministic FSA from your previous answer. Solution.
The following table demonstrate implementation of subset construction algorithm. The state labelled with → is the initial state while the states denoted with ∗ are the final states.
State 0 1
∅∅∅
→S0 S13 S23 ∗S13 S13 S1 ∗S23 S2 S23 S1 S13 S1 S2 1S2 S23
0
?
-
1 0
S1 1
S13
–
06
S0
1
?
-
0 1
S2 0
S23
Exercise 2
Regular Expressions
6
1
Consider the alphabet Σ = {a, b}. Build Regular Expressions for:
1. the set of strings over Σ∗ that consists of alternating a’s and b’s;
Solution.
(ε | a)(ba)∗(ε | b)
2. the set of strings over Σ∗ that contains an even number of a’s and b’s;
Solution.
(aa | bb | (ab | ba)(aa | bb)∗(ab | ba))∗
Exercise 3 Identifying Equivalent States
Consider the DFA given by the following state diagram:
a SaS
35
start S1
a
b
bb
S2 a S4 a,b Identify all equivalent states of this automation using the algorithm given in the lectures.
Solution. To simplify notation, we just write 1 for S1 and similarly for all other states.
1. The initial partition just distinguishes final states and non-final states. That is, we start with [[1, 5], [2, 3, 4]].
bb
2. We test [2,3,4] for splitting. Since 2 −→ 1 and 3 −→ 4 and 1 and 4 are (by the previous step) known to be non-equivalent, they need to be in different partitions.
aa
Similarly, 4 −→ 4 and 3 −→ 5 and 4 and 5 are (by the previous step) non-equivalent, they need to be in different paritions.
This means that we separate all states in [2, 3, 4] in the next partition and obtain [[1, 5], [2], [3], [4]] as the second
partition.
b
2
2. Convert the automaton to an NFA using the algorithm given in the lectures.
Solution.
aa
3. We now test [1, 5] for splitting. We have 1 −→ 3 and 5 −→ 3 so they produce equivalet states on a. Moreover, bb
4. As the singletion sets [2], [3] and [4] cannot be split, no more splittings are possible, and [[1, 5], [2], [3], [4]] is the final partition.
That is, only states S1 and S5 are equivalent in the above automation. Exercise 4 From ε-NFAs to NFAs
Consider the ε-NFA given by the following state diagram: aεa
1 −→ 2 and 5 −→ 2 so they also produce equivalent (even identical) states on b. That means that we don’t need to split [1, 5].
start
S b S 01
1. Compute the ε−closure of each state. Solution.
• eclose(S0) = {S0}
• eclose(S1) = {S1, S0}
• eclose(S2)={S2,S1,S0}
c c
b
ε
S2 a
start
a a a,b S b S
01
c a,c
b,c
a,b
Alternatively, you can follow the algorithm from the videos. It would yield the following NFA:
3
S2 a,b,c
Exercise 5
From Regular Expressions to ε-NFAs
For the regular expression 00(0 | 1)∗
• use the algorithm given in lectures to produce a ε-NFA A
a,b,c start S0
c a,b,c
a,b,c b,c
S2 a,b,c
a,b,c
• describe the language that A accepts. Phrase your answer in the form L(A) = {w ∈ Σ∗ | P (w)}, where P (w) is some predicate on words.
Solution.
L(A) = {w ∈ {0, 1}∗ | w contains all binary numbers starting with 00} A=
start
S0S 67
εε S0S0SεS SεS
0123εεε45 S1S
S1
b,c
a,b,c
Exercise 6
Consider the non-deterministic finite automaton A:
-S0
Q Q
Q 1Q
T
3 0
89
ε
6
U 0,1
1. Describe the language that this automaton accepts.
Solution. The language L(A) is the set of all binary integers that are even (or, equivalently, end in 0), but without
unnecessary leading 0s.
Qs
4
2. Use the subset construction algorithm to construct an equivalent deterministic FSA from your previous answer.
Solution. The following table demonstrate implementation of subset construction algorithm. State labelled with → is the initial state while the states denoted with ∗ are the final states.
State
→Ss ∗ST SU S∅ ∗SU T
Exercise 7 More Regular Expressions
Consider the alphabet Σ = {a, b}. Build Regular Expressions for:
1. the set of strings over Σ∗ that contains an odd number of a’s;
Solution.
(b | ab∗a)∗ab∗
2. the set of strings over Σ∗ that ends with b and does not contains the substring aa;
Solution.
(b | ab)∗(b | ab)
3. the set of string over Σ∗ that contains a number of a’s that is a multiple of 3.
Solution.
b∗ | (b∗ab∗ab∗ab∗)∗
Exercise 8 More from ε-NFAs to NFAs Consider the ε-NFA given by the following state diagram:
0 1
ST SU S∅ S∅
SUT SU S∅ S∅
SUT SU
Here, we have started the construction with the initial state, SS , and have only added states to the transition table
that are in fact reachable from the initial state.
start S0
1. Compute the ε−closure of each state. Solution.
• eclose(S0)={S0,S1,S2} • eclose(S1) = {S1}
• eclose(S2) = {S2}
a,c ε,b
S2
c
S1
2. Convert the automaton to an NFA using the algorithm given in the lectures.
Solution.
ε,c
b
5
a,c
start S0
a,c b,c
c
S1
S2
Alternatively, you can follow the algorithm from the videos. It would yield the following NFA:
a,c
start S0
a,c a,b,c
a,c
S1
b,c
b
Exercise 9
From Regular Expressions to ε-NFAs
For each of the following regular expressions
• use the algorithm given in lectures to produce a ε-NFA A
01234
a,b,c
a,b,c
• describe the language that A accepts. Phrase your answer in the form L(A) = {w ∈ Σ∗ | P (w)}, where P (w) is some predicate on words.
1. 01∗;
Solution. L(A) = {w ∈ {0, 1}∗ | w begins with 0 followed by 1’s} A=
ε
start S 0 S ε S 1 S ε S
ε
2. (0 | 1)01; Solution.
L(A) = {w ∈ {0, 1}∗ | w is the 3-bit binary representation of either 1 or 5} A=
S2 a,b,c
6
start S
S0S 12
εε
S 0 S 1 S 0 567
εε
S1S 34
7