Nielit Scentist-B [02-12-2018]
October 4, 2023GATE 2010
October 4, 2023UGC NET CS 2005 june-paper-2
|
Question 1
|
Which of the following is not true ?
|
Power of deterministic automata is equivalent to power of non-deterministic automata.
|
|
|
Power of deterministic pushdown automata is equivalent to power of non-deterministic pushdown automata.
|
|
|
Power of deterministic turing machine is equivalent to power of non-deterministic turing machine.
|
|
|
All the above
|
Question 1 Explanation:
→ NPDA(Non deterministic Pushdown Automata) and DPDA(Deterministic Pushdown Automata) are not equivalent in power.
→ NPDA is more powerful than DPDA which means for every language for which a dpda exist, there exist an NPDA but there are some languages that are accepted by NPDA but are not accepted by DPDA.
→ In case of DFA and NFA they are equivalent in power. So for every language accepted by DFA there exists an NFA and vice versa.
Hence,we can’t convert NPDA to DPDA always and we can convert NFA to an equivalent DFA always.
→ In case of DTM and NTM they are equivalent in power.
→ NPDA is more powerful than DPDA which means for every language for which a dpda exist, there exist an NPDA but there are some languages that are accepted by NPDA but are not accepted by DPDA.
→ In case of DFA and NFA they are equivalent in power. So for every language accepted by DFA there exists an NFA and vice versa.
Hence,we can’t convert NPDA to DPDA always and we can convert NFA to an equivalent DFA always.
→ In case of DTM and NTM they are equivalent in power.
Correct Answer: B
Question 1 Explanation:
→ NPDA(Non deterministic Pushdown Automata) and DPDA(Deterministic Pushdown Automata) are not equivalent in power.
→ NPDA is more powerful than DPDA which means for every language for which a dpda exist, there exist an NPDA but there are some languages that are accepted by NPDA but are not accepted by DPDA.
→ In case of DFA and NFA they are equivalent in power. So for every language accepted by DFA there exists an NFA and vice versa.
Hence,we can’t convert NPDA to DPDA always and we can convert NFA to an equivalent DFA always.
→ In case of DTM and NTM they are equivalent in power.
→ NPDA is more powerful than DPDA which means for every language for which a dpda exist, there exist an NPDA but there are some languages that are accepted by NPDA but are not accepted by DPDA.
→ In case of DFA and NFA they are equivalent in power. So for every language accepted by DFA there exists an NFA and vice versa.
Hence,we can’t convert NPDA to DPDA always and we can convert NFA to an equivalent DFA always.
→ In case of DTM and NTM they are equivalent in power.
Subscribe
Login
0 Comments