Theory of Computation - Department of Computer Science

The Australian National University
Research School of Computer Science
Marcus Hutter
Jan Leike
Semester 1, 2014
Assignment 2 of 3
Theory of Computation
Release Date. Thursday, March 27, 2014
Due Date. Monday, April 28, 2014 1300
Maximum points. 25
Weight. 10% of final grade
Estimated time. 15 hours
Late Penalty. 20% per day
Questions to Jan Leike ([email protected])
Submission. Hand in on Wattle or drop in the course mailbox on the ground floor in the CSIT building
by Monday, April 28, 2014 1300 . Your name and university id must be indicated clearly on every
submitted piece of paper. You do not need to provide your solutions in LATEX if your handwriting
is legible. Please indicate the actual time spent on the assignment, and separately the time used for
preparation (reading/learning).
Exercise 1
Gradiance
8 points
You should have received an email with your login details to Gradiance. Log in to Gradiance and complete
the homework “Assignment 2 (graded!)”, to be found in the section Homeworks. You have only one
attempt in completing this exercise!
Exercise 2
Proof by Induction
4 points
Consider the context-free grammar G defined by the following productions.
S → aS | Sb | a | b
(a) Describe L(G) informally.
(b) Prove by induction on the string length that no string in L(G) has ba as a substring.
CFG → PDA
Exercise 3
4 points
Convert the grammar
S → aAA
A → aS | bS | a
to a PDA that accepts the same language by empty stack, and show an accepting sequence of IDs for
input string aabaaa.
Exercise 4
CFL Pumping Lemma
4 points
i j k
Use the Pumping Lemma for context-free languages to show that the language L = {a b c | i · j = k}
over the alphabet Σ = {a, b, c} is not context-free.
Exercise 5
Closure properties of CFLs
2+4 points
(a) Are context-free languages closed under set difference? That is, for any two context-free languages
L1 and L2 , is L1 \ L2 always context-free?
(b) Recall that for a language L, min(L) = {w | w ∈ L, but no proper prefix of w is in L}. Are contextfree languages closed under the min operation?
In each case, provide a formal proof that justifies your answer!
Exercise 6
Turing Machines
6 points
Using JFLAP, construct a 3-tape Turing machine that multiplies two non-negative integers. The two input
numbers are given in binary notation on the first two tapes. The output is to be written on the third tape.
Save your Turing machine to a file of the form u1234567.jff (substituting your uni id) and submit it
on Wattle as part of this assignment sheet. Some documentation on creating multitape Turing machines
in JFLAP can be found at http://jflap.org/tutorial/turing/multi/index.html.

Download Report