Recent questions tagged peter-linz / GATE Overflow for GATE CSE

0 votes

0 answers

211

Peter Linz Edition 5 Exercise 9.2 Question 5(d) (Page No. 245)
Provide a “high-level” description for Turing machines that accept the following languages on $\{a,b\}$. For each problem, define a set of appropriate macroinstructions that you feel are reasonably easy to implement. Then use them for the solution. $L = \{a^nb^m : m = n^2,n\geq1\}.$

Provide a “high-level” description for Turing machines that accept the following languages on $\{a,b\}$. For each problem, define a set of appropriate macroinstructio...

Rishi yadav

166 views

Rishi yadav asked Apr 9, 2019

0 votes

0 answers

212

Peter Linz Edition 5 Exercise 9.2 Question 5(c) (Page No. 245)
Provide a “high-level” description for Turing machines that accept the following languages on $\{a,b\}.$ For each problem, define a set of appropriate macroinstructions that you feel are reasonably easy to implement. Then use them for the solution. $\text{The complement of the language in }L = \{ww^R\}.$

Provide a “high-level” description for Turing machines that accept the following languages on $\{a,b\}.$ For each problem, define a set of appropriate macroinstructio...

Rishi yadav

231 views

Rishi yadav asked Apr 9, 2019

0 votes

0 answers

213

Peter Linz Edition 5 Exercise 9.2 Question 5(b) (Page No. 245)
Provide a “high-level” description for Turing machines that accept the following languages on $\{a,b\}.$ For each problem, define a set of appropriate macroinstructions that you feel are reasonably easy to implement. Then use them for the solution. $L = \{w_1w_2: w_1 \neq w_2: |w_1| = |w_2|\}.$

Provide a “high-level” description for Turing machines that accept the following languages on $\{a,b\}.$ For each problem, define a set of appropriate macroinstructio...

Rishi yadav

121 views

Rishi yadav asked Apr 9, 2019

0 votes

0 answers

214

Peter Linz Edition 5 Exercise 9.2 Question 5(a) (Page No. 244)
Provide a “high-level” description for Turing machines that accept the following languages on $\{a,b\}.$ For each problem, define a set of appropriate macroinstructions that you feel are reasonably easy to implement. Then use them for the solution. $L = \{ww^R\}.$

Provide a “high-level” description for Turing machines that accept the following languages on $\{a,b\}.$ For each problem, define a set of appropriate macroinstructio...

Rishi yadav

206 views

Rishi yadav asked Apr 9, 2019

0 votes

0 answers

215

Peter Linz Edition 5 Exercise 9.2 Question 4 (Page No. 244)
Use a block diagram to sketch the implementation of a function f defined for all $w_1,w_2,w_3\in \{1\}^+$ by $f(w_1,w_2,w_3) = i,$ where $i$ is such that $|w_i| = \text{max}(|w_1|,|w_2|,|w_3|)$ if no two $w’s$ have the same length, and $i=0$ otherwise.

Use a block diagram to sketch the implementation of a function f defined for all $w_1,w_2,w_3\in \{1\}^+$ by ...

Rishi yadav

144 views

Rishi yadav asked Apr 9, 2019

0 votes

0 answers

216

Peter Linz Edition 5 Exercise 9.2 Question 3(d) (Page No. 244)
Using adders, subtracters, comparers, copies or multipliers, draw block diagrams for Turing machines that compute the functions for all positive integers $n$ $f(n) = n!,$

Using adders, subtracters, comparers, copies or multipliers, draw block diagrams for Turing machines that compute the functions for all positive integers $n$ ...

Rishi yadav

278 views

Rishi yadav asked Apr 9, 2019

0 votes

0 answers

217

Peter Linz Edition 5 Exercise 9.2 Question 3(e) (Page No. 244)
Using adders, subtracters, comparers, copiers or multipliers, draw block diagrams for Turing machines that compute the functions for all positive integers $n$ $f(n) = n^{n!},$

Using adders, subtracters, comparers, copiers or multipliers, draw block diagrams for Turing machines that compute the functions for all positive integers $n$ ...

