question

Question

Which of the following statements is/are true about the automata?
(i) DFA is more efficient but less powerful than NFA
(ii) DPDA is more powerful but less efficient than NPDA
(iii) DTM is more efficient but less powerful than NTM
(a) (i), (ii) & (iii) (b) Only (i) & (ii)
(c) Only (ii) & (iii) (d) Only (i) & (iii)

Comments

I don't think any of them is true:

(i) Both DFA and NFA are equivalent in power.

(ii)NPDA is more powerful than DPDA.

iii) Nondeterministic Turing machines are equivalent with Deterministic Turing machines .

---

i exactly mean the same! none of them is going to be a correct option.

Answer 1

(d) Only (i) and (iii) 

Refer the following link in case you want to study about expressive powers, deterministic and non-deterministic automata. 

http://www.gripinit.com/2015/04/08/automata-theory-an-introduction/

Comments

I agree that DFA and DTM is more efficient,as also mentioned in the link attached,but the statement in this question also talks about being powerful,whic is false in both cases.To be true,both the parts of the statement should be true.

---

^ you are correct (y)

---

@Shradha I agree. I've seen a similar question in another mock test too.

So, there's nothing as less powerful and more powerful when we talk about Deterministic and Non-deterministic machines. Is that what you mean?

Answer 2

4 is correct answer

1) dfa is efficient but less powerfull than nfa but their capacity is same means for each nfa there exists a equivalent dfa.

2) npda is always more powerful than dpda

3) turing machine is sameas dfa