Take Home Exam 3 Solution

Description

Objectives

To familiarize with computation using Turing Machines and inspect aspects of the class of languages associated with them.

Speci cations

You must adhere to the notation conventions adapted in the textbook. Use the standard deterministic Turing Machine as de ned in the book unless stated otherwise. You should utilize basic machines notation whenever asked for.

Your solution should be delivered as a pdf le generated using the tex template provided or employ-ing other text editors. You are allowed to use only text and vector images in your submission, i.e. use of raster images is clearly forbidden.

Questions and submission regulations are included in subsequent sections. Assume that any input string w over a nite alphabet is initially placed on the tape of the standard TM always as .tw unless stated otherwise. If multi-tape TM is used then the same placement occurs on its rst tape and initial con gu-ration will be as .t concerning the remaining tapes.

Designing your solutions to the tasks, explicitly state any assumptions you make and pay particular attention to the notation you use. Your proofs must be sound and complete. Grading will be heavily a ected by the formalization of your solutions.

Question 1 (12 pts)

Answer the questions using the following Turing Machine.

a 6= t

1. • R t Lt a

a. Write the given TM in ve-tuple notation as M = (K; ; ; s; H) explicitly specifying each con-

stituent. Let = fa; b; t; .g and (q; .) = (q; !) for all q 2 K H. Denote as a table. (6 pts)

2. Using M de ned in (a), write down the computation (sequence of con gurations related by ‘_M )

for the following initial con gurations. (6 pts)

1. (s; . t tbab).

2. (s; .aaa).

3. (s; .a t bb).

Question 2			(8 pts)
Given the following Turing Machine on the alphabet = fa; b; c; t; .g,
> R	a 6= t	Rt L b = c R t R a b R t R a

trace its operation on the input string babc (intially placed on the tape as .tbabc) without explic-itly referring to the particular set of states. In plain English, write down the set of actions taken by the TM upon encountering any string over ( ft ; .g) on its tape.

Question 3 (10 pts)

Given the following Turing Machine M on the alphabet = fa; b; #; t; .g, answer the questions.

b

• • a

• R_a R_b # L_b R a R#b R

t	a
	t
	t
	Lt

a.	Write the language L over fa; bg that M semidecides using set notation.								(5 pts)
b.	Using De nition	4.2.2 of the textbook, identify the function f :	f	a; b	g		7! f	g	such that
							a; b
M(w) = f(w) where w		2 fa; bg .							(5 pts)

Question 4 (10 pts)

Using basic machines notation, construct a multi-tape Turing Machine that decides the following language:

L = fwcu : w; u 2 fa; bg⁺; w(2i) = w(2i 1) = u(i) for i = 1; :::; juj; jwj = 2jujg.

Question 5 (10 pts)

Using basic machines notation, construct a multi-tape Turing Machine that computes the following function:

• : fa; bg 7! a;f bg where f(e) = e and f(u) = v where u; v 2 fa; bg⁺ and jvj juj + 1 such that

v(2i 1) = u(i)

v(2i) = u(juj i + 1)

^juj

2

Question 6 (12 pts + 10 pts bonus)

A variant of Turing Machine is the deterministic queue TM de ned as a quintuple (K; ; ; s; H) where K is the set of states; is a nite alphabet containing . to denote the left end of the queue; s 2 K is the initial state; H K is the set of halting states; and : (K H) 7!K ( [ f#g) is the transition function where (q; a) = (p; X) for q 2 K H, p 2 K, a 2 , X 2 [ f#g indicates that whenever the machine is in state q and there is a at the front position of the queue, the machine enters the state p and takes the action X. If X 2 , the machine enqueues the element X at the rear position of the queue. Otherwise if X = #, the machine pops the element at the front. Note that by these mechanisms the queue can get arbitrarily large or small.

1. Impose restrictions on so that the pop operation is not allowed in an empty queue and enqueueing

of . is forbidden. (4 pts)

2. Add the exibility of taking action regardless of what element is placed at the front of the queue, using e-transitions in in a way that preserves the determinism of the machine. Also update the sets

over which is de ned. (4 pts)

c. De ne the yields-in-one-step relation of the machine, covering every case. (4 pts)

4. Construct a deterministic queue TM to semidecide the language L = fw^Rcw : w 2 fa; bg g. Your solution to this option will be considered as a bonus, provide a solution if you want to get extra points.

You may invent your own graphical notation of the queue TM. (bonus: 10 pts)

Question 7 (20 pts)

Another variant of the Turing Machine can be de ned as a deterministic TM where you can read the character at the front and rear positions of the input string on the tape, and perform insertion of new cells initialized with a character in the alphabet and deletion of existing cells only at the front and rear positions. Call this TM the insert-delete TM and assume that it does not have any additional functionality other than those mentioned.

1. De ne the insert-delete TM as a tuple, stating the type of each constituent and identifying their

functionalities. (5 pts)

b. De ne the notion of con guration for the insert-delete TM. (2 pts)

3. De ne the yields-in-one-step relation of the machine. Write in set notation the language recog-

nized by the re exive transitive closure of yields-in-one-step relation. (4 pts)

4. Prove that the insert-delete TM is equivalent to the standard TM. Write down how each case should

be proved without going over every possible detail. (9 pts)

Question 8 (10 pts)

Construct an unrestricted grammar that generates the language

L = fa^f(n) : f(n) = ⁿ_i=0i²; n 2 Ng.

(Note that n² = 1 + 3 + ::: + (2n 1) for n 2 N f 0; 1g.)

Question 9 (8 pts)

Let L₁, L₂, and L₃ be recursively enumerable languages. Prove that the language L = (L₁L₂) \ L₃ is a recursively enumerable language by devising a nondeterministic TM that semidecides L utilizing TM’s for L₁, L₂, and L₃.

Question 10 (not graded)

Prove that L is not recursively enumerable where

L = f\M”\w” : \M” is encoding of a Turing machine and w 62L(M)g:

Submission

• You should submit your THE3 as a pdf le with the identi er ‘the3.pdf’ on odtuclass. You may use the provided .tex template with appropriate modi cations.

• Name your Turnitin submission in the format <id> <first-name> <last-name>.

• Late Submission: You have two days in total for late submission with penalties of 20 pts and 50 pts reduction in your grade for the rst and second day, respectively. No further submissions are accepted.

• Do not submit solutions for not graded questions.

Regulations

1. Cheating: This take-home exam has to be completed and submitted individually. Teaming up, sharing solutions anywhere other parties might access and using work belonging to others as part or in whole are considered cheating. We have zero tolerance policy for cheating. People involved in cheating will be punished in accordance with the university regulations.

2. Newsgroup: You must follow the newsgroup (cow.ceng.metu.edu.tr) for discussions and possible updates on a daily basis. You are advised to initiate discussions on COW so that most parties will bene t.

5