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 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.
  • 2.
  • 3.
  • 4.

Leave a Reply

Your email address will not be published. Required fields are marked *