search
Log In
0 votes
1 answer
1
Let $G_1$ and $G_2$ be arbitrary context free languages and $R$ an arbitrary regular language. Consider the following problems: Is $L(G_1)=L(G_2)$? Is $L(G_2) \leq L(G_1)$? Is $L(G_1)=R$? Which of the problems are undecidable? Choose the correct answer from the options given below: $(a)$ only $(b)$ only $(a)$ and $(b)$ only $(a)$, $(b)$ and $(c)$
asked Nov 20 in Theory of Computation jothee 15 views
0 votes
1 answer
2
Given below are two statements: Statement $I$: The problem Is $L_1 \wedge L_2 = \phi$? is undecidable for context sensitive languages $L_1$ and $L_2$ Statement $II$: The problem Is $W \in L$? is decidable for context sensitive language $L$. (where $W$ is ... $II$ are false Statement $I$ is correct but Statement $II$ is false Statement $I$ is incorrect but Statement $II$ is true
asked Nov 20 in Theory of Computation jothee 12 views
0 votes
2 answers
3
Which of the following are undecidable? $P1$: The language generated by some CFG contains any words of length less than some given number $n$. $P2$: Let $L1$ be CFL and $L2$ be regular, to determine whether $L1$ and $L2$ have common elements $P3$: Any given CFG is ambiguous or not. ... CFG $G$, to determine whether epsilon belongs to $L(G)$ $P2$ only $P1$ and $P2$ only $P2$ and $P3$ only $P3$ only
asked Mar 30 in Theory of Computation Lakshman Patel RJIT 640 views
11 votes
7 answers
4
Which of the following languages are undecidable? Note that $\left \langle M \right \rangle$ indicates encoding of the Turing machine M. $L_1 = \{\left \langle M \right \rangle \mid L(M) = \varnothing \}$ ... $L_1$, $L_3$, and $L_4$ only $L_1$ and $L_3$ only $L_2$ and $L_3$ only $L_2$, $L_3$, and $L_4$ only
asked Feb 12 in Theory of Computation Arjun 2.5k views
1 vote
3 answers
5
Consider the following statements. The intersection of two context-free languages is always context-free The super-set of a context-free languages is never regular The subset of a decidable language is always decidable Let $\Sigma = \{a,b,c\}.$ Let $L\subseteq \Sigma$ be the language of all strings in which either ... $(2)$ Only $(1),(2)$ and $(3)$ Only $(4)$ None of $(1),(2),(3),(4)$ are true.
asked Feb 11 in Theory of Computation Lakshman Patel RJIT 223 views
3 votes
0 answers
6
1 vote
0 answers
7
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 92 views
0 votes
1 answer
8
0 votes
0 answers
9
0 votes
0 answers
10
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 120 views
0 votes
0 answers
11
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 70 views
1 vote
0 answers
12
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 86 views
0 votes
0 answers
13
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 50 views
0 votes
0 answers
14
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 69 views
1 vote
0 answers
15
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 148 views
0 votes
0 answers
16
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 78 views
0 votes
0 answers
19
1 vote
0 answers
24
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 Oct 19, 2019 in Theory of Computation Lakshman Patel RJIT 181 views
0 votes
0 answers
25
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 Oct 19, 2019 in Theory of Computation Lakshman Patel RJIT 42 views
0 votes
0 answers
26
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 Oct 19, 2019 in Theory of Computation Lakshman Patel RJIT 47 views
0 votes
0 answers
27
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 Oct 19, 2019 in Theory of Computation Lakshman Patel RJIT 67 views
0 votes
0 answers
28
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 Oct 19, 2019 in Theory of Computation Lakshman Patel RJIT 51 views
1 vote
0 answers
29
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 Oct 19, 2019 in Theory of Computation Lakshman Patel RJIT 25 views
...