Recent questions

0 votes

0 answers

1

Michael Sipser Edition 3 Exercise 4 Question 4 (Page No. 211)
Let $A\varepsilon_{CFG} = \{ \langle{ G }\rangle \mid G\: \text{is a CFG that generates}\: \epsilon \}.$Show that $A\varepsilon_{CFG}$ is decidable.

asked 8 hours ago in Theory of Computation by Lakshman Patel RJIT Veteran (50.9k points) | 2 views

0 votes

0 answers

2

Michael Sipser Edition 3 Exercise 4 Question 3 (Page No. 211)
Let $ALL_{DFA} = \{ \langle{ A }\rangle \mid A \text{ is a DFA and}\: L(A) = \Sigma^{\ast}\}.$ Show that $ALL_{DFA}$ is decidable.

asked 8 hours ago in Theory of Computation by Lakshman Patel RJIT Veteran (50.9k points) | 2 views

0 votes

0 answers

3

Michael Sipser Edition 3 Exercise 4 Question 2 (Page No. 211)
Consider the problem of determining whether a DFA and a regular expression are equivalent. Express this problem as a language and show that it is decidable.

asked 8 hours ago in Theory of Computation by Lakshman Patel RJIT Veteran (50.9k points) | 1 view

0 votes

0 answers

4

Michael Sipser Edition 3 Exercise 4 Question 1 (Page No. 210)

asked 8 hours ago in Theory of Computation by Lakshman Patel RJIT Veteran (50.9k points) | 2 views

0 votes

0 answers

5

Michael Sipser Edition 3 Exercise 3 Question 22 (Page No. 190)
Let $A$ be the language containing only the single string $s$ ... of this problem, assume that the question of whether life will be found on Mars has an unambiguous $YES$ or $NO$ answer.

asked 8 hours ago in Theory of Computation by Lakshman Patel RJIT Veteran (50.9k points) | 1 view

0 votes

0 answers

6

Michael Sipser Edition 3 Exercise 3 Question 21 (Page No. 190)
Let $c_{1}x^{n} + c_{2}x^{n-1} + \dots + c_{n}x + c_{n+1}$ be a polynomial with a root at $x = x_{0}.$ Let $c_{max}$ be the largest absolute value of a $c_{i}.$ Show that $\mid x_{0} \mid < (n+1)\frac{c_{max}}{\mid c_{1} \mid}.$

asked 8 hours ago in Theory of Computation by Lakshman Patel RJIT Veteran (50.9k points) | 1 view

0 votes

0 answers

7

Michael Sipser Edition 3 Exercise 3 Question 20 (Page No. 190)
Show that single-tape $TMs$ that cannot write on the portion of the tape containing the input string recognize only regular languages.

asked 8 hours ago in Theory of Computation by Lakshman Patel RJIT Veteran (50.9k points) | 1 view

0 votes

0 answers

8

Michael Sipser Edition 3 Exercise 3 Question 19 (Page No. 190)
Show that every infinite Turing-recognizable language has an infinite decidable subset.

asked 8 hours ago in Theory of Computation by Lakshman Patel RJIT Veteran (50.9k points) | 1 view

0 votes

0 answers

9

Michael Sipser Edition 3 Exercise 3 Question 18 (Page No. 190)
Show that a language is decidable iff some enumerator enumerates the language in the standard string order.

asked 8 hours ago in Theory of Computation by Lakshman Patel RJIT Veteran (50.9k points) | 1 view

0 votes

0 answers

10

Michael Sipser Edition 3 Exercise 3 Question 17 (Page No. 189)
Let $B = \{\langle {M_{1}\rangle},\langle{ M_{1}\rangle} , \dots \}$ be a Turing-recognizable language consisting of $TM$ descriptions. Show that there is a decidable language $C$ consisting of $TM$ descriptions such that every machine described in $B$ has an equivalent machine in $C$ and vice versa.

asked 8 hours ago in Theory of Computation by Lakshman Patel RJIT Veteran (50.9k points) | 1 view

0 votes

0 answers

11

Michael Sipser Edition 3 Exercise 3 Question 16 (Page No. 189)
Show that the collection of Turing-recognizable languages is closed under the operation of union. concatenation. star. intersection. homomorphism.

asked 8 hours ago in Theory of Computation by Lakshman Patel RJIT Veteran (50.9k points) | 2 views

0 votes

0 answers

12

Michael Sipser Edition 3 Exercise 3 Question 15 (Page No. 189)
Show that the collection of decidable languages is closed under the operation of union. concatenation. star. complementation. intersection.

asked 8 hours ago in Theory of Computation by Lakshman Patel RJIT Veteran (50.9k points) | 1 view

0 votes

0 answers

13

