in Theory of Computation retagged by
1,265 views
1 vote
1 vote

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

  1. 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 push-down automata.
  4. Multi-tape Turing Machines are equivalent to Single-tape Turing Machines.
in Theory of Computation retagged by
by
1.3k views

4 Comments

B is the correct one

NPDA has more power than DPDA

1
1
B and C is the correct answer .
0
0
B is false  bcz npda is more powerful then dpda nd also c is false bcz tm is powerful than pda
0
0

2 Answers

0 votes
0 votes

Option B and C are False,

  1. Non-deterministic push-down automata is more powerful than deterministic push-down automata.
  2. Non-deterministic Turing Machines are powerful than deterministic push-down automata.
0 votes
0 votes

B). Non-deterministic push-down automata are equivalent to deterministic push-down automata....

 

Non-deterministic push down automata is NOT equivalent to deterministic push down automata....

Option (B) is false....

 

1. https://en.wikipedia.org/wiki/Nondeterministic_finite_automaton 

 

2. https://gateoverflow.in/1648/Gate-cse-1998-question-1-11

 

 

by
Answer:

Related questions