Decidability and Undecidability Questions and Answers

Q: Which of the following decision problems are undecidable?I. Given NFAs \(N_{1}\) and \(N_{2}\), is \(L(N_{1}) \cap L(N_{2}) = \Phi\)?II. Given a CFG \(G = (N, \Sigma, P, S)\) and a string \(x \in \Sigma^{*}\), does \(x \in L(G)\)?III. Given CFGs \(G_{1}\) and \(G_{2}\), is \(L(G_{1}) = L(G_{2})\)?IV. Given a TM \(M\), is \(L(M) = \Phi\)?

Problems III and IV are undecidable, so the answer is III and IV only.I is decidable: build the product automaton for \(L(N_{1}) \cap L(N_{2})\) and check whether any accepting state is reachable.II is decidable: membership in a context-free language is decided by the CYK algorithm.III is undecidable: equivalence of two context-free grammars cannot be decided in general.IV is undecidable: emptiness of a Turing machine's language is a non-trivial property of recursively enumerable languages, undecidable by Rice's theorem.Any option containing I or II includes a decidable problem.

Q: Let \(X\) be a recursive language and \(Y\) be a recursively enumerable but not recursive language. Let \(W\) and \(Z\) be two languages such that \(\overline{Y}\) reduces to \(W\), and \(Z\) reduces to \(\overline{X}\) (reduction means the standard many-one reduction). Which one of the following statements is TRUE?

The true statement is \(W\) is not recursively enumerable and \(Z\) is recursive.\(Y\) is recursively enumerable but not recursive, so its complement \(\overline{Y}\) is not recursively enumerable (if both a language and its complement were RE, the language would be recursive). \(\overline{Y}\) reduces to \(W\), and a reduction transfers recursive enumerability downward: if \(W\) were RE, \(\overline{Y}\) would be RE too. So \(W\) is not RE.\(X\) is recursive, so \(\overline{X}\) is recursive as well. \(Z\) reduces to \(\overline{X}\), so a decider for \(\overline{X}\) combined with the reduction decides \(Z\): \(Z\) is recursive.The options saying \(W\) can be RE or recursive contradict the first argument, and the one saying \(Z\) is not recursive contradicts the second. Note the bars: the reductions are from \(\overline{Y}\) and to \(\overline{X}\).

Q: Let \(G_{1}\), \(G_{2}\) be Context Free Grammars (CFGs) and \(R\) be a regular expression. For a grammar \(G\), let \(L(G)\) denote the language generated by \(G\).Which ONE among the following questions is decidable?

The decidable question is: Is \(L(G_{1}) = \emptyset\)?Emptiness of a context-free grammar is decidable: mark every terminal as generating, then repeatedly mark a variable as generating if some production rewrites it into generating symbols only. The language is empty exactly when the start symbol is never marked. This runs in polynomial time.The other three are undecidable. Equivalence of two CFGs, emptiness of the intersection of two context-free languages, and whether a CFG generates the same language as a given regular expression (which includes the undecidable question of whether a CFG generates everything, Σ*) are classic undecidable problems, proved by reduction from the Post correspondence problem.

Q: Consider the following problems. \(L(G)\) denotes the language generated by a grammar \(G\). \(L(M)\) denotes the language accepted by a machine \(M\).(I) For an unrestricted grammar \(G\) and a string \(w\), whether \(w \in L(G)\)(II) Given a Turing machine \(M\), whether \(L(M)\) is regular(III) Given two grammars \(G_{1}\) and \(G_{2}\), whether \(L(G_{1}) = L(G_{2})\)(IV) Given an NFA \(N\), whether there is a deterministic PDA \(P\) such that \(N\) and \(P\) accept the same language.Which one of the following statements is correct?

The correct statement is Only I, II and III are undecidable.I: unrestricted grammars generate exactly the recursively enumerable languages, so their membership problem is as hard as the halting problem: undecidable.II: being regular is a non-trivial property of the language of a Turing machine, so by Rice's theorem it is undecidable.III: equivalence of two grammars is undecidable already for context-free grammars, so it is undecidable for grammars in general.IV: an NFA accepts a regular language, and every regular language is accepted by a deterministic PDA (a DFA that ignores its stack). The answer is always yes, so the problem is trivially decidable.The options leaving out I, II or III, or listing IV as undecidable, are therefore wrong.

