0 votes
asked in TOC by (330 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

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!!
Welcome to Gatepoint Q&A, where you can ask questions and receive answers from other members of the community.
...