The Australian National University Semester 2, 2020 Research School of Computer Science Tutorial 7 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 7
At the end of this tutorial, you will be able to
• design Deterministic Finite Automata given a language;
• determine whether a word is recognised by an automaton; • describe the language that an automaton recognises.
Exercise 1 DFAs and Acceptance
The automaton A1 is specified by the following diagram.
0
S1 – S4 0
11
@
@
0
– S0 S3 0,1
@1 0I@ @
@ @
0@
@
R@ 1 @
S2 – S5 1
1. Translate the graphical representation of A1 into the form of a 5-tuple, (Σ, S, s0, F, N). Solution.
Σ = {0,1};
S = {S0,S1,S2,S3,S4,S5}; s0 = S0;
F = {S4,S5};
State 0 1
S0 S1 S2
S1 S4 S3 N=S2 S3S5
S3 S3 S3 S4 S4 S3 S5 S3 S5
2. The next state function is N and so N∗ is the eventual state function. What is N∗(S2,00010)? Please show your solution step by step.
1
Solution.
N∗(S2, 00010) =N∗(N(S2, 0), 0010) you can skip this step =N∗(S3,0010)
=N∗(S3,010) =N∗(S3, 10) =N∗(S3,0) =N∗(S3,ε) =S3
3. What is the purpose of the state S3?
Solution. S3 is a ‘failure’ state; any string that enters S3 will stay in S3 and never be accepted.
4. What language does A1 accept? Phrase your answer in the form L(A1)={w∈Σ∗ |P(w)}
where P (w) is some predicate on words.
Solution. L(A) = {w∈Σ∗ |∃n∈N.(w=0n ∨w=1n)∧n≥2}.
5. Consider the statement ∀n ∈ N. N∗(S5,1n) = S5. Express it in English and give a proof. Which technique would you be using?
Solution. In English, this reads that “the automaton remains in state S5 if it processes an aribitrary long sequence of 1’s.”. We prove this statement by induction on n.
For n = 0, we have that N∗(S5,10) = N∗(S5,ε) = S5 (by def. of N∗). Now let n > 0. Then
.
Exercise 2
Consider the alphabet Σ = {0, 1}.
1. Construct a DFA that recognises the language {w∈Σ∗ |whasanoddnumberof0’s}; Solution.
N∗(S5,1n)
=N∗(N(S5, 1), 1n−1)(by def. of N∗)
=N∗(S5,1n−1)(by def. of the transition state function) =S5(by IH)
Deterministic Finite Automata
11 0
start S0
2. Construct a DFA that recognises the language {w ∈ Σ∗ | w contains the substring 110}; Solution.
S1
2
0
01
start S 1 S 1 S 0 S
0123
0,1
0
3. Construct a DFA that recognises the language
{w ∈ Σ∗ | w does not contains the substring 110}; Solution.
0 10,1 start S 1 S 1 S 0 S
0123
Exercise 3
0
Let A2 be an automaton with next state function given in the following table. The initial state of the automaton is S0 and the only accepting state is Sf .
State 0 1
S0 S1 S2
S1 S3 S4
S2 S4 S3
S3 S5 Sf
S4 Sf S5
S5 S5 S5
Sf S6 S6 S6 S6 S6
1. Draw the transition diagram for A2. Solution.
00
S-S-S 135
* 0,1
@1
@@ -S @
@@
0@
0,1
H
?
H
H R@ @R
Hj
S2 – S4 – Sf
0 0 0,1
2. Describe the language L(A2) accepted by A2.
Solution. The language accepted by this automaton is the finite set of strings of length equal to 3 over the alphabet
{0, 1} with an odd number of 1’s: {001, 010, 100, 111}.
3. State what you need to prove to establish that every word of the language you have described is accepted by A2.
(You do not need to give proofs.)
Solution. We have to show that N∗(S0, 001) = Sf ,
3
– S6
N∗(S0, 010) = Sf , N∗(S0, 100) = Sf , N∗(S0, 111) = Sf .
Give a proof of the fact that every word accepted by A2 is in the language you have described.
Solution. WefirstshowthateverywordacceptedbyA2 haslengthexactlythree.SoconsiderthatN∗(S0,w) = Sf.
Looking at the transition diagram, this can only happen if
• wisoftheformxdwhered∈{0,1}andxisastring,
• N∗(S0,x)∈{S3,S4}.
Again, if N∗(S0, x) ∈ {S3, S4}, this can only happen if
• xisoftheformyewheree∈{0,1}andyisastring, • andN∗(S0,y)∈{S1,S2}
Again, the latter is only possible if y is a single letter y ∈ {0, 1} so that in total w = yed where all of y, e, d ∈ {0, 1} are single letters, so that w is of length three.
There are eight words of length three, and by tracing the transition diagram, we have that A2 accepts exactly the words in the language described above.
In summary: if w is accepted by A2 , then w is of length 3 and one of the words {001, 010, 100, 111} as the other length-3 words are not accepted.
Exercise 4 Non-Existence of Automata
Let L be the language of strings over {0, 1} that contain more 0’s than 1’s.
Prove that there is no finite state automaton that can recognise L.
Solution.
Suppose there exists a DFA A which accepts L. Let S0 be A’s start state, we derive a contradiction.
There are only finitely many different states of A, so by the pigeon-hole principle there exist numbers n, m, with n > m, such that
N∗(S0,0n) = N∗(S0,0m)
The string 0n1m contains more 0’s than 1’s, so it is in L and is accepted by A. Hence
N∗(N∗(S0,0n),1m) = N∗(S0,0n1m) ∈F N∗(S0,0m1m) = N∗(N∗(S0,0m),1m) = N∗(N∗(S0,0n),1m) ∈F
And therefore
so 0m1m is accepted. But 0m1m ∈/ L, giving us a contradiction.
Exercise 5 Deterministic Finite Automata
Consider the alphabet Σ = {0, 1}.
1. Construct a DFA that recognises the language {w∈Σ∗ |whasanevennumberof1’s}; Solution.
00 1
start S0
S1
2. Construct a DFA that recognises the language {w∈Σ∗ |whastwoorthree1’s};
Solution.
4
1
0 0 0 0 0,1 start S 1 S 1 S 1 S 1 S
01234
3. Construct a DFA that recognises the language {w ∈ Σ∗ | w contains the substring 110100}. Solution.
1 1
start S
0
1
1,0 S 1 S 0 S 1 S 0 S 0 S
0
Formal Proofs of Automaton Languages I
1 S00S1 S2
1 00123456
Exercise 6
Consider the following finite automaton B:
1
1 0
0,1
We would like to prove that the language L(B) that is accepted by B is equal to
L={0(11)n :n≥0}
Prove that L = L(B). Ensure that you clearly state your two main proof obligations, and that the proof is given in full
rigorous detail.
Solution. We first prove that B accepts all strings in L(B), that is,
x ∈ L(B) ⇒ N∗(S0,x) = S1
Since all strings in L(B) are of the form 0(11)n for some n ≥ 0, we do a proof by induction on n.
Base case, n = 0.
N ∗ (S0, 0(11)0) = N ∗ (S0, 0ε) = N ∗ (S0, 0) = S1 Step case. Assume that N∗(S0,0(11)n) = S1 and prove that N∗(S0,0(11)n+1) = S1.
N∗(S0, 0(11)n+1) = N∗(S0, 011(11)n) = N∗(S1, 11(11)n) = N∗(S2, 1(11)n) = N∗(S1, (11)n) = S1
Where the last step is justified by since N∗(S0, 0(11)n) = S1 by assumption, and N∗(S0, 0(11)n) = N∗(S1, (11)n), we
have that N∗(S1, (11)n) = S1. Hence x ∈ L(B) ⇒ N∗(S0,x) = S1
5
S3
0
We now prove the converse, that if a string is accepted by B, then it must be in L(B). N∗(S0,x)=S1 ⇒x∈L(B)
It is easier instead to prove the contrapositive: If a string is not in L(B), then B rejects it. x ̸∈ L(B) ⇒ N∗(S0,x) ̸= S1
Now, what kinds of strings are not in L(B)? Well, L(B) is the set of all strings that start with a zero, and are followed by an even number of ones. So strings that don’t satisfy this condition must be either
• The empty string.
• Any string that starts with a one.
• Any string that starts with a zero, and is followed by another string that contains at least one zero. • Any string that starts with a zero, and is followed by a string of odd many ones.
The first case is trivial, as N∗(S0,ε) = S0 ̸= S1.
The second case is also trivial, as by observing the DFA we can see that S3 is a trap state, so N∗(S3,δ) = S3 for all
strings δ. Then, N∗(S0, 1δ) = N∗(S3, δ) = S3 ̸= S1
The third cases requires some work, but we can use the append theorem to help us. A string of this form looks like 0α0β
for some strings α, β. Then,
N∗(S0,0α0β) = N∗(S1,α0β) = N∗(N∗(S1,α),0β)
Now, we are not sure where N∗(S1,α) is, but we know that N∗(S1,α) ̸= S0, as there is no way to enter S0 from any
other state. So we check all the combinations.
• If N∗(S1,α) = S1, then N∗(N∗(S1,α),0β) = N∗(S1,0β) = N∗(S3,β) = S3. • If N∗(S1,α) = S2, then N∗(N∗(S1,α),0β) = N∗(S2,0β) = N∗(S3,β) = S3. • If N∗(S1,α) = S3, then N∗(N∗(S1,α),0β) = N∗(S3,0β) = S3.
So in all cases, we end up in the non-final state S3.
The forth case is a string of the form 0(11)n1, which is a zero followed by odd many ones. We can use the property proven
before, that N ∗ (S0 , 0(11)n ) = S1 together with the append theorem to obtain
N∗(S0, 0(11)n1) = N∗(N∗(S0, 0(11)n), 1) = N∗(S1, 1) = S2 ̸= S1
All the cases are shown to be rejected by the machine, as required.
Exercise 7 Formal Proofs of Automaton Languages II
(Difficult.) Consider the following finite automaton
{b,c} a {a,b,c}
? – S0
? ?
a
c
-b
S01 – S02
and prove that the DFA C recognises the language L = {γabδ | γ, δ ∈ {a, b, c}∗}.
Ensure that you clearly state your two main proof obligations. Make sure that you give your proof in full rigorous detail.
For example, be explicit about any use of the append theorem.
Solution.
We need to show two things:
6
1. C accepts all strings γabδ, for any γ, δ ∈ {a, b, c}∗, i.e., N∗(S0,γabδ) = S02
2. if C accepts a string w, i.e., N∗(S0, w) = S02, then there exists γ, δ ∈ {a, b, c}∗ such that w = γabδ. We tackle both in turn.
1. We establish the following facts that we will use later.
Lemma 1
N∗(S0,γab) = S02
Proof: the left hand side equals N∗(N∗(S0,γ),ab) by the append theorem. But we have no way of knowing what
N∗(S0,γ) is, so we consider every possibility:
N∗(S0, ab) =S02 N∗(S01,ab) =S02 N∗(S02,ab) =S02
Hence N∗(S0,γab) = N∗(N∗(S0,γ),ab) = N∗(S02ab) = S02. We next prove
Lemma 2
N∗(S02,δ) = S02
Proof. This is an easy induction on the length of δ. For the base case (δ = ε) we have N∗(S02, ε) = S02 by definition
of N∗. For the step case, we calculate
N∗(S02, xδ) =N∗(N(S02, x), δ) =N∗(S02, δ)
(Def. of N∗) (Holds for all x ∈ {a, b, c}) (IH)
=S02
We can now show that C recognises all strings of the form γabδ by looking at the eventual state function:
N∗(S0, γabδ) =N∗(N∗(S0, γab), δ) =N∗(S02,δ)
=S02
2. As in the first part, we isolate some observations that we will use later.
Lemma 3
N∗(S0,w)=S02 ⇒∃γ′,δ.(w=γ′bδ∧N∗(S0,γ′)=S01)
(Append Theorem) (Lemma ??) (Lemma ??)
Proof: by induction on the length of w. Base case, w = ε, which follows because N∗(S0,ε) ̸= S02, so the LHS of the implication is false, and the implication is vacuously true. Inductive case, suppose N∗(S0,wx) = S02. Now N∗(S0,wx) = N(N∗(S0,w),x) by the corollary to the append theorem. We cannot know what N∗(So,w) is, but can eliminate one possibility: there is no x ∈ {a, b, c} such that N(S0, x) = S02, so N∗(S0, w) ̸= S0. If N∗(S0, w) were S01 then x can only be b, and so Lemma ?? holds by setting γ′ = w and δ = ε. If N∗(S0,w) were S02, then by the IH w = γ′bδ and N∗(S0,γ′) = S01. Therefore wx = γ′b(δx), whatever x is. So Lemma ?? holds in this case too.
We next observe that
Lemma 4
N∗(S0,w) = S01 ⇒ ∃γ.w = γa
Proof: simply because all arcs into S01 are labelled by a.
We now show that any string accepted by C has necessarily the form w = γabδ for some strings γ and δ. So assume that C accepts w, that is, N∗(S0,w) = S02. By Lemma ?? there are strings γ′ and δ such that
w = γ′bδ and N∗(S0,γ′) = S01.
Using Lemma ?? we now obtain γ such that γ′ = γa. Putting everything together, we have that w = γabδ as required.
7