recategorized by
956 views
0 votes
0 votes

Which of the following pairs have different expressive power?

  1. Single-tape-turing machine and multi-dimensional turing machine
  2. Multi-tape-turing machine and multi-dimensional turing machine
  3. Deterministic push down automata and non-deterministic push down automata
  4. Deterministic finite automata and non-deterministic finite automata
recategorized by

4 Answers

0 votes
0 votes
Option C is correct. Because there are some NPDAs for which a DPDA is not availabe.
Answer:

Related questions

1 votes
1 votes
7 answers
2
go_editor asked Mar 24, 2020
1,450 views
Consider the languages $L_{1}= \phi$ and $L_{2}=\{1\}$. Which one of the following represents $L_{1}^{\ast}\cup L_{2}^{\ast} L_{1}^{\ast}$?$\{\in \}$$\{\in,1\}$$\phi$$1^{...