Let A and B be finite alphabets and let # be a symbol outside both A and B. Let f be a total function from A^{*} to B^{*}. We say f is computable if there exists a Turing machine M which given an input x in A^{*}, always halts with f(x) on its tape. Let L_{f} denote the language $\{x\;\#\;f(x)\vert x\in A^\ast\}$. Which of the following statemeant is true:
Let L(R) be the language represented by regular expression R. Let L(G) be the language generated by a context free grammar G. Let L(M) be the language accepted by a Turning machine M.
Which of the following decision problems are undecidable?
I. Given a regular expression R and a string w, is $\style{font-family:'Times New Roman'}{w\in L(R)}$?
II. Given context-free grammar G, is L(G)=$\style{font-family:'Times New Roman'}\phi$?
III. Given a context-free grammar G, is L(G)=$\style{font-family:'Times New Roman'}{\sum\nolimits^\ast}$ for some alphabet $\style{font-family:'Times New Roman'}\sum$?
IV. Given a Turning machine M and a string w, is $\style{font-family:'Times New Roman'}{w\in L(M)}$
Consider the following statements. I. The complement of every Turing decidable language is Turing decidable II. There exists some language which is in NP but is not Turing decidable III. If L is a language in NP, L is Turing decidable Which of the above statements is/are true?
Let L be a language and $\overline{)L}$ be its complement. Which one of the following is NOT a viable possibility?
Let A ≤_{m} B denotes that language A is mapping reducible (also known as many-to-one reducible) to language B. Which one of the following is FALSE?
Let < M > be the encoding of a Turing machine as a string over ∑ = {0, 1}. Let $L=\left\{<M>|MisaTuringmachinethatacceptsastringoflength2014\right\}.$
Let Σ be a finite non-empty alphabet and let ${2}^{{\sum}^{*}}$ be the power set of Σ*. Which one of the following is TRUE?
Which one of the following problems is undecidable?
Which of the following statements is/are FALSE? 1. For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine. 2. Turing recognizable languages are closed under union and complementation. 3. Turing decidable languages are closed under intersection and complementation. 4. Turing recognizable languages are closed under union and intersection.
Assuming P ≠ NP, which of the following is TRUE?
Which of the following problems are decidable?
Which of the following pairs have DIFFERENT expressive power?
Which of the following is true for the language {a^{p} | p is a prime}?
Which of the following are decidable? I. Whether the intersection of two regular languages is infinite II. Whether a given context-free language is regular III. Whether two push-down automata accept the same language IV. Whether a given grammar is context-free
If L and $\overline{L}$ are recursively enumerable then L is
Which of the following problems is undecidable?