Q: Which among the following is/are correct statement/statements ?(i) A class of problems with two outputs "yes" or "no" is said to be decidable (solvable) if there exists some definite algorithm which always terminates (halts) with one of two outputs "yes" or "no". Otherwise, the class of problems is said to be undecidable.(ii) A decision problem is a problem that requires a yes or no answer.(iii) Undecidable problem can be solved by a computer or a computer program of any kind.

The correct statements are (i) and (ii) only.A decision problem is one whose answer is yes or no (ii). It is decidable if some algorithm always halts with the correct yes or no answer for every input, and undecidable otherwise (i).Statement (iii) contradicts the definition: an undecidable problem, such as the halting problem, cannot be solved by any computer program in general. So options including (iii) are wrong.

Q: If there exists a Turing machine M which when applied to any problem in the class terminates if the correct answer is yes and may not terminate otherwise is said to be .................. .

Such a class is said to be Partially solvable.A problem is partially solvable (semi-decidable) when a Turing machine exists that halts and answers yes on every yes-instance, but may run forever on a no-instance. The halting problem itself is of this kind: simulating the machine eventually confirms that it halts, but never confirms that it does not.A problem is solvable when some Turing machine halts on every instance with the right answer, and unsolvable when none does. 'Stable' and 'unstable' are not terms of computability theory.

Q: For Σ to be an alphabet and L &sube; Σ* be a language A is said to be decidable if there exists a Turing machine M for every string ω ∈ Σ* with which of the following conditions.(i) If ω ∈ L, the computation of TM M on input string ω terminates in accept state(ii) If ω ∉ L (ω does not belong to L) then computation of TM M on input string ω terminates in reject state(iii) If ω ∈ L then computation of TM M on input string ω terminates in reject state.

The conditions are (i) and (ii) only.A language L is decidable if some Turing machine M halts on every input and gives the right verdict: for every string \(\omega\) in L, M halts in its accept state (i), and for every string not in L, M halts in its reject state (ii). Halting on both kinds of input is what separates decidable from merely recognisable (recursively enumerable) languages.Condition (iii) says that strings in L are rejected, which contradicts (i) and would make M decide some other language. Every option containing (iii) is therefore wrong.

Q: The decision problem "Given a Turing Machine M and a step-counting function "myfun", is the language accepted by M in Time (myfun) ?" is........... .

The problem is unsolvable, that is undecidable.The input is a Turing machine \(M\), and the question asks whether the language it accepts belongs to the class \(\mathrm{TIME}(\mathit{myfun})\). That is a property of the language \(L(M)\), not of how \(M\) happens to run. The property is non-trivial: some recursively enumerable languages are decidable within the time bound and some are not. Rice's theorem says every non-trivial property of the language of a Turing machine is undecidable, so no algorithm decides it.'Solvable' is therefore wrong. 'Stable' is not a term used for decidability. 'Partially solvable' would mean the yes-instances can at least be recognised, which Rice's theorem does not give, and the standard answer for such a question is unsolvable.

Q: Which one of the following is not decidable ?

The problem that is not decidable is the equivalence of two given Turing machines.Whether two Turing machines accept the same language is undecidable; if it were decidable, we could decide whether a machine accepts the empty language by comparing it with a machine that rejects everything, which contradicts Rice's theorem.The others are decidable: whether M accepts S within K steps is settled by simulating M for K steps; emptiness of a DFA's language is checked by searching for a path from the start state to an accepting state; and emptiness of a CFG's language is checked by finding whether the start symbol can derive a terminal string.

Which of the following decision problems are undecidable?

I. Given NFAs \(N_{1}\) and \(N_{2}\), is \(L(N_{1}) \cap L(N_{2}) = \Phi\)?
II. Given a CFG \(G = (N, \Sigma, P, S)\) and a string \(x \in \Sigma^{*}\), does \(x \in L(G)\)?
III. Given CFGs \(G_{1}\) and \(G_{2}\), is \(L(G_{1}) = L(G_{2})\)?
IV. Given a TM \(M\), is \(L(M) = \Phi\)?

