menu
search
Log In
Quick search syntax
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

Subjects

Recent questions in Theory of Computation

Network Sites

 GO Mechanical
 GO Electrical
 GO Electronics
 GO Civil
 CSE Doubts

Web Page

Regular expressions and finite automata, Context-free grammars and push-down automata, Regular and context-free languages, Pumping lemma, Turing machines and undecidability.

$$\small{\overset{{\large{\textbf{Mark Distribution in Previous GATE}}}}{\begin{array}{|c|c|c|c|c|c|c|c|}\hline
\textbf{Year}&\textbf{2019}&\textbf{2018}&\textbf{2017-1}&\textbf{2017-2}&\textbf{2016-1}&\textbf{2016-2}&\textbf{Minimum}&\textbf{Average}&\textbf{Maximum}
\\\hline\textbf{1 Mark Count}&2&2&2&3&3&3&2&2.5&3
\\\hline\textbf{2 Marks Count}&3&3&5&3&3&3&3&3.3&5
\\\hline\textbf{Total Marks}&8&8&12&9&9&9&\bf{8}&\bf{9.2}&\bf{12}\\\hline
\end{array}}}$$

Recent questions in Theory of Computation

1 vote
1 answer
1
NTA NET DEC 2019(Inherently ambiguous language)
Consider the following languages: L1 ={a^nb^nc^m } U {a^nb^mc^m} n, m ≥ 0 L2={wwR|w {a,b}*} Where R represents reversible operation Which one of the following is (are) inherently ambiguous language(s)? 1) Only L1 (2) only L2 3) Both L1 and L2 (4) neither L1 nor L2
Consider the following languages: L1 ={a^nb^nc^m } U {a^nb^mc^m} n, m ≥ 0 L2={wwR|w {a,b}*} Where R represents reversible operation Which one of the following is (are) inherently ambiguous language(s)? 1) Only L1 (2) only L2 3) Both L1 and L2 (4) neither L1 nor L2
asked Dec 21, 2019 in Theory of Computation Sanjay Sharma 1.1k views
1 vote
2 answers
2
NTA NET DEC 2019 (Post-correspondence)
$\mathbf{Q57}$ Let $\mathrm{A={001,0011,11,101}}$ and $\mathrm{B={01,111,111,010}}$. Similarly , Let $\mathrm{C={00,001,1000}}$ and $\mathrm{B={0,11,011}}$. Which of the following pairs have a post correspondence solution? $\mathrm{1)\; Only \;pair \;(A,B) }$ ... $\mathrm{\; 4) \;Neither \;(A,B) \;nor\; (C,D) }$
$\mathbf{Q57}$ Let $\mathrm{A={001,0011,11,101}}$ and $\mathrm{B={01,111,111,010}}$. Similarly , Let $\mathrm{C={00,001,1000}}$ and $\mathrm{B={0,11,011}}$. Which of the following pairs have a post correspondence solution? $\mathrm{1)\; Only \;pair \;(A,B) }$ $\mathrm{ 2) \;Only\; pair \;(C,D) }$ $\mathrm{ 3) \; Both (A,B)\; and (C,D) \; }$ $\mathrm{\; 4) \;Neither \;(A,B) \;nor\; (C,D) }$
asked Dec 20, 2019 in Theory of Computation Sanjay Sharma 1.3k views
3 votes
0 answers
3
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.
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 Oct 20, 2019 in Theory of Computation Lakshman Patel RJIT 251 views
1 vote
0 answers
4
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.
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 Oct 20, 2019 in Theory of Computation Lakshman Patel RJIT 99 views
0 votes
1 answer
5
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.
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 Oct 20, 2019 in Theory of Computation Lakshman Patel RJIT 197 views
1 vote
1 answer
6
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.
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 Oct 20, 2019 in Theory of Computation Lakshman Patel RJIT 154 views
0 votes
0 answers
7
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}\}$.
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 Oct 20, 2019 in Theory of Computation Lakshman Patel RJIT 134 views
0 votes
0 answers
8
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.
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 obtain a sequence, $x, f(x), f(f(x)), \dots$ ... problem. Suppose that $ATM$ were decidable by a $TM\: H$. Use $H$ to describe a $TM$ that is guaranteed to state the answer to the $3x + 1$ problem.
asked Oct 20, 2019 in Theory of Computation Lakshman Patel RJIT 82 views
1 vote
0 answers
9
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} \}$.
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 Oct 20, 2019 in Theory of Computation Lakshman Patel RJIT 110 views
0 votes
0 answers
10
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.
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 consisting of Turing ... any $TMs$. Prove that $P$ is an undecidable language. Show that both conditions are necessary for proving that $P$ is undecidable.
asked Oct 20, 2019 in Theory of Computation Lakshman Patel RJIT 58 views
0 votes
0 answers
11
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.
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$ ... $M_{1}$ and $M_{2}$ are any $TMs$. Prove that $P$ is an undecidable language.
asked Oct 20, 2019 in Theory of Computation Lakshman Patel RJIT 87 views
1 vote
0 answers
12
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.
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$. The squares along the boundary of the rectangle contain the symbol $\#$ and the internal squares contain ... . Consider the problem of determining whether two of these machines are equivalent. Formulate this problem as a language and show that it is undecidable.
asked Oct 20, 2019 in Theory of Computation Lakshman Patel RJIT 163 views
0 votes
0 answers
13
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.
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 of a $2DFA$ is finite and is just large ... $E_{2DFA}$ is not decidable.
asked Oct 20, 2019 in Theory of Computation Lakshman Patel RJIT 91 views
0 votes
0 answers
15
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.
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 Oct 19, 2019 in Theory of Computation Lakshman Patel RJIT 28 views
0 votes
0 answers
18
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.)
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 Oct 19, 2019 in Theory of Computation Lakshman Patel RJIT 64 views
Page:
Dark theme
Muffin by Hélio Chun
Thanks to Q2A
...