Michael Sipser Edition 3 Exercise 3 Question 14 (Page No. 189)
A queue automaton is like a push-down automaton except that the stack is replaced by a queue. A queue is a tape allowing symbols to be written only on the left-hand end and read only at the right-hand end. ... at any time. Show that a language can be recognized by a deterministic queue automaton iff the language is Turing-recognizable.

asked 8 hours ago in Theory of Computation by Lakshman Patel RJIT Veteran (50.9k points) | 1 view

0 votes

0 answers

14

Michael Sipser Edition 3 Exercise 3 Question 13 (Page No. 189)
A Turing machine with stay put instead of left is similar to an ordinary Turing machine, but the transition function has the form $\delta: Q\times \Gamma \rightarrow Q\times \Gamma \times \{R,S\}$ At each ... that this Turing machine variant is not equivalent to the usual version. What class of languages do these machines recognize?

asked 8 hours ago in Theory of Computation by Lakshman Patel RJIT Veteran (50.9k points) | 1 view

0 votes

0 answers

15

Michael Sipser Edition 3 Exercise 3 Question 12 (Page No. 189)
A Turing machine with left reset is similar to an ordinary Turing machine, but the transition function has the form $\delta: Q\times \Gamma \rightarrow Q\times \Gamma \times \{R,RESET\}$ ... to move the head one symbol left. Show that Turing machines with left reset recognize the class of Turing-recognizable languages.

asked 8 hours ago in Theory of Computation by Lakshman Patel RJIT Veteran (50.9k points) | 1 view

0 votes

0 answers

16

Michael Sipser Edition 3 Exercise 3 Question 11 (Page No. 189)
A Turing machine with doubly infinite tape is similar to an ordinary Turing machine, but its tape is infinite to the left as well as to the right. The tape is initially filled with blanks except for the portion ... tape as it moves leftward. Show that this type of Turing machine recognizes the class of Turing-recognizable languages.

asked 9 hours ago in Theory of Computation by Lakshman Patel RJIT Veteran (50.9k points) | 1 view

0 votes

0 answers

17

Michael Sipser Edition 3 Exercise 3 Question 10 (Page No. 188)
Say that a write-once Turing machine is a single-tape TM that can alter each tape square at most once (including the input portion of the tape). Show that this variant Turing machine model is equivalent to the ordinary Turing ... , consider the case whereby the Turing machine may alter each tape square at most twice. Use lots of tape.)

asked 9 hours ago in Theory of Computation by Lakshman Patel RJIT Veteran (50.9k points) | 1 view

0 votes

0 answers

18

Michael Sipser Edition 3 Exercise 3 Question 9 (Page No. 188)
Let a $k-PDA$ be a pushdown automaton that has $k$ stacks. Thus a $0-PDA$ is an $NFA$ and a $1-PDA$ is a conventional $PDA$. You already know that $1-PDAs$ are more powerful (recognize a larger class of languages) than ... $3-PDAs$ are not more powerful than $2-PDAs$. (Hint: Simulate a Turing machine tape with two stacks.)

asked 9 hours ago in Theory of Computation by Lakshman Patel RJIT Veteran (50.9k points) | 1 view

0 votes

0 answers

19

Michael Sipser Edition 3 Exercise 3 Question 8 (Page No. 188)
Give implementation-level descriptions of Turing machines that decide the following languages over the alphabet $\{0,1\}$. $\{w \mid w \text{contains an equal number of 0s and 1s}\}$ $\{w \mid w \text{contains twice as many 0s as 1s}\}$ $\{w \mid w \text{does not contain twice as many 0s as 1s}\}$

asked 9 hours ago in Theory of Computation by Lakshman Patel RJIT Veteran (50.9k points) | 1 view

0 votes

0 answers

20

Michael Sipser Edition 3 Exercise 3 Question 7 (Page No. 188)
Explain why the following is not a description of a legitimate Turing machine. $M_{bad} = $ On input $\langle p \rangle,$ a polynomial over variables $x_{1},\dots,x_{k}:$ ... . Evaluate $p$ on all of these settings. If any of these settings evaluates to $0$, accept; otherwise, reject.$ $

asked 9 hours ago in Theory of Computation by Lakshman Patel RJIT Veteran (50.9k points) | 1 view

0 votes

0 answers

21

Michael Sipser Edition 3 Exercise 3 Question 6 (Page No. 188)
In Theorem $3.21$, we showed that a language is Turing-recognizable iff some enumerator enumerates it. Why didn't we use the following simpler algorithm for the forward direction of the proof? As before, $s_{1}, s_{2},\dots $ is a list of all strings in ... $i = 1,2,3,\dots.$ Run $M$ on $s_{i}.$ If it accepts, print out $s_{i}."$