A.I and IV only
B.II and III only
C.III and IV only
D.II and IV only

Exam Year(s)

GATE CS - 2016,

Answer: C

Problems III and IV are undecidable, so the answer is III and IV only.

I is decidable: build the product automaton for \(L(N_{1}) \cap L(N_{2})\) and check whether any accepting state is reachable.
II is decidable: membership in a context-free language is decided by the CYK algorithm.
III is undecidable: equivalence of two context-free grammars cannot be decided in general.
IV is undecidable: emptiness of a Turing machine's language is a non-trivial property of recursively enumerable languages, undecidable by Rice's theorem.

Any option containing I or II includes a decidable problem.

Discuss in Forum

Let \(X\) be a recursive language and \(Y\) be a recursively enumerable but not recursive language. Let \(W\) and \(Z\) be two languages such that \(\overline{Y}\) reduces to \(W\), and \(Z\) reduces to \(\overline{X}\) (reduction means the standard many-one reduction). Which one of the following statements is TRUE?

A.\(W\) can be recursively enumerable and \(Z\) is recursive.
B.\(W\) can be recursive and \(Z\) is recursively enumerable.
C.\(W\) is not recursively enumerable and \(Z\) is recursive.
D.\(W\) is not recursively enumerable and \(Z\) is not recursive.

Exam Year(s)

GATE CS - 2016,

Answer: C

The true statement is \(W\) is not recursively enumerable and \(Z\) is recursive.

\(Y\) is recursively enumerable but not recursive, so its complement \(\overline{Y}\) is not recursively enumerable (if both a language and its complement were RE, the language would be recursive). \(\overline{Y}\) reduces to \(W\), and a reduction transfers recursive enumerability downward: if \(W\) were RE, \(\overline{Y}\) would be RE too. So \(W\) is not RE.

\(X\) is recursive, so \(\overline{X}\) is recursive as well. \(Z\) reduces to \(\overline{X}\), so a decider for \(\overline{X}\) combined with the reduction decides \(Z\): \(Z\) is recursive.

The options saying \(W\) can be RE or recursive contradict the first argument, and the one saying \(Z\) is not recursive contradicts the second. Note the bars: the reductions are from \(\overline{Y}\) and to \(\overline{X}\).

Discuss in Forum

Consider the following languages.

\(L_{1} = \{\langle M \rangle \mid M\) takes at least 2016 steps on some input\(\}\),
\(L_{2} = \{\langle M \rangle \mid M\) takes at least 2016 steps on all inputs\(\}\) and
\(L_{3} = \{\langle M \rangle \mid M\) accepts \(\varepsilon\}\),

where for each Turing machine \(M\), \(\langle M \rangle\) denotes a specific encoding of \(M\). Which one of the following is TRUE?

A.\(L_{1}\) is recursive and \(L_{2}, L_{3}\) are not recursive
B.\(L_{2}\) is recursive and \(L_{1}, L_{3}\) are not recursive
C.\(L_{1}, L_{2}\) are recursive and \(L_{3}\) is not recursive
D.\(L_{1}, L_{2}, L_{3}\) are recursive

Exam Year(s)

GATE CS - 2016,

Answer: C

\(L_{1}, L_{2}\) are recursive and \(L_{3}\) is not recursive.

Within its first 2016 steps a Turing machine can read at most the first 2016 or so input symbols. So whether \(M\) takes at least 2016 steps on an input depends only on that input’s first 2016 symbols, and there are finitely many such prefixes. A decider can simulate \(M\) for 2016 steps on each of them and answer whether some (for \(L_{1}\)) or all (for \(L_{2}\)) inputs reach step 2016. Both are therefore recursive.

\(L_{3}\), whether \(M\) accepts the empty string, is a non-trivial property of the language \(M\) accepts, so it is undecidable by Rice’s theorem (it is recursively enumerable, but not recursive).