Rishi yadav

303 views

Rishi yadav asked Apr 9, 2019

0 votes

0 answers

218

Peter Linz Edition 5 Exercise 9.2 Question 3(c) (Page No. 244)
Using adders, subtracters, comparers, copies or multipliers, draw block diagrams for Turing machines that compute the functions for all positive integers $n$ $f(n) = 2^n,$

Using adders, subtracters, comparers, copies or multipliers, draw block diagrams for Turing machines that compute the functions for all positive integers $n$ ...

Rishi yadav

410 views

Rishi yadav asked Apr 9, 2019

0 votes

0 answers

219

Peter Linz Edition 5 Exercise 9.2 Question 3(b) (Page No. 244)
Using adders, subtracters, comparers, copies or multipliers, draw block diagrams for Turing machines that compute the functions for all positive integers $n$ $f(n) = n^5,$

Using adders, subtracters, comparers, copies or multipliers, draw block diagrams for Turing machines that compute the functions for all positive integers $n$ ...

Rishi yadav

212 views

Rishi yadav asked Apr 9, 2019

0 votes

0 answers

220

Peter Linz Edition 5 Exercise 9.2 Question 3(a) (Page No. 244)
Using adders, subtracters, comparers, copies or multipliers, draw block diagrams for Turing machines that compute the functions for all positive integers $n$ $f(n) = n(n+1),$

Using adders, subtracters, comparers, copies or multipliers, draw block diagrams for Turing machines that compute the functions for all positive integers $n$ ...

Rishi yadav

282 views

Rishi yadav asked Apr 9, 2019

1 votes

0 answers

221

Peter Linz Edition 5 Exercise 9.2 Question 2 (Page No. 244)
Establish a convention for representing positive and negative integers in unary notation. With your convention, sketch the construction of a subtracter for computing $x-y.$

Establish a convention for representing positive and negative integers in unary notation. With your convention, sketch the construction of a subtracter for computing $x-y...

Rishi yadav

194 views

Rishi yadav asked Apr 9, 2019

0 votes

0 answers

222

Peter Linz Edition 5 Exercise 9.2 Question 1 (Page No. 244)
$\text{Example}:$ Design a Turing machine that multiples two positive integers in unary notation. Write out the complete solution to Example.

$\text{Example}:$ Design a Turing machine that multiples two positive integers in unary notation.Write out the complete solution to Example.

Rishi yadav

172 views

Rishi yadav asked Apr 9, 2019

0 votes

0 answers

223

Peter Linz Edition 5 Exercise 9.1 Question 19 (Page No. 240)
You may have noticed that all the examples in these sections had only one final state. Is it generally true that for any Turing machine, there exists another one with only one final state that accepts the same language$?$

You may have noticed that all the examples in these sections had only one final state. Is it generally true that for any Turing machine, there exists another one with onl...

Rishi yadav

173 views

Rishi yadav asked Apr 9, 2019

0 votes

0 answers

224

Peter Linz Edition 5 Exercise 9.1 Question 18 (Page No. 240)
$\text{Example}:$ Given two positive integers $x$ and $y$, design a Turing machine that computes $x+y$. Sketch how Example could be solved if $x$ and $y$ were represented in decimal.

$\text{Example}:$ Given two positive integers $x$ and $y$, design a Turing machine that computes $x+y$.Sketch how Example could be solved if $x$ and $y$ were represented ...

Rishi yadav

286 views

Rishi yadav asked Apr 6, 2019

0 votes

0 answers

225

Peter Linz Edition 5 Exercise 9.1 Question 17 (Page No. 239)
$\text{Example}:$ Given two positive integers $x$ and $y,$ design a Turing machine that computes $x+y$. Suppose that in Example we had decided to represent $x$ and $y$ in binary. Write a Turing machine program for doing the indicated computation in this representation

$\text{Example}:$ Given two positive integers $x$ and $y,$ design a Turing machine that computes $x+y$.Suppose that in Example we had decided to represent $x$ and $y$ in ...

Rishi yadav

239 views

Rishi yadav asked Apr 6, 2019

0 votes

0 answers

226

Peter Linz Edition 5 Exercise 9.1 Question 16 (Page No. 239)
$\text{Example}:$ Let $x$ and $y$ be two positive integers represented in unary notation. Construct a Turing machine that will halt in a final state $q_y$ if $x\geq y,$ and that will halt in a nonfinal state $q_n$ if $x < y.$ More ... $q_0w(x)0w(y) \vdash^* q_nw(x)0w(y)$ if $x < y$, Complete all the details in Example

$\text{Example}:$ Let $x$ and $y$ be two positive integers represented in unary notation. Construct a Turing machine that will halt in a final state $q_y$ if $x\geq y,$ a...

Rishi yadav

572 views

Rishi yadav asked Apr 6, 2019

0 votes

0 answers

227

Peter Linz Edition 5 Exercise 9.1 Question 15 (Page No. 239)
$\text{Example}:$ Design a Turing machine that copies strings of $1’s$. More precisely, find a machine that performs the computation $q_0w \vdash^* q_fww,$ for any $w\in\{1\}^+$. Give convincing arguments that the Turing machine in Example does in fact carry out the indicated computation$.$

$\text{Example}:$ Design a Turing machine that copies strings of $1’s$. More precisely, find a machine that performs the computation ...

Rishi yadav

162 views

Rishi yadav asked Apr 6, 2019

0 votes

0 answers

228

