# Theory Of Computation Test – Question 7

Consider the following problems.

1. Given a TM M and a string w, does M ever write the Symbol $on its tape on input w? 2. Given a CFG G over {0,1}, does G generate all the strings of the language {0,1}* of length $\leqslant$1050? 3. Given a CFG G over {0,1}. does G generate all the strings of the language {0,1}* of length greater than 1050? 4. Given a TM M, are there infinitely many TM M’ accepting the same language i.e. L(M) ? Which of the above Problem is decidable? • 1. Only 4 • 2. 2 and 3 Only • 3. 2 and 4 Only • 4. 2,3 and 4 Only ## 1 Answer 0 votes answered by (320 points) The correct option should be opt 2... 1-the given option is wrong ,because the machine may or may not write$ (when it is in loop ).

4-equivalence problem of turing machine is undecidable..so wrong

2-all the string of length<=1050 ...so it is finite ...(decidable)

3-complement of option 2 (decidable)

Please correct if i am wrong!!

Thankyou!!