Semester 2, 2021
Assignment 3
The Austalian National University
School of Computing
Foundations of Computation
Released: 8 October, 2021
Due: Friday, 22 October, 2021, 23:55 AEST
Mode: individual submissions only
Submit: as single pdf file via Wattle (scans of legible handwritten solutions are perfectly acceptable), here.
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
https://wattlecourses.anu.edu.au/mod/assign/view.php?id=2395381
https://www.anu.edu.au/students/academic-skills/academic-integrity
https://www.legislation.gov.au/Details/F2015L02025
https://cs.anu.edu.au/courses/comp1600/policies/#academic-integrity
Question 1 DFA proofs and right-linear grammars [20+6 Credits]
Consider the DFA D,
S0start S1
S2
S3
S4
0
1
0
1
0
1
0, 1
0, 1
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.
Question 2 FSA conversion [6+10+10 Credits]
Let A be the �-NFA below.
S0start
S1 S2
S3 S4
�
�
a
b
c
a
�
c
b
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;
2
• w2 ends with b.
b) • 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).
• Show that B accepts your words w1 and w2 from (a).
c) • 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).
Question 3 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}
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.)
b) Explain how your PDA works. That is, explain why your automation indeed accepts precisely the
language L.
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.
d) Give a string w2 6∈ L that contains at least two b’s and two a’s. Show that w2 6∈ L(P ) by giving
a rejecting trace of your machine for w2.
Question 4 Nondeterministic Context Free languages [12+3+6 Credits]
Consider the following language L over the alphabet Σ = {a, b}.
L = {bnam | n < m < 2n or 2n < m < 3n} a) Build a context free grammar G that generates L. Briefly explain your answer. b) Give a string w ∈ L, and show its derivation in the grammar G that you have constructed in part (a). c) Construct a non-deterministic PDA N that accepts L. 3