Question 1 |

Which of the following is/are undecidable?

**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