Computer Science > QUESTIONS & ANSWERS > CMSC 303 Introduction to Theory of Computation, VCU Virginia Commonwealth University - CMSC 303CMSC3 (All)

CMSC 303 Introduction to Theory of Computation, VCU Virginia Commonwealth University - CMSC 303CMSC303_Spring2017_A5_fullsolutions

Document Content and Description Below

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 LaT... eX. 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]

Last updated: 2 years ago

Preview 1 out of 5 pages

Buy Now

Instant download

We Accept: