Recent questions tagged turing-machine / GATE Overflow for GATE CSE

A counter is a stack with an alphabet of exactly two symbols a stack start symbol and a counter symbol. Only the counter symbol can be put on the stack or removed from it...

Rishi yadav

203 views

Rishi yadav asked Mar 28, 2019

0 votes

0 answers

217

Peter Linz Edition 5 Exercise 10.2 Question 4 (Page No. 264)
Give a formal definition of a Turing machine with a single tape but multiple control units, each with a single read-write head. Show how such a machine can be simulated with a multitape machine.

Give a formal definition of a Turing machine with a single tape but multiple control units, each with a single read-write head. Show how such a machine can be simulated w...

Rishi yadav

171 views

Rishi yadav asked Mar 28, 2019

0 votes

0 answers

218

Peter Linz Edition 5 Exercise 10.2 Question 3 (Page No. 264)
Give a formal definition of a multihead-multitape Turing machine. Then show how such a machine can be simulated by a standard Turing machine.

Give a formal definition of a multihead-multitape Turing machine. Then show how such a machine can be simulated by a standard Turing machine.

Rishi yadav

167 views

Rishi yadav asked Mar 28, 2019

0 votes

0 answers

219

Peter Linz Edition 5 Exercise 10.1 Question 11 (Page No. 259)
Consider a Turing machine with a different decision process in which transitions are made if the current tape symbol is not one of the specified set. For example, $\delta(q_i,\{a,b\})=(q_j,c,R)$ will allow the ... neither $a$ nor $b$. Formalize this concept and show that this modification is equivalent to a standard Turing machine.

Consider a Turing machine with a different decision process in which transitions are made if the current tape symbol is not one of the specified set. For example, ...

Rishi yadav

206 views

Rishi yadav asked Mar 28, 2019

0 votes

0 answers

220

Peter Linz Edition 5 Exercise 10.1 Question 10 (Page No. 259)
Consider a version of the standard Turing machine in which transitions can depend not only on the cell directly under the read-write head but also on the cells to the immediate right and left. Make a formal definition of such a machine, then sketch its simulation by a standard Turing machine.

Consider a version of the standard Turing machine in which transitions can depend not only on the cell directly under the read-write head but also on the cells to the imm...

Rishi yadav

169 views

Rishi yadav asked Mar 28, 2019

0 votes

0 answers

221

Peter Linz Edition 5 Exercise 10.1 Question 9 (Page No. 259)
Suppose we make the restriction that a Turing must always write a symbol different from the one it reads, that is, if $\delta(q_i,a)=(q_j,b,L\space or\space R)$, then $a$ and $b$ must be different. Does this limitation reduce the power of the automaton $?$

Suppose we make the restriction that a Turing must always write a symbol different from the one it reads, that is, if ...

Rishi yadav

167 views

Rishi yadav asked Mar 28, 2019

0 votes

0 answers

222

Peter Linz Edition 5 Exercise 10.1 Question 8 (Page No. 259)
Suppose we make the requirement that a Turing machine can halt only in a final state, that is, we ask that $\delta(q, a)$ be defined for all pairs $(q, a)$ with $a\in \Gamma$ and $q\notin F$. Does this restrict the power of the Turing machine?

Suppose we make the requirement that a Turing machine can halt only in a final state, that is, we ask that $\delta(q, a)$ be defined for all pairs $(q, a)$ with $a\in \Ga...

Rishi yadav

157 views

Rishi yadav asked Mar 28, 2019

0 votes

0 answers

223

Peter Linz Edition 5 Exercise 10.1 Question 7 (Page No. 259)
Consider a Turing machine that cannot write blanks; that is, for all $\delta (q_i,a)=(q_j,b,L\space)$, $b$ must be in $\Gamma-\{\square\}$. Show how such a machine can simulate a standard Turing machine.

Consider a Turing machine that cannot write blanks; that is, for all $\delta (q_i,a)=(q_j,b,L\space)$, $b$ must be in $\Gamma-\{\square\}$. Show how such a machine can si...

Rishi yadav

165 views

Rishi yadav asked Mar 28, 2019

0 votes

0 answers

224

Peter Linz Edition 5 Exercise 10.1 Question 6 (Page No. 259)
A nonerasing Turing machine is one that cannot change a nonblank symbol to a blank. This can be achieved by the restriction that if $\delta (q_i,a)=(q_j,\square ,L \space or \space R),$ then $a$ must be $\square$. Show that no generality is lost by making much a restriction.

A nonerasing Turing machine is one that cannot change a nonblank symbol to a blank. This can be achieved by the restriction that if ...

Rishi yadav

244 views

Rishi yadav asked Mar 28, 2019

0 votes

0 answers

225

Peter Linz Edition 5 Exercise 10.1 Question 5 (Page No. 259)
Consider a model of a Turing machine in which each move permits the read-write head to travel more than one cell to the left or right, the distance and direction of travel being one of the arguments of $\delta$. Give a precise definition of such an automaton and sketch a simulation of it by a standard Turing machine.

Consider a model of a Turing machine in which each move permits the read-write head to travel more than one cell to the left or right, the distance and direction of trave...

Rishi yadav

178 views

Rishi yadav asked Mar 28, 2019

0 votes

0 answers

226

Peter Linz Edition 5 Exercise 10.1 Question 4 (Page No. 259)
Consider a Turing machine that, on any particular move, can either change the top symbol or move the read-write head, but not both. $(a)$ Give a formal definition of such a machine. $(b)$ Show that the class of such machines is equivalent to the class of standard Turing machines.

Consider a Turing machine that, on any particular move, can either change the top symbol or move the read-write head, but not both.$(a)$ Give a formal definition of such ...

Rishi yadav

299 views

Rishi yadav asked Mar 28, 2019

0 votes

0 answers

227

Peter Linz Edition 5 Exercise 10.1 Question 3 (Page No. 259)
Give convincing arguments that any language accepted by an off-line Turing machine is also accepted by some standard machine.

Give convincing arguments that any language accepted by an off-line Turing machine is also accepted by some standard machine.

Rishi yadav

146 views

Rishi yadav asked Mar 28, 2019

0 votes

0 answers

228

Peter Linz Edition 5 Exercise 10.1 Question 2 (Page No. 258)
Give a formal definition of an off-line Turing machine.

Give a formal definition of an off-line Turing machine.

Rishi yadav

141 views

Rishi yadav asked Mar 28, 2019

0 votes

0 answers

229

Peter Linz Edition 5 Exercise 10.1 Question 1 (Page No. 258)
Give a formal definition of a Turing machine with a semi-infinite tape. Then prove that the class of Turing machines with semi-infinite tape. Then prove the class of Turing machines with semi-infinite tape is equivalent to the class of standard Turing machines.

Give a formal definition of a Turing machine with a semi-infinite tape. Then prove that the class of Turing machines with semi-infinite tape. Then prove the class of Turi...

Rishi yadav

177 views

Rishi yadav asked Mar 28, 2019

1 votes

3 answers

230

Turing Machine Self Doubt
Can someone explain in details how set of all TM is countable?

Can someone explain in details how set of all TM is countable?

aditi19

612 views

aditi19 asked Mar 23, 2019

0 votes

0 answers

231

Peter Linz Edition 5 Exercise 11.3 Question 6 (Page No. 296)
Without explicitly constructing it, show that there exists a context-sensitive grammar for the language $L=\{www^R: w,u\in\{a,b\}^+,|w|\geq|u|\}$.

Without explicitly constructing it, show that there exists a context-sensitive grammar for the language $L=\{www^R: w,u\in\{a,b\}^+,|w|\geq|u|\}$.

Rishi yadav

261 views

Rishi yadav asked Mar 17, 2019

0 votes

0 answers

232

Peter Linz Edition 5 Exercise 11.3 Question 5 (Page No. 296)
$\text{Theorem}:$ Every context-sensitive language $L$ is recursive. For $m$ in Theorem, give explicit bounds for $m$ as a function of $|w|$ and $|V\cup T|$.

$\text{Theorem}:$ Every context-sensitive language $L$ is recursive.For $m$ in Theorem, give explicit bounds for $m$ as a function of $|w|$ and $|V\cup T|$.

Rishi yadav

154 views

Rishi yadav asked Mar 17, 2019

0 votes

0 answers

233

Peter Linz Edition 5 Exercise 11.3 Question 4 (Page No. 296)
Show that the family of context-sensitive languages is closed under reversal.

Show that the family of context-sensitive languages is closed under reversal.

Rishi yadav

131 views

Rishi yadav asked Mar 17, 2019

0 votes

0 answers

234

Peter Linz Edition 5 Exercise 11.3 Question 3 (Page No. 296)
Show that the family of context-sensitive languages is closed under union.

Show that the family of context-sensitive languages is closed under union.

Rishi yadav

144 views

Rishi yadav asked Mar 17, 2019

0 votes

0 answers

235

Peter Linz Edition 5 Exercise 11.3 Question 2 (Page No. 296)
Find context-sensitive grammars for the following languages. $(a)$ $L=\{w: n_a(w) = n_b(w) = n_c(w)\}$. $(b)$ $L=\{w: n_a(w) = n_b(w) < n_c(w)\}$.

Find context-sensitive grammars for the following languages.$(a)$ $L=\{w: n_a(w) = n_b(w) = n_c(w)\}$.$(b)$ $L=\{w: n_a(w) = n_b(w) < n_c(w)\}$.

Rishi yadav

161 views

Rishi yadav asked Mar 17, 2019

0 votes

0 answers

236

Peter Linz Edition 5 Exercise 11.3 Question 1 (Page No. 296)
Find the context-sensitive grammars for the following languages. $\text{(a)}$ $L=\{a^{n+1}b^nc^{n-1} : n\geq 1\}$. $\text{(b)}$ $L=\{a^{n}b^nc^{2n} : n\geq 1\}$. $\text{(c)}$ $L=\{a^{n}b^mc^{n}d^m : n\geq 1, m\geq1\}$. $\text{(d)}$ $L=\{ww : w\in \{a,b\}^+\}$. $\text{(e)}$ $L=\{a^{n}b^nc^{n}d^m : n\geq 1\}$.

Find the context-sensitive grammars for the following languages.$\text{(a)}$ $L=\{a^{n+1}b^nc^{n-1} : n\geq 1\}$.$\text{(b)}$ $L=\{a^{n}b^nc^{2n} : n\geq 1\}$.$\text{(c)}...

Rishi yadav

162 views

Rishi yadav asked Mar 17, 2019

0 votes

0 answers

237

Peter Linz Edition 5 Exercise 11.2 Question 9 (Page No. 290,291)
A grammar $G = (V, T, S, P)$ is called $\text{unrestricted }$ if all the production are of the form $u\rightarrow v$, where $u$ is nit $(V\cup T)^+$ and $v$ is int $(V\cup T)^*$ Some authors give ... the same as the one we use, in the sense that for every grammar of one type, there is an equivalent grammar of the other type.

A grammar $G = (V, T, S, P)$ is called $\text{unrestricted }$ if all the production are of the form ...

Rishi yadav

225 views

Rishi yadav asked Mar 17, 2019

0 votes

0 answers

238

Peter Linz Edition 5 Exercise 11.2 Question 8 (Page No. 290)
Every unrestricted grammar there exists an equivalent unrestricted grammar, all of whose productions have the form $u\rightarrow v,$ with $u,v\in (V \cup T)^+$ and $|u| \leq |v|$, or $A\rightarrow\lambda$ with $A\in V$ Show that the conclusion still holds if we add the further conditions $|u|\leq2$ and $|v|\leq2$

Every unrestricted grammar there exists an equivalent unrestricted grammar, all of whose productions have the form ...

Rishi yadav

167 views

Rishi yadav asked Mar 17, 2019

0 votes

0 answers

239

Peter Linz Edition 5 Exercise 11.2 Question 7 (Page No. 290)
Show that for every unrestricted grammar there exists an equivalent unrestricted grammar, all of whose productions have the form $u\rightarrow v,$ with $u,v\in (V \cup T)^+$ and $|u| \leq |v|$, or $A\rightarrow\lambda$ with $A\in V$

Show that for every unrestricted grammar there exists an equivalent unrestricted grammar, all of whose productions have the form ...

Rishi yadav

152 views

Rishi yadav asked Mar 17, 2019

1 votes

0 answers

240

Peter Linz Edition 5 Exercise 11.2 Question 6 (Page No. 290)
$\text{Theorem}:$ For every recursively enumerable language $L$, there exists an unrestricted grammar $G$, such that $L=L(G)$. Construct a Turing machine for $L(01(01)^*)$, then find an unrestricted grammar for it using the construction in Theorem. Give a derivation for $0101$ using the resulting grammar.

$\text{Theorem}:$ For every recursively enumerable language $L$, there exists an unrestricted grammar $G$, such that $L=L(G)$.Construct a Turing machine for $L(01(01)^*)$...

Rishi yadav

187 views

Rishi yadav asked Mar 17, 2019

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true