in Theory of Computation retagged by
501 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.
in Theory of Computation retagged by
501 views

1 comment

$ \large{\colorbox{yellow}{Detailed video solution of this question with direct time stamp}}$
All India Mock Test 2 - Solutions Part 3

1
1

1 Answer

3 votes
3 votes

Every r.e. set, including the halting set, can be generated by some grammar. But the complement of such RE (RE which is not REC) is not RE.

Detailed Video Solution: https://www.youtube.com/live/atrZdsQU5RE?feature=shared&t=10370 

edited by
Answer:

Related questions