retagged by
1,267 views
1 votes
1 votes

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.
retagged by

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.
Answer:

Related questions

1 votes
1 votes
2 answers
1
admin asked Mar 31, 2020
1,673 views
If there is in NP-Complete language L whose complement is in NP, then complement of any language in NP is inPNPboth (A) and (B)None of these
2 votes
2 votes
2 answers
2
admin asked Mar 31, 2020
1,873 views
Which of the following regular expressions denotes a language comprising all possible strings over the alphabet $\{a,b\}$?$a^*b^*$$(a\mid b)^*$$(ab)^+$$(a\mid b^*)$
2 votes
2 votes
4 answers
3
admin asked Mar 31, 2020
908 views
If $L_1$ and $L_2$ are context free language and $R$ a regular set, then which one of the languages below is not necessarily a context free language?$L_1L_2$$L_1\cap L_2$...
4 votes
4 votes
4 answers
4