/Users/billy/gits/moc-2021/problem-sets/ps11.dvi
School of Computing and Information Systems
COMP30026 Models of Computation Problem Set 11
11 – 15 October 2021
Content: Turing machines, decidability, recognisability, closure results
P11.1 Show that the class of decidable languages is closed under complement. Why can’t we use
the same argument to show that the class of Turing recognisable languages is closed under
complement?
P11.2 Show that the class of decidable languages is closed under concatenation, as well as under
Kleene star.
P11.3 A 2-PDA is a pushdown automaton that has two stacks instead of one. In each transition
step it may consume an input symbol, pop and/or push to stack 1, and pop an/or push to
stack 2. It can also leave out any of these options (using ǫ moves) just like the standard PDA.
In the Week 9 lecture we used the pumping lemma for context-free languages to established
that the language B = {0n1n2n | n ∈ N} is not context-free. However, B has a 2-PDA that
recognises it. Outline in English or pseudo-code how that 2-PDA operates.
P11.4 In fact, a 2-PDA is as powerful as a Turing machine. Outline an argument for this proposition
by showing how a 2-PDA can simulate a given Turing machine. Hint: Arrange things so that,
at any point during simulation, the two stacks together hold the contents of the Turing
machine’s tape, and the symbol under the tape head sits on top of one of the stacks.
P11.5 For each of the following languages, write an algorithm in pseudocode which describes a
Turing machine that decides the following languages. Assume that Σ = {0, 1}
(i) {w | w has an equal number of 0’s and 1’s}
(ii) {w | w has twice as many 0’s as 1’s}
(iii) {w | w does not have twice as many 0’s as 1’s}
P11.6 For each language in the previous question, draw a Turing machine that carries out the
pseudocode. Then write down the sequence of configurations your TM goes through on an
interesting input.
P11.7 Show that the problem of whether the language of a DFA is empty, is decidable. That is,
show that the language
E
DFA
= {〈D〉 | D is a DFA and L(D) = ∅}
is decidable. Hint: Write pseudocode for an algorithm which analyses the graph of the DFA,
and argue that your algorithm will not run forever on any input DFA 〈D〉.
P11.8 Show that the problem of whether the language of a CFG is empty, is decidable. That is,
show that the language
E
CFG
= {〈G〉 | G is a CFG and L(G) = ∅}
is decidable. Hint: Write pseudocode for an algorithm which analyses the rules of the CFG,
and argue that your algorithm will not run forever on any input CFG 〈G〉.