edited by
7,415 views
28 votes
28 votes

In which of the cases stated below is the following statement true?
"For every non-deterministic machine $M_{1}$ there exists an equivalent deterministic machine $M_{2}$ recognizing the same language".      

  1. $M_{1}$ is non-deterministic finite automaton.
  2. $M_{1}$ is non-deterministic PDA.
  3. $M_{1}$ is a non-deterministic Turing machine.
  4. For no machines $M_{1}$ and $M_2$,  the above statement true.
edited by

1 Answer

Best answer
34 votes
34 votes

Answer: A and C.

  • For every NFA there exists a DFA.
  • For every NPDA there does not exist a deterministic PDA.
  • Every nondeterministic Turing machine has an equivalent deterministic Turing Machine.
edited by
Answer:

Related questions

42 votes
42 votes
8 answers
1
Kathleen asked Sep 13, 2014
14,301 views
Which of the following regular expression identities is/are TRUE?$r^{(^\ast)} =r^\ast$$(r^\ast s^\ast)=(r+s)^\ast$$(r+s)^\ast = r^\ast + s^\ast$$r^\ast s^\ast = r^\ast+s^...
24 votes
24 votes
4 answers
2
Kathleen asked Sep 13, 2014
9,947 views
Which of the following is/are a tautology?$a \vee b \to b \wedge c$$a \wedge b \to b \vee c$$a \vee b \to \left(b \to c \right)$$a \to b \to \left(b \to c \right)$
18 votes
18 votes
2 answers
3
9 votes
9 votes
2 answers
4
Kathleen asked Sep 12, 2014
2,962 views
Start and stop bits do not contain any 'information' but are used in serial communicationError detectionError correctionSynchronizationSlowing down the communications