The options calling \(L_{1}\) or \(L_{2}\) non-recursive overlook the bounded step count, and the option calling all three recursive ignores Rice’s theorem.

Discuss in Forum

Let \(G_{1}\), \(G_{2}\) be Context Free Grammars (CFGs) and \(R\) be a regular expression. For a grammar \(G\), let \(L(G)\) denote the language generated by \(G\).

Which ONE among the following questions is decidable?

A.Is \(L(G_{1}) = L(G_{2})\)?
B.Is \(L(G_{1}) \cap L(G_{2}) = \emptyset\)?
C.Is \(L(G_{1}) = L(R)\)?
D.Is \(L(G_{1}) = \emptyset\)?

Exam Year(s)

GATE CS - 2025,

Answer: D

The decidable question is: Is \(L(G_{1}) = \emptyset\)?

Emptiness of a context-free grammar is decidable: mark every terminal as generating, then repeatedly mark a variable as generating if some production rewrites it into generating symbols only. The language is empty exactly when the start symbol is never marked. This runs in polynomial time.

The other three are undecidable. Equivalence of two CFGs, emptiness of the intersection of two context-free languages, and whether a CFG generates the same language as a given regular expression (which includes the undecidable question of whether a CFG generates everything, Σ*) are classic undecidable problems, proved by reduction from the Post correspondence problem.

Discuss in Forum

Consider the following problems. \(L(G)\) denotes the language generated by a grammar \(G\). \(L(M)\) denotes the language accepted by a machine \(M\).

(I) For an unrestricted grammar \(G\) and a string \(w\), whether \(w \in L(G)\)
(II) Given a Turing machine \(M\), whether \(L(M)\) is regular
(III) Given two grammars \(G_{1}\) and \(G_{2}\), whether \(L(G_{1}) = L(G_{2})\)
(IV) Given an NFA \(N\), whether there is a deterministic PDA \(P\) such that \(N\) and \(P\) accept the same language.

Which one of the following statements is correct?

A.Only I and II are undecidable
B.Only III is undecidable
C.Only II and IV are undecidable
D.Only I, II and III are undecidable

Exam Year(s)

GATE CS - 2018,

Answer: D

The correct statement is Only I, II and III are undecidable.

I: unrestricted grammars generate exactly the recursively enumerable languages, so their membership problem is as hard as the halting problem: undecidable.
II: being regular is a non-trivial property of the language of a Turing machine, so by Rice's theorem it is undecidable.
III: equivalence of two grammars is undecidable already for context-free grammars, so it is undecidable for grammars in general.
IV: an NFA accepts a regular language, and every regular language is accepted by a deterministic PDA (a DFA that ignores its stack). The answer is always yes, so the problem is trivially decidable.

The options leaving out I, II or III, or listing IV as undecidable, are therefore wrong.

Discuss in Forum

Which among the following is/are correct statement/statements ?

(i) A class of problems with two outputs "yes" or "no" is said to be decidable (solvable) if there exists some definite algorithm which always terminates (halts) with one of two outputs "yes" or "no". Otherwise, the class of problems is said to be undecidable.
(ii) A decision problem is a problem that requires a yes or no answer.
(iii) Undecidable problem can be solved by a computer or a computer program of any kind.

A.(i) and (ii) only
B.(i) and (iii) only
C.(ii) and (iii) only
D.(i), (ii) and (iii) only

Exam Year(s)

MH SET - 2020, SET Exam - 2020,

Answer: A

The correct statements are (i) and (ii) only.

A decision problem is one whose answer is yes or no (ii). It is decidable if some algorithm always halts with the correct yes or no answer for every input, and undecidable otherwise (i).

Statement (iii) contradicts the definition: an undecidable problem, such as the halting problem, cannot be solved by any computer program in general. So options including (iii) are wrong.

Discuss in Forum

If there exists a Turing machine M which when applied to any problem in the class terminates if the correct answer is yes and may not terminate otherwise is said to be .................. .

A.Stable
B.Unsolvable
C.Partially solvable
D.Unstable

Exam Year(s)

