The Australian National University Semester 2, 2020 Research School of Computer Science Tutorial 11 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 Weeks 1 – 11
Exercise 1
Natural deduction proofs
Establish the validity of the following formulae using natural deduction. 1. (p∨q)→(¬p→q)
2. (∃x.(¬P (x))) → ((∀x.P (x)) → D(z))
Example solution has ten lines, but any proper proof will do.
Exercise 2 Tree Induction
Consider the definition of binary trees given in the lectures
data Tree a = Nul | Node (Tree a) a (Tree a)
and the following three functions:
f :: Tree a -> Int
f (Node Nul
xr )=(fl)+(fr)
g :: Tree a -> Int gt=h0 t
h :: Int -> Tree a -> Int
haccNul= h acc (Node h acc (Node
NulxNul)=acc+1
l xr ) =h(haccl)r
Establish, using structural induction, that f t = g t for all trees t of type Tree a.
State clearly what property P is being proved by induction, including any quantifiers needed in the statement of P and in
the inductive hypothesis.
Exercise 3 Tree Induction (II)
Consider the definition of binary trees given in the lectures
data Tree a = Nul | Node (Tree a) a (Tree a)
and the following two functions:
size :: Tree a -> Int
size Nul = 0 –C1
size (Node l x r) = 1 + size l + size r
mirror :: Tree a -> Tree a
mirror Nul = Nul
mirror (Node l x r) = Node (mirror r) x (mirror l)
— M1 — M2
size tcountsthenumberofnodesintandmirror tobtainsthemirroredtreet. Establish, using structural induction, that mirror preserves the size of the tree.
Exercise 4 Hoare Logic
Consider the Hoare Triple:
[x>0] while (x ̸= 0) do x := x – 1 [true]
1. What is a suitable invariant P ?
2. What is a suitable variant E?
3. We wish to use Hoare Logic to prove the total correctness of the triple
[x>0] while (x ̸= 0) do x := x – 1 [true] For your reference the while-rule for total correctness is as follows:
P ∧ b → E ≥ 0 [P ∧ b ∧ E = n] S [P ∧ E < n] [P ] while b do S [P ∧ ¬b]
where n is an auxiliary variable not appearing anywhere else.
Exercise 5 Deterministic Finite Automata
Design a minimal DFA that recognises the language
{w ∈ {a,b}∗ | in w, every a is followed by bb}
Exercise 6 Push-down Automata
1. Design a (deterministic or non-deterministic) pushdown automaton that recognises precisely all odd length palin- dromes over the alphabet Σ = {a, b, c}. A palindrome is a word that reads the same backwards and forwards, e.g. “racecar” or “reviver”. Briefly explain the design of your automaton.
2. Is your PDA deterministic or non-deterministic? Justify your answer.
3. Give an execution trace of your PDA that shows that the word “accca” is accepted by your automaton.
4. Argue why there cannot be an execution trace that accepts the word “acca” (which is an even-length palindrome).
Exercise 7 Regular Expressions
In this exercise, we conceptualise regular expressions as string, and we add parentheses. Over the finite alphabet Σ = {a, b, . . . , z}, a regular expression with parentheses is defined by the following:
• ε, ∅ and each a ∈ Σ is a regular expression
• if r and s are regular expressions, the so are r|s, rs, r∗, and (r).
That is, the strings “abc”, “a|(bcd) ∗ e′′ and “a ∗ (b|c)d” are regular expressions with parentheses, but “∗ ∗ ba|′′ and “(ba(∗” are not.
1. Design a context-free grammar that generates precisely all strings over the alphabet Σ ∪ {(, ), ∗, |, ∅, ε} that are regular expressions with parentheses.
2. Hence, or otherwise, construct a pushdown automaton that accepts precisely all regular expressions with parenthe- ses.
Exercise 8 Turing Machine
Specify a Turing machine which will multiply the binary number on its tape by 3. Assume (as above) that the head is initially somewhere over the data.
When doing this operation manually, we would work from right to left and compute a new value and a carry at each bit position. The carry can be 0, 1, or 2. The pair (new bit, carry-out) is a simple function of old bit value and carry-in. The following table captures this function.
012 0 0,0 1,0 0,1 1 1,1 0,2 1,2 Λ 0,0 1,0 0,1
We suggest that you try multiplying a few numbers by hand, using the above table, before starting on the Turing machine.
Exercise 9 Undecidable Problem
Show that the language
is undecidable.
L = {w | w is an encoding of a TM that accepts all strings in Σ∗}