retagged by
557 views
4 votes
4 votes
Which of the following statements about Turing machines is false?
  1. For every context-sensitive language $L$, there is a Turing machine that accepts precisely the strings of $L$.
  2. For any grammar $G$ with set of terminals $\Sigma$, there is a Turing machine that accepts precisely the strings in $\Sigma^*$ that cannot be derived from $G$.
  3. There is a Turing machine which, given encodings of two DFAs over the same alphabet $\Sigma$, can tell whether or not they define the same language.
  4. There is a Turing machine $A$ which can simulate the behaviour of any given Turing machine $B$ on any given finite input.
retagged by

1 Answer

Answer:

Related questions