edited by
8,176 views
20 votes
20 votes

Regarding the power of recognition of languages, which of the following statements is false?

  1. The non-deterministic finite-state automata are equivalent to deterministic finite-state automata.

  2. Non-deterministic Push-down automata are equivalent to deterministic Push-down automata.

  3. Non-deterministic Turing machines are equivalent to deterministic Turing machines.

  4. Multi-tape Turing machines are available are equivalent to Single-tape Turing machines.

edited by

1 Answer

Best answer
27 votes
27 votes
  1. True. Proof - Subset Construction Procedure.
  2. False. Conversion from NPDA To DPDA is not always possible like in the case of $ww_R.$
  3. True. For any non-deterministic TM we can construct an equivalent (accepting the same language) deterministic TM.
  4. True. For an $n-\textsf{tape}$ TM, we can always construct an equivalent single tape TM.

Answer: B

edited by
Answer:

Related questions

41 votes
41 votes
7 answers
1
Kathleen asked Sep 25, 2014
22,934 views
The string $1101$ does not belong to the set represented by$110^*(0 + 1)$$1(0 + 1)^*101$$(10)^*(01)^*(00 + 11)^*$$(00 + (11)^*0)^*$
29 votes
29 votes
5 answers
2
Arjun asked Oct 17, 2014
8,696 views
Give a regular expression for the set of binary strings where every $0$ is immediately followed by exactly $k$ $1$'s and preceded by at least $k$ $1$’s ($k$ is a fixed...
23 votes
23 votes
3 answers
3
Kathleen asked Sep 25, 2014
6,323 views
Which of the following statements is false?Every finite subset of a non-regular set is regularEvery subset of a regular set is regularEvery finite subset of a regular set...
19 votes
19 votes
3 answers
4