Home » Theory of Computation » Theory of computation miscellaneous » Question

Theory of computation miscellaneous

Easy Questions

Theory of Computation

Theory of computation miscellaneous
  1. Which of the following pairs have different expressive power?
    1. Deterministic Finite Automata (DFA) and Nondeterministic Finite Automata (NFA)
    2. Deterministic Push Down Automata (DPDA) and Nondeterministic Push Down Automata (NPDA)
    3. Deterministic single-tape turing machine and nondeterministic single tape turing machine
    4. Single-tape turing machine and multi-tape turing machine
Correct Option: B

DPDA and NPDA because an NPDA cannot be converted into DPDA.


Your comments will be displayed only after manual approval.