Recent questions and answers in Theory of Computation

+4 votes

3 answers

1

TOC SAMPLE PRACTICE
Determine the minimum height of parse tree in CNF for terminal string of length w, which is constructed by using CFG G (a) log2|w|+1 (b) log2|w| (c) log2|w|−1 (d) None of these

answered 1 day ago in Theory of Computation by dhruvil3 (11 points) | 987 views

0 votes

0 answers

2

Michael Sipser Edition 3 Exercise 5 Question 36 (Page No. 242)
Say that a $CFG$ is minimal if none of its rules can be removed without changing the language generated. Let $MIN_{CFG} = \{\langle G \rangle \mid \text{G is a minimal CFG}\}$. Show that $MIN_{CFG}$ is $T-$recognizable. Show that $MIN_{CFG}$ is undecidable.

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

+1 vote

0 answers

3

Michael Sipser Edition 3 Exercise 5 Question 35 (Page No. 242)
Say that a variable $A$ in $CFG \:G$ is necessary if it appears in every derivation of some string $w \in G$. Let $NECESSARY_{CFG} = \{\langle G, A\rangle \mid \text{A is a necessary variable in G}\}$. Show that $NECESSARY_{CFG}$ is Turing-recognizable. Show that $NECESSARY_{CFG} $is undecidable.

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

0 votes

0 answers

4

Michael Sipser Edition 3 Exercise 5 Question 34 (Page No. 241)
Let $X = \{\langle M, w \rangle \mid \text{M is a single-tape TM that never modifies the portion of the tape that contains the input $w$ } \}$ Is $X$ decidable? Prove your answer.

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

0 votes

0 answers

5

Michael Sipser Edition 3 Exercise 5 Question 33 (Page No. 241)
Consider the problem of determining whether a $PDA$ accepts some string of the form $\{ww \mid w \in \{0,1\}^{\ast} \}$ . Use the computation history method to show that this problem is undecidable.

asked 3 days ago in Theory of Computation by Lakshman Patel RJIT Veteran (51.5k points) | 1 view

0 votes

0 answers

6

Michael Sipser Edition 3 Exercise 5 Question 32 (Page No. 241)
Prove that the following two languages are undecidable. $OVERLAP_{CFG} = \{\langle G, H\rangle \mid \text{G and H are CFGs where}\: L(G) \cap L(H) \neq \emptyset\}$. $PREFIX-FREE_{CFG} = \{\langle G \rangle \mid \text{G is a CFG where L(G) is prefix-free}\}$.

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

0 votes

0 answers

7

