# 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