MH SET - 2021, SET Exam - 2021,

Answer: C

Such a class is said to be Partially solvable.

A problem is partially solvable (semi-decidable) when a Turing machine exists that halts and answers yes on every yes-instance, but may run forever on a no-instance. The halting problem itself is of this kind: simulating the machine eventually confirms that it halts, but never confirms that it does not.

A problem is solvable when some Turing machine halts on every instance with the right answer, and unsolvable when none does. 'Stable' and 'unstable' are not terms of computability theory.

Discuss in Forum

For Σ to be an alphabet and L ⊆ Σ^* be a language A is said to be decidable if there exists a Turing machine M for every string ω ∈ Σ^* with which of the following conditions.

(i) If ω ∈ L, the computation of TM M on input string ω terminates in accept state
(ii) If ω ∉ L (ω does not belong to L) then computation of TM M on input string ω terminates in reject state
(iii) If ω ∈ L then computation of TM M on input string ω terminates in reject state.

A.(iii) only
B.(i) and (iii) only
C.(i) and (ii) only
D.(ii) and (iii) only

Exam Year(s)

MH SET - 2023, SET Exam - 2023,

Answer: C

The conditions are (i) and (ii) only.

A language L is decidable if some Turing machine M halts on every input and gives the right verdict: for every string \(\omega\) in L, M halts in its accept state (i), and for every string not in L, M halts in its reject state (ii). Halting on both kinds of input is what separates decidable from merely recognisable (recursively enumerable) languages.

Condition (iii) says that strings in L are rejected, which contradicts (i) and would make M decide some other language. Every option containing (iii) is therefore wrong.

Discuss in Forum

The decision problem "Given a Turing Machine M and a step-counting function "myfun", is the language accepted by M in Time (myfun) ?" is........... .

A.Stable
B.Unsolvable
C.Partially solvable
D.Solvable

Exam Year(s)

MH SET - 2023, SET Exam - 2023,

Answer: B

The problem is unsolvable, that is undecidable.

The input is a Turing machine \(M\), and the question asks whether the language it accepts belongs to the class \(\mathrm{TIME}(\mathit{myfun})\). That is a property of the language \(L(M)\), not of how \(M\) happens to run. The property is non-trivial: some recursively enumerable languages are decidable within the time bound and some are not. Rice's theorem says every non-trivial property of the language of a Turing machine is undecidable, so no algorithm decides it.

'Solvable' is therefore wrong. 'Stable' is not a term used for decidability. 'Partially solvable' would mean the yes-instances can at least be recognised, which Rice's theorem does not give, and the standard answer for such a question is unsolvable.

Discuss in Forum

10.

Which one of the following is not decidable ?

A.Given a Turing machine M, a string S and an integer K, M accepts S with K step S
B.Equivalence of two given Turing machines
C.Language accepted by a given DFSA is non-empty
D.Language generated by a CFG is non-empty

Exam Year(s)

MH SET - 2024, SET Exam - 2024,

Answer: B

The problem that is not decidable is the equivalence of two given Turing machines.

Whether two Turing machines accept the same language is undecidable; if it were decidable, we could decide whether a machine accepts the empty language by comparing it with a machine that rejects everything, which contradicts Rice's theorem.

The others are decidable: whether M accepts S within K steps is settled by simulating M for K steps; emptiness of a DFA's language is checked by searching for a path from the start state to an accepting state; and emptiness of a CFG's language is checked by finding whether the start symbol can derive a terminal string.

Discuss in Forum

Loading…

Topics

Other Subjects

Tags: Decidability and Undecidability Questions and Answers || Decidability and Undecidability MCQ Questions and Answers || Decidability and Undecidability GK Questions and Answers || Decidability and Undecidability GK MCQ Questions || Decidability and Undecidability Multiple Choice Questions and Answers || Decidability and Undecidability GK || GK on Decidability and Undecidability || Theory of Computation Questions and Answers || Theory of Computation MCQ Questions and Answers || Theory of Computation GK Questions and Answers || GK on Theory of Computation

Decidability and Undecidability Questions and Answers

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications