Question 1 |
Which of the following is/are undecidable?
MSQ
MSQ
Given two Turing machines M1 and M2 , decide if L(M1 ) = L(M2 ). | |
Given a Turing machine M , decide if L(M ) is regular. | |
Given a Turing machine M , decide if M accepts all strings. | |
Given a Turing machine M , decide if M takes more than 1073 steps on every string. |
Question 1 Explanation:
Question 2 |
For a Turing machine M, < M > denotes an encoding of M. Consider the following two languages.
\begin{array}{ll} L1 = \{ \langle M \rangle \mid M \text{ takes more than } 2021 \text{ steps on all inputs} \} \\ L2 = \{ \langle M \rangle \mid M\text{ takes more than } 2021 \text{ steps on some input} \} \end{array}
Which one of the following options is correct?
\begin{array}{ll} L1 = \{ \langle M \rangle \mid M \text{ takes more than } 2021 \text{ steps on all inputs} \} \\ L2 = \{ \langle M \rangle \mid M\text{ takes more than } 2021 \text{ steps on some input} \} \end{array}
Which one of the following options is correct?
Both L1 and L2 are decidable. | |
L1 is decidable and L2 is undecidable. | |
L1 is undecidable and L2 is decidable. | |
Both L1 and L2 are undecidable. |
Question 2 Explanation:
Question 3 |
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|L(M)=\varnothing \}
L_2={\left \langle M,w,q \right \rangle|M on input w reaches state q in exactly 100 steps}
L_3=\{\left \langle M \right \rangle|L(M) \;is \; not \; recursive\}
L_4=\{\left \langle M \right \rangle|L(M) \;contains \; at \; least\; 21 \; members\}
L_1=\{\left \langle M \right \rangle|L(M)=\varnothing \}
L_2={\left \langle M,w,q \right \rangle|M on input w reaches state q in exactly 100 steps}
L_3=\{\left \langle M \right \rangle|L(M) \;is \; not \; recursive\}
L_4=\{\left \langle M \right \rangle|L(M) \;contains \; at \; least\; 21 \; members\}
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 |
Question 3 Explanation:
Question 4 |
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 G1 and G2, whether L(G1) = L(G2)
(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?
(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 G1 and G2, whether L(G1) = L(G2)
(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?
Only I and II are undecidable | |
Only III is undecidable | |
Only II and IV are undecidable | |
Only I, II and III are undecidable |
Question 4 Explanation:
Question 5 |
Let A and B be infinite alphabets and let # be a symbol outside both A and B. Let f be a total
functional from A* to B*. We say f is computable if there exists a Turning 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)|x\inA*}. Which of the following statements is true:
f is computable if and only if L_{f} is recursive. | |
f is computable if and only L_{f} recursively enumerable. | |
If f is computable then L_{f} is recursive, but not conversely. | |
If f is computable then L_{f} is recursively enumerable, but not conversely. |
Question 5 Explanation:
There are 5 questions to complete.
GOOD