Michael Sipser Edition 3 Exercise 5 Question 31 (Page No. 241)
Let $f(x)=\left\{\begin{matrix}3x+1 & \text{for odd}\: x& \\ \dfrac{x}{2} & \text{for even}\: x & \end{matrix}\right.$ for any natural number $x$. If you start with an integer $x$ and iterate $f$, you ... decidable by a $TM\: H$. Use $H$ to describe a $TM$ that is guaranteed to state the answer to the $3x + 1$ problem.

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

0 votes

0 answers

8

Michael Sipser Edition 3 Exercise 5 Question 30 (Page No. 241)
Use Rice’s theorem, to prove the undecidability of each of the following languages. $INFINITE_{TM} = \{\langle M \rangle \mid \text{M is a TM and L(M) is an infinite language}\}$. $\{\langle M \rangle \mid \text{M is a TM and }\:1011 \in L(M)\}$. $ ALL_{TM} = \{\langle M \rangle \mid \text{ M is a TM and}\: L(M) = Σ^{\ast} \}$.

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

0 votes

0 answers

9

Michael Sipser Edition 3 Exercise 5 Question 29 (Page No. 241)
Rice's theorem. Let $P$ be any nontrivial property of the language of a Turing machine. Prove that the problem of determining whether a given Turing machine's language has property $P$ is undecidable. In more formal ... that $P$ is an undecidable language. Show that both conditions are necessary for proving that $P$ is undecidable.

asked 3 days ago in Theory of Computation by Lakshman Patel RJIT Veteran (51.5k points) | 1 view

0 votes

0 answers

10

Michael Sipser Edition 3 Exercise 5 Question 28 (Page No. 241)
Rice's theorem. Let $P$ be any nontrivial property of the language of a Turing machine. Prove that the problem of determining whether a given Turing machine's language has property $P$ is undecidable. In more formal terms, let $P$ be a language ... $M_{1}$ and $M_{2}$ are any $TMs$. Prove that $P$ is an undecidable language.

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

0 votes

0 answers

11

Michael Sipser Edition 3 Exercise 5 Question 27 (Page No. 241)
A two-dimensional finite automaton $(2DIM-DFA)$ is defined as follows. The input is an $m \times n$ rectangle, for any $m, n \geq 2$ ... of determining whether two of these machines are equivalent. Formulate this problem as a language and show that it is undecidable.

asked 3 days ago in Theory of Computation by Lakshman Patel RJIT Veteran (51.5k points) | 1 view

0 votes

0 answers

12

Michael Sipser Edition 3 Exercise 5 Question 26 (Page No. 240)
Define a two-headed finite automaton $(2DFA)$ to be a deterministic finite automaton that has two read-only, bidirectional heads that start at the left-hand end of the input tape and can be independently controlled to move in either direction. The tape ... $E_{2DFA}$ is not decidable.

asked 3 days ago in Theory of Computation by Lakshman Patel RJIT Veteran (51.5k points) | 1 view

+1 vote

1 answer

13

Mod Machine
Can we have a mod- n machine with states less than n? Does it exist for a particular n?

answered 3 days ago in Theory of Computation by Shubhdhiman (11 points) | 101 views

+31 votes

5 answers

14

GATE2018-52
Given a language $L$, define $L^i$ as follows:$L^0 = \{ \varepsilon \}$$L^i = L^{i-1} \bullet L \text{ for all } I >0$The order of a language $L$ is defined as the smallest $k$ such that $L^k = L^{k+1}$. Consider the language $L_1$ (over alphabet O) accepted by the following automaton. The order of $L_1$ is ____

answered 4 days ago in Theory of Computation by JashanArora Junior (827 points) | 5.4k views

0 votes

0 answers

15

Michael Sipser Edition 3 Exercise 5 Question 25 (Page No. 240)
Give an example of an undecidable language $B$, where $B \leq_{m} \overline{B}$.

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

0 votes

0 answers

16

Michael Sipser Edition 3 Exercise 5 Question 24 (Page No. 240)
Let $J = \{w \mid \text{either $w = 0x$ for some $x \in A_{TM},$ or $w = 1y\:$ for some $y \in \overline{A_{TM}}\:\:$}\}$. Show that neither $J$ nor $\overline{J}$ is Turing-recognizable.

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

0 votes

0 answers

17

Michael Sipser Edition 3 Exercise 5 Question 23 (Page No. 240)
Show that $A$ is decidable iff $A \leq_{m} 0 ^{\ast} 1^{\ast}$ .

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

0 votes

0 answers

18

Michael Sipser Edition 3 Exercise 5 Question 22 (Page No. 240)
Show that $A$ is Turing-recognizable iff $A \leq_{m} A_{TM}$.

asked 4 days ago in Theory of Computation by Lakshman Patel RJIT Veteran (51.5k points) | 1 view

0 votes

0 answers

19

Michael Sipser Edition 3 Exercise 5 Question 21 (Page No. 240)
Let $AMBIG_{CFG} = \{\langle G \rangle \mid \text{G is an ambiguous CFG}\}$. Show that $AMBIG_{CFG}$ is undecidable. (Hint: Use a reduction from $PCP$ ... $a_{1},\dots,a_{k}$ are new terminal symbols. Prove that this reduction works.)

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

0 votes

0 answers

20

Michael Sipser Edition 3 Exercise 5 Question 20 (Page No. 240)
Prove that there exists an undecidable subset of $\{1\}^{\ast}$ .

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

0 votes

0 answers

21

Michael Sipser Edition 3 Exercise 5 Question 19 (Page No. 240)
In the silly Post Correspondence Problem, $SPCP$, the top string in each pair has the same length as the bottom string. Show that the $SPCP$ is decidable.

asked 4 days ago in Theory of Computation by Lakshman Patel RJIT Veteran (51.5k points) | 1 view

0 votes

0 answers

22

Michael Sipser Edition 3 Exercise 5 Question 18 (Page No. 240)
Show that the Post Correspondence Problem is undecidable over the binary alphabet $\Sigma = \{0,1\}$.

asked 4 days ago in Theory of Computation by Lakshman Patel RJIT Veteran (51.5k points) | 1 view

0 votes

0 answers

23

Michael Sipser Edition 3 Exercise 5 Question 17 (Page No. 240)
Show that the Post Correspondence Problem is decidable over the unary alphabet $\Sigma = \{1\}$.

asked 4 days ago in Theory of Computation by Lakshman Patel RJIT Veteran (51.5k points) | 1 view

0 votes

0 answers

24

Michael Sipser Edition 3 Exercise 5 Question 16 (Page No. 240)
Let $\Gamma = \{0, 1, \sqcup\}$ be the tape alphabet for all TMs in this problem. Define the busy beaver function $BB: N \rightarrow N$ as follows. For each value of $k$, consider all $k-$state TMs that halt when ... maximum number of $1s$ that remain on the tape among all of these machines. Show that $BB$ is not a computable function.

asked 4 days ago in Theory of Computation by Lakshman Patel RJIT Veteran (51.5k points) | 1 view

0 votes

0 answers

25

Michael Sipser Edition 3 Exercise 5 Question 15 (Page No. 240)
Consider the problem of determining whether a Turing machine $M$ on an input w ever attempts to move its head left at any point during its computation on $w$. Formulate this problem as a language and show that it is decidable.

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

0 votes

0 answers

26

Michael Sipser Edition 3 Exercise 5 Question 14 (Page No. 240)
Consider the problem of determining whether a Turing machine $M$ on an input $w$ ever attempts to move its head left when its head is on the left-most tape cell. Formulate this problem as a language and show that it is undecidable.

asked 4 days ago in Theory of Computation by Lakshman Patel RJIT Veteran (51.5k points) | 1 view

0 votes

0 answers

27

Michael Sipser Edition 3 Exercise 5 Question 13 (Page No. 239)
A useless state in a Turing machine is one that is never entered on any input string. Consider the problem of determining whether a Turing machine has any useless states. Formulate this problem as a language and show that it is undecidable.

asked 4 days ago in Theory of Computation by Lakshman Patel RJIT Veteran (51.5k points) | 1 view

0 votes

0 answers

28

Michael Sipser Edition 3 Exercise 5 Question 12 (Page No. 239)
Consider the problem of determining whether a single-tape Turing machine ever writes a blank symbol over a nonblank symbol during the course of its computation on any input string. Formulate this problem as a language and show that it is undecidable.

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

0 votes

0 answers

29

Michael Sipser Edition 3 Exercise 5 Question 11 (Page No. 239)
Consider the problem of determining whether a two-tape Turing machine ever writes a nonblank symbol on its second tape during the course of its computation on any input string. Formulate this problem as a language and show that it is undecidable.

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

0 votes

0 answers

30

Michael Sipser Edition 3 Exercise 5 Question 10 (Page No. 239)
Consider the problem of determining whether a two-tape Turing machine ever writes a nonblank symbol on its second tape when it is run on input $w$. Formulate this problem as a language and show that it is undecidable.

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

0 votes

0 answers

31

Michael Sipser Edition 3 Exercise 5 Question 9 (Page No. 239)
Let $T = \{\langle M \rangle \mid \text{M is a TM that accepts $w^{R}$ whenever it accepts} \:w\}$. Show that $T$ is undecidable.

asked 4 days ago in Theory of Computation by Lakshman Patel RJIT Veteran (51.5k points) | 1 view

0 votes

0 answers

32

Michael Sipser Edition 3 Exercise 5 Question 8 (Page No. 239)
In the proof of Theorem $5.15$, we modified the Turing machine $M$ so that it never tries to move its head off the left-hand end of the tape. Suppose that we did not make this modification to $M$. Modify the $PCP$ construction to handle this case.

asked 4 days ago in Theory of Computation by Lakshman Patel RJIT Veteran (51.5k points) | 1 view

0 votes

0 answers

33

Michael Sipser Edition 3 Exercise 5 Question 7 (Page No. 239)
Show that if $A$ is Turing-recognizable and $A\leq_{m} \overline{A},$ then $A$ is decidable.

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

0 votes

0 answers

34

Michael Sipser Edition 3 Exercise 5 Question 6 (Page No. 239)
Show that $\leq_{m}$ is a transitive relation.

asked 4 days ago in Theory of Computation by Lakshman Patel RJIT Veteran (51.5k points) | 1 view

0 votes

0 answers

35

Michael Sipser Edition 3 Exercise 5 Question 5 (Page No. 239)
Show that $A_{TM}$ is not mapping reducible to $E_{TM}$. In other words, show that no computable function reduces $A_{TM}$ to $E_{TM}$. (Hint: Use a proof by contradiction, and facts you already know about $A_{TM}$ and $E_{TM}$.)

asked 4 days ago in Theory of Computation by Lakshman Patel RJIT Veteran (51.5k points) | 1 view

0 votes

0 answers

36

Michael Sipser Edition 3 Exercise 5 Question 4 (Page No. 239)
If $A \leq_{m} B$ and $B$ is a regular language, does that imply that $A$ is a regular language? Why or why not?

asked 4 days ago in Theory of Computation by Lakshman Patel RJIT Veteran (51.5k points) | 1 view

0 votes

1 answer

37

Michael Sipser Edition 3 Exercise 0 Question 4 (Page No. 26)
If A has a elements and B has b elements, how many elements are in A × B? Explain your answer.

answered 4 days ago in Theory of Computation by Spidey_guy (111 points) | 21 views

0 votes

0 answers

38

Michael Sipser Edition 3 Exercise 5 Question 3 (Page No. 239)
Find a match in the following instance of the Post Correspondence Problem. $\begin{Bmatrix} \bigg[\dfrac{ab}{abab}\bigg],&\bigg[\dfrac{b}{a}\bigg],&\bigg[\dfrac{aba}{b}\bigg], & \bigg[\dfrac{aa}{a}\bigg] \end{Bmatrix}$

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

0 votes

0 answers

39

Michael Sipser Edition 3 Exercise 5 Question 2 (Page No. 239)
Show that $EQ_{CFG}$ is co-Turing-recognizable.

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

0 votes

0 answers

40

Michael Sipser Edition 3 Exercise 5 Question 1 (Page No. 239)
Show that $EQ_{CFG}$ is undecidable.

asked 5 days ago in Theory of Computation by Lakshman Patel RJIT Veteran (51.5k points) | 4 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 questions and answers in Theory of Computation

Recent Posts

Recent Blog Comments