Computer Science, School of Informatics and Engineering
Assignment 8
This assignment is due at 5pm Friday, Week 14. Late submissions will incur a penalty of 20% of earned marks per day or part day.
This assignment concerns various aspects of the theory of computability
1. Pushdown Automata and Context-free Languages
Give a context-free grammar for the following language: L1 = {ww R c n : w ∈ {a, b}*, n >= 0}, i.e each string consists of a string w containing a’s and b’s, followed by the reverse of w, followed by 0 or more c’s.
2. Turing Machines (10 marks) Show that the class of Turing-recognizable languages is closed under the operations of
(a) concatenation and (b) intersection.
Hint for part (a): You may wish to make use of a nondeterministic Turing machine to recognize the concatenation of two Turing-recognizable languages. For any input string, the NDTM can nondeterministically divide the string into two parts
3. Undecidability using a reduction from an undecidable language (10 marks) “Blank-symbol”
Consider the problem of deciding whether a single-tape Turing machine ever writes a blank symbol during the course of its computation on any input string. This problem can be formulated as the language:
E = {
Show that E is undecidable. Hints for solution: As is usual for undecidability problems, we can show that ATM reduces to E, by assuming that there is a decider R for E, and then showing that we can make use of R to decide ATM. This leads to a contradiction, because ATM is known to be undecidable.
It may be a useful strategy to construct a Turing machine that has the property referred to in the definition of E if and only if a particular Turing machine M accepts a particular input w. This is the same strategy shown in the textbook, e.g. for demonstrating the undecidability of REGULARTM (p. 191).
USA 
India