asked 9 hours ago in Theory of Computation by Lakshman Patel RJIT Veteran (50.9k points) | 3 views

0 votes

0 answers

22

Michael Sipser Edition 3 Exercise 3 Question 5 (Page No. 188)
Examine the formal definition of a Turing machine to answer the following questions, and explain your reasoning. Can a Turing machine ever write the blank symbol $\sqcup$ on its tape? Can the tape alphabet $\Gamma$ be the ... head ever be in the same location in two successive steps? Can a Turing machine contain just a single state?

asked 3 days ago in Theory of Computation by Lakshman Patel RJIT Veteran (50.9k points) | 5 views

0 votes

1 answer

23

Michael Sipser Edition 3 Exercise 3 Question 4 (Page No. 187)
Give a formal definition of an enumerator. Consider it to be a type of two-tape Turing machine that uses its second tape as the printer. Include a definition of the enumerated language.

asked 3 days ago in Theory of Computation by Lakshman Patel RJIT Veteran (50.9k points) | 6 views

0 votes

0 answers

24

Michael Sipser Edition 3 Exercise 3 Question 3 (Page No. 187)
Modify the proof of Theorem $3.16$ to obtain Corollary $3.19$, showing that a language is decidable iff some nondeterministic Turing machine decides it. (You may assume the following theorem about trees. If every node in a ... many children and every branch of the tree has finitely many nodes, the tree itself has finitely many nodes.)

asked 3 days ago in Theory of Computation by Lakshman Patel RJIT Veteran (50.9k points) | 3 views

0 votes

0 answers

25

Michael Sipser Edition 3 Exercise 3 Question 2 (Page No. 187)
This exercise concerns $TM\: M_{1}$, whose description and state diagram appear in Example $3.9$. In each of the parts, give the sequence of configurations that $M_{1}$ enters when started on the indicated input string. $11$ $1\#1$ $1\#\#1$ $10\#11$ $10\#10$

asked 3 days ago in Theory of Computation by Lakshman Patel RJIT Veteran (50.9k points) | 3 views

0 votes

0 answers

26

Michael Sipser Edition 3 Exercise 3 Question 1 (Page No. 187)
This exercise concerns $TM\: M_{2}$, whose description and state diagram appear in Example $3.7$. In each of the parts, give the sequence of configurations that $M_{2}$ enters when started on the indicated input string. $0$ $00$ $000$ $000000$

asked 3 days ago in Theory of Computation by Lakshman Patel RJIT Veteran (50.9k points) | 2 views

0 votes

0 answers

27

Michael Sipser Edition 3 Exercise 2 Question 59 (Page No. 160)
If we disallow $\epsilon$-rules in CFGs, we can simplify the DK-test. In the simplified test,we only need to check that each of DK’s accept states has a single rule. Prove that a CFG without $\epsilon$-rules passes the simplified DK-test iff it is a DCFG.

asked 3 days ago in Theory of Computation by Lakshman Patel RJIT Veteran (50.9k points) | 2 views

0 votes

0 answers

28

Michael Sipser Edition 3 Exercise 2 Question 58 (Page No. 160)
Let $C = \{ww^{R} \mid w in \{0,1\}^{\ast}\}$. Prove that $C$ is not a DCFL. (Hint: Suppose that when some DPDA $P$ is started in state $q$ with symbol $x$ on the top of its stack, $P$ never pops its ... of $P's$ stack at that point cannot affect its subsequent behavior, so $P's$ subsequent behavior can depend only on $q$ and $x$.)

asked 3 days ago in Theory of Computation by Lakshman Patel RJIT Veteran (50.9k points) | 3 views

+1 vote

1 answer

29

Michael Sipser Edition 3 Exercise 2 Question 57 (Page No. 160)
Let $B = \{a^{i}b^{j}c^{k}\mid i,j,k \geq 0\: \text{and}\: i = j\: \text{or}\: i = k \}$. Prove that $B$ is not a DCFL.

asked 3 days ago in Theory of Computation by Lakshman Patel RJIT Veteran (50.9k points) | 8 views

0 votes

0 answers

30

Michael Sipser Edition 3 Exercise 2 Question 56 (Page No. 160)
Let $A = L(G_{1})$ where $G_{1}$ is defined in Question $2.55$. Show that $A$ is not a DCFL.(Hint: Assume that $A$ is a DCFL and consider its DPDA $P$. Modify $P$ ... an accept state, it pretends that $c's$ are $b's$ in the input from that point on. What language would the modified $P$ accept?)

asked 3 days ago in Theory of Computation by Lakshman Patel RJIT Veteran (50.9k points) | 2 views

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

Recent Posts

Recent Blog Comments