CMSC 303 Introduction to Theory of Computation, VCU
Spring 2015, Assignment 5 Solutions
Due: Thursday, March 30, 2017 in class
Total marks: 38 marks + 4 marks bonus for typing your solutions in LaTeX.
Unless otherwis
...
CMSC 303 Introduction to Theory of Computation, VCU
Spring 2015, Assignment 5 Solutions
Due: Thursday, March 30, 2017 in class
Total marks: 38 marks + 4 marks bonus for typing your solutions in LaTeX.
Unless otherwise noted, the alphabet for all questions below is assumed to be Σ = f0; 1g.
1. [6 marks] This question asks you to examine the formal definitions of a TM and related concepts closely. Based
on these definitions, answer the following.
(a) A configuration of a Turing Machine (TM) consists of three things. What are these three things?
Solution: The location of the tape head, the tape contents, and the state of the machine.
(b) Can a Turing machine ever write the blank symbol t on its tape?
Solution: Yes. The blank symbol is by definition in Γ.
(c) Can the tape alphabet Γ be the same as the input alphabet Σ?
Solution: No. By definition, t 2 Γ, but t 62 Σ.
(d) Can a Turing machine’s head ever be in the same location in two successive steps?
Solution: Yes. This happens if we are at the leftmost cell on the tape and try to move the head left.
(e) Can a TM contain just a single state?
Solution: No. Every TM must contain both an accept and reject state.
(f) What is the difference between a decidable language and a Turing-recognizable language?
Solution: A language L is decidable if there exists a TM which halts on any input x 2 Σ∗ and accepts
if x 2 L, or rejects if x 62 L. For a recognizable language, only the acceptance condition is required. In
other words, if x 62 L, the TM can either halt and reject or it can loop forever.
2. [8 marks] This question gets you to practice describing TM’s at a semi-low level. Give an implementation-level
description of a TM that decides the language
L = fx j x contains twice as many 0s as 1sg:
By implementation-level description, we mean a description similar to Example 3.11 in the text (i.e. describe
how the machine’s head would move around, whether the head might mark certain tape cells, etc. . . . Please do
not draw a full state diagram (for your sake and for ours)).
Solution: Define TM M to act as follows on input string w 2 Σ∗:
(a) (Tape is blank) If the first cell on the tape is blank, reject.
(b) Scan the input from left to right until a zero is found. Place a mark over this zero. If no zero is found,
reject
[Show More]