Peter Linz Edition 5 Exercise 9.1 Question 14 (Page No. 239
$\text{Example}:$ Design a Turing machine that copies strings of $1's$. More precisely, find a machine that performs the computation $q_0w \vdash^* q_fww,$ for any $w\in\{1\}^+$. Give the sequence of instantaneous ... through when presented with the input $111$. What happens when this machine is started with $110$ on its tape$?$

$\text{Example}:$ Design a Turing machine that copies strings of $1’s$. More precisely, find a machine that performs the computation ...

Rishi yadav

275 views

Rishi yadav asked Apr 6, 2019

0 votes

0 answers

229

Peter Linz Edition 5 Exercise 9.1 Question 13 (Page No. 239)
$\text{Example}:$ Design a Turing machine that accepts $L = \{a^nb^nc^n:n\geq 1\}$. Write out a complete solution for Example.

$\text{Example}:$ Design a Turing machine that accepts $L = \{a^nb^nc^n:n\geq 1\}$.Write out a complet...

Rishi yadav

186 views

Rishi yadav asked Apr 6, 2019

0 votes

0 answers

230

Peter Linz Edition 5 Exercise 9.1 Question 12 (Page No. 239)
Design a Turing machine $\Gamma = \{0,1,\square\}$ that, when started on any cell containing a blank or $a\space 1$, will halt if and only if its tape has a $0$ somewhere it.

Design a Turing machine $\Gamma = \{0,1,\square\}$ that, when started on any cell containing a blank or $a\space 1$, will halt if and only if its tape has a $0$ somewhere...

Rishi yadav

371 views

Rishi yadav asked Apr 6, 2019

0 votes

0 answers

231

Peter Linz Edition 5 Exercise 9.1 Question 11(f) (Page No. 239)
Design Turing machines to compute the following functions for $x$ and $y$ positive integers represented in unary. $f(x) = \lfloor{\frac{x}{2}}\rfloor,$ where $\lfloor{\frac{x}{2}}\rfloor,$ denotes the largest integer less than or equal to $\frac{x}{2}.$

Design Turing machines to compute the following functions for $x$ and $y$ positive integers represented in unary.$f(x) = \lfloor{\frac{x}{2}}\rfloor,$ where $\lfloor{\fra...

Rishi yadav

344 views

Rishi yadav asked Apr 6, 2019

0 votes

0 answers

232

Peter Linz Edition 5 Exercise 9.1 Question 11(e) (Page No. 239)
Design Turing machines to compute the following functions for $x$ and $y$ positive integers represented in unary. $f(x) = x \text { mod } 5. $

Design Turing machines to compute the following functions for $x$ and $y$ positive integers represented in unary. ...

Rishi yadav

367 views

Rishi yadav asked Apr 6, 2019

2 votes

0 answers

233

Peter Linz Edition 5 Exercise 9.1 Question 11(d) (Page No. 239)
Design Turing machines to compute the following functions for $x$ and $y$ positive integers represented in unary $f(x) =\frac{x}{2},$ if $x$ is even, $ = \frac{x+1}{2},$ if $x$ is odd.

Design Turing machines to compute the following functions for $x$ and $y$ positive integers represented in unary ...

Rishi yadav

897 views

Rishi yadav asked Apr 6, 2019

0 votes

0 answers

234

Peter Linz Edition 5 Exercise 9.1 Question 11(c) (Page No. 239)
Design Turing machines to compute the following functions for $x$ and $y$ positive integers represented in unary $f(x,y) = 2x+3y$.

Design Turing machines to compute the following functions for $x$ and $y$ positive integers represented in unary ...

Rishi yadav

1.1k views

Rishi yadav asked Apr 6, 2019

0 votes

0 answers

235

Peter Linz Edition 5 Exercise 9.1 Question 11(b) (Page No. 239)
Design Turing machines to compute the following functions for $x$ and $y$ positive integers represented in unary. $f(x,y) = x-y,$ $x>y,$ $= 0,$ $x\leq y$.

Design Turing machines to compute the following functions for $x$ and $y$ positive integers represented in unary. ...

Rishi yadav

287 views

Rishi yadav asked Apr 6, 2019

0 votes

0 answers

236

Peter Linz Edition 5 Exercise 9.1 Question 11(a) (Page No. 239)
Design Turing machines to compute the following functions for $x$ and $y$ positive integers represented in unary. $f(x) = 3x$

Design Turing machines to compute the following functions for $x$ and $y$ positive integers represented in unary. ...

Rishi yadav

239 views

Rishi yadav asked Apr 6, 2019

0 votes

0 answers

237

Peter Linz Edition 5 Exercise 9.1 Question 10 (Page No. 239)
Design a Turing machine that finds the middle of a string of even length. Specifically, if $w = a_1a_2...a_na_{n+1}...a_{2n},$ with $a_i\in\Sigma,$ the Turing machine should produce $\widehat{w} = a_1a_2...a_nca_{n+1}...a_{2n},$ where $c\in\Gamma-\Sigma$.

Design a Turing machine that finds the middle of a string of even length. Specifically, if $w = a_1a_2...a_na_{n+1}...a_{2n},$ with $a_i\in\Sigma,$ the Turing machine sho...

Rishi yadav

149 views

Rishi yadav asked Apr 6, 2019

0 votes

0 answers

238

Peter Linz Edition 5 Exercise 9.1 Question 9 (Page No. 239)
Construct a Turing machine to compute the function $f(w) = w^R$, where $w\in \{0,1\}^+$.

Construct a Turing machine to compute the function $f(w) = w^R$,where $w\in \{0,1\...

Rishi yadav

127 views

Rishi yadav asked Apr 6, 2019

0 votes

0 answers

239

Peter Linz Edition 5 Exercise 9.1 Question 8 (Page No. 239)
Design a Turing machine that accepts the language. $L = \Big\{ww:w\in \{a,b\}^+\Big\}$.

Design a Turing machine that accepts the language. $L = \Big\{ww:w\in \{a,b\}^+\Big\}$.

Rishi yadav

111 views

Rishi yadav asked Apr 6, 2019

0 votes

0 answers

240

Peter Linz Edition 5 Exercise 9.1 Question 7(h) (Page No. 239)
Construct Turing machines that will accept the following languages on $\{a,b\}$ $L = \{a^nb^{2n}:n\geq 0\}$.

Construct Turing machines that will accept the following languages on $\{a,b\}$ $L = \{a^nb^{2n}:n\geq 0\...

Rishi yadav

186 views

Rishi yadav asked Apr 6, 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