The Austalian National University School of Computing
Victor Rivera and
Semester 2, 2021 Assignment 3
Released: Due: Mode: Submit:
8 October, 2021
Friday, 22 October, 2021, 23:55 AEST
individual submissions only
as single pdf file via Wattle (scans of legible handwritten solutions are perfectly acceptable), here.
Foundations of Computation
Pledge of Academic Integrity and Originality statement1
I am committed to being a person of integrity. I pledge, as a member of the Australian National University community, to abide by and uphold the standards of academic integrity outlined in the ANU statement on honesty and plagiarism. I understand that it is wrong to ever misrepresent another person’s work as my own.
I am aware of the relevant legislation, and understand the consequences of me breaching those rules. I have read the COMP1600/COMP6260 academic integrity and pledge to abide by it.
I declare that everything I have submitted in this assignment was entirely my own work.
Name: UID:
Signature:
1Submissions without your name, UID and signature will not be marked. 1
Question 1
Consider the DFA D,
DFA proofs and right-linear grammars
[20+6 Credits]
1 S2 0,1 11
start S0 together with the language
L = {0(11)n0 | n ≥ 0}.
a) Prove that L(D) = L.
(i) Clearly state your two main proof obligations;
(ii) Give a proof for each proof obligation.
Make sure that you give your proof in full rigorous detail. For example, be explicit about any use
of the append theorem.
b) Give a right-linear grammar G that generates the language L, and briefly justify your answer. Solution.
a) Prove that L(D) = L.
(i) Formally state the two statements required to prove to show that L(D) = L.
(B) (ii) (A)
w∈L⇒N∗(S0,w)=S3.
w∈L⇐N∗(S0,w)=S3.
Prove that all strings in the language are accepted by the automaton. We prove a lemma first, N∗(S1,(11)n) = S1 for all n ≥ 0 by induction.
Base case is trivial (n = 0), N∗(S1,ε) = S1 (by N∗ def.). Step case, assume N∗(S1,(11)n) = S1.
N∗(S1, (11)n+1)
= N∗(S1, 11(11)n) = N∗(S2,1(11)n) = N∗(S1,(11)n) = S1
Maths def of N∗ def of N∗ Assumption
We can now prove that N∗(S0,0(11)n0) = S3.
N∗(S0, 0(11)n0)
= N∗(S1,(11)n0)
= N∗(N∗(S1,(11)n),0) = N∗(S1,0)
def of N∗ append theorem lemma def of N∗
(B) Prove that if a string is accepted by the automaton, then it is in the language. There are many ways to go on. Here’s one option.
We instead prove the contrpositive: all strings not in the language are rejected by the automaton: β ̸∈ L ⇒ N∗(S0,β) ̸= S3.
What strings are not of the form 0(11)n0? We claim any string not of the form 0(11)n0 must fall into one (or more) of the following categories.
i. The empty string.
ii. Strings that start with a 1.
iii. Strings that end with a 1.
iv. Strings that start and end with a zero, and contain a third zero.
v. Strings that start with a zero, end with a zero, and have odd many ones in between. vi. Strings of length 1.
Why? Well, suppose a string is not of the form 0(11)n0. Then if it starts with a 1, then case ii. applies. Suppose it does start with a 0. If it ends in a 1, case iii. applies. Suppose it ends with a zero. If it contains a third zero, case iv. applies. So the string must be of the form 01∗0. Since it is not of the form 0(11)n0, it must have odd many ones, and so case v. applies.
The first case is trivial, as N∗(S0,ε) = S0 (by def of N∗), and S0 ̸= S3.
Second case: by observing the DFA, we can see that S4 is a trap state, so N∗(S4,δ) = S4
for any string δ. Then
= N∗(S4,δ) def of N∗ = S4 previous observation
and S4 ̸= S3.
Third case: it requires more work. We need to show that N∗(S0,α1) ̸= S3, for any α ∈ Σ∗. We know that N∗(S0,α1) = N∗(N∗(S0,α),1) by the append theorem, but we are not sure where N∗(S0,α) is. So we can check all cases:
• If N∗(S0,α) = S0, then N∗(N∗(S0,α),1) = N∗(S0,1) = S4 ̸= S3. • If N∗(S0,α) = S1, then N∗(N∗(S0,α),1) = N∗(S1,1) = S2 ̸= S3. • If N∗(S0,α) = S2, then N∗(N∗(S0,α),1) = N∗(S2,1) = S1 ̸= S3. • If N∗(S0,α) = S3, then N∗(N∗(S0,α),1) = N∗(S3,1) = S4 ̸= S3. • If N∗(S0,α) = S4, then N∗(N∗(S0,α),1) = N∗(S4,1) = S4 ̸= S3.
Forth case: it also requires some work. We need to show that N∗(S0,0(11)n0(11)n0) ̸= S3 (the case with odd number of 1’s is considered in the next case). We will make use of
the lemma proven before, that N∗(S1,(11)n) = S1 to obtain
N∗(S0, 0(11)n0(11)n0)
= N∗(S1,(11)n0(11)n0)
= N∗(N∗(S1,(11)n),0(11)n0) = N∗(S1, 0(11)n0)
= N∗(S3,(11)n0)
= N∗(S3,α0) = S4
def of N∗ append theorem lemma def of N∗ for any α
and S4 ̸= S3.
Fifth case: we need to show that N∗(S0,0(11)n10) ̸= S3. We will again make use of the lemma proven before, that N∗(S1,(11)n) = S1 to obtain
N∗(S0, 0(11)n10)
= N∗(S1,(11)n10)
= N∗(N∗(S1, (11)n)10) = N∗(S1,10)
= N∗(S4,0)
def of N∗ append theorem lemma def of N∗ def of N∗
and S4 ̸= S3.
The last case is also trivial, as N∗(S0,0) = S1 (by def of N∗), and S1 ̸= S3. The second
case also covers the string 1.
All the cases are shown to be rejected by the machine, as required.
b) The Following right-linear grammar G generates precisely language L as we used the algorithm “from NFAs to Right-linear Grammars” in lectures and we assumed it to be correct.
S0 →0S1 |1S4
S1 →0S3 |1S2
S2 →0S4 |1S1
S3 →0S4 |1S4 |ε S4 →0S4 |1S4
With S0 as the starting symbol. Question 2
Let A be the ε-NFA below.
FSA conversion
[6+10+10 Credits]
Construct an equivalent DFA C from B, that is L(A) = L(B) = L(C), following the subset construction algorithm in lecture slides week 8, slides 21 and 22.
• Show that C accepts your words w1 and w2 from (a). Solution.
Many solutions. Here’s one: • w1 = aabcc.
• w2 = aacbb.
• NFA B is represented with the following tables (the state labelled with → is the initial state
while the states denoted with ⊙ are the final states.) Using the algorithm from the videos:
{S1, S2, S3} {S2} {S2, S4} {S1} {S2} ∅
∅ ∅ {S2} {S2, S3} ∅ {S2, S4}
∅ {S4} ∅ Using the algorithm from the lecture slides:
a) Give two strings w1, w2 ∈ L(A) that are both at least 4 characters long and such that:
• w1 contains each letter of A’s alphabet, and ends with c;
• w2 ends with b.
• Show that B accepts your words w1 and w2 from (a).
Construct an equivalent NFA B from A, that is L(A) = L(B), following the algorithm in lecture slides week 8, slide 30 (alternatively, following the algorithm in video 11 week 8).
⊙ → S0 S1 ⊙S2 ⊙S3 ⊙S4
⊙ → S0 S1 ⊙S2
{S1, S3} {S2} {S2, S4} {S1} {S2} ∅
∅ ∅ {S2} ⊙S3 {S3} ∅ {S4}
∅ {S4} ∅ 5
– S0 →a S1 →a S1 →b S2 →c S2 →c S2, hence (S0,“aabcc”,S2) ∈ R∗. – S0 →a S3 →a S3 →c S4 →b S4 →b S4, hence (S0,“aacbb”,S4) ∈ R∗.
DFA C is represented with the table below. The state labelled with → is the initial state while the states denoted with ⊙ are the final states. States are treated as single states (see the second table below, where state names have been changed to avoid confusion).
If part (b) was computed using the videos:
• To show that B accepts words w1 and w2 in (a), we show that (S0,w1,S2) ∈ R∗ and (S0, w2, S4) ∈ R∗ by showng the sequence of states:
Changing state names:
⊙→{S0} ⊙{S2 } ⊙{S2 , S4 } ⊙{S1, S2, S3} ⊙{S4 }
{S1, S2, S3} {S2} {S2, S4} ∅ ∅ {S2} ∅ {S4} {S2}
{S1, S2, S3} {S2} {S2, S4} ∅ {S4} ∅
If part (b) was computed using the lecture slides:
{S4} ∅ Changing state names yields the same diagram as above.
AAAA ⊙→BECD ⊙C A A C ⊙D A F C ⊙E E C D ⊙F A F A
⊙→{S0} ⊙{S2 } ⊙{S2 , S4 } ⊙{S1 , S3 } ⊙{S4 }
{S1, S3} ∅
∅ {S1, S3} ∅
{S2} ∅ {S4 } {S2}
{S2, S4} {S2}
{S2 } {S2, S4}
• To show that C accepts words w1 and w2 in (a), we show the eventual state function working N∗(B,w1) and N∗(B,w2):
N∗(B, aabcc) = N∗(E, abcc) = N∗(E, bcc) = N∗(C, cc) = N∗(C, c) = C which is a final state.
N∗(B, aacbb) = N∗(E, acbb) = N∗(E, cbb) = N∗(D, bb) = N∗(F, b) = F which is a final state.
Deterministic PDA [15+4+4+4 Credits] Consider the following language L over the alphabet Σ = {a, b, c}.
L = {ωc | ω ∈ {a, b}∗, ω contains exactly twice as many a’s as b’s} 6
Question 3
For example, the following strings are in L: aabc, babaaac, and c. Whereas the following strings are not: babaac, bbaaaa, aaac, bbbc, and abbc.
a) Prove that L is a deterministic context free language by constructing a deterministic PDA P that accepts L. (You do not need to formally prove language acceptance.) (No marks given for a non-deterministic PDA.)
Solution. Many ways. Here’s one: P:
ε,Z , ε,b, ε,a bZ bb ε
b,Z , b,a, b,b bZ ε bb
a,b , a,Z , a,a ε aZ aa
b) Explain how your PDA works. That is, explain why your automation indeed accepts precisely the
language L.
Solution. We will use the stack to count the difference between the number of a’s and the number of b’s seen so far. To represent a positive number n > 0, we will encode this as a stack with n many a’s. For negative numbers n < 0, a stack with n many b’s. When we see a c, this means that the string has been fully read, and so we accept if and only if the stack contains only the bottom stack symbol Z, (meaning that the count n = 0).
When we observe an a at the input, we increase the count by one (push an a if we see a or Z, pop a b if we see b.)
When we observe a b at the input, we decrease the count by two: pop two a’s if we see two a’s, popanaandpushabifthestackonlycontainsa,orpushtwob’sifweseeZ orbonthestack (as we cannot pop two a’s, we simulate this by transitioning to S1).
Hence the count will be zero when we observe the c if and only if there were exactly twice as many a’s as b’s.
c) Give a string w1 ∈ L that contains at least two b’s. Show that w1 ∈ L(P ) by giving an accepting trace of your machine for w1.
Solution. Many options. Here’s one. Consider w1 = aababac:
(S0, aababac, Z)
⇒ (S0, ababac, aZ) ⇒ (S0, babac, aaZ) ⇒ (S1, abac, aZ) ⇒ (S0, abac, Z)
⇒ (S0, bac, aZ)
⇒ (S1,ac,Z)
⇒ (S0, ac, bZ)
⇒ (S0,c,Z)
⇒ (F, ε, ε)
d) Give a string w2 ̸∈ L that contains at least two b’s and two a’s. Show that w2 ̸∈ L(P ) by giving
a rejecting trace of your machine for w2.
Solution. Many options. Here’s one. Consider w2 = babac:
(S0, ababac, Z)
⇒ (S0, babac, aZ) ⇒ (S1, abac, Z) ⇒ (S0, abac, bZ) ⇒ (S0, bac, Z)
⇒ (S1, ac, bZ)
⇒ (S0, ac, bbZ) ⇒ (S0,c,bZ)
Machine gets stuck in an undefined transition, reject.
Question 4 Nondeterministic Context Free languages [12+3+6 Credits]
Consider the following language L over the alphabet Σ = {a, b}. L={bnam |n