0 votes
asked in TOC by (580 points)

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

Your answer

Your name to display (optional):
Privacy: Your email address will only be used for sending these notifications.
Anti-spam verification:
To avoid this verification in future, please log in or register.
Welcome to Gatepoint Q&A, where you can ask questions and receive answers from other members of the community.
...