GATE 2008
March 14, 2025GATE 2008
March 14, 2025GATE 2008
| Question 48 |
Which of the following statements is false?
| Every NFA can be converted to an equivalent DFA | |
| Every non-deterministic Turing machine can be converted to an equivalent deterministic Turing machine
| |
| Every regular language is also a context-free language
| |
| Every subset of a recursively enumerable set is recursive |
Question 48 Explanation:
Every NFA can be converted into DFA (as there exist a standard procedure to convert NFA into DFA). Also, every non-deterministic Turing machine can be converted to an equivalent deterministic Turing machine. Every regular language is also a CFL , since if a language can be recognized by Finite automata, then it must also be recognize by PDA (as PDA is more powerful than FA). But every subset of recursively enumerable need not be recursive.
Correct Answer: D
Question 48 Explanation:
Every NFA can be converted into DFA (as there exist a standard procedure to convert NFA into DFA). Also, every non-deterministic Turing machine can be converted to an equivalent deterministic Turing machine. Every regular language is also a CFL , since if a language can be recognized by Finite automata, then it must also be recognize by PDA (as PDA is more powerful than FA). But every subset of recursively enumerable need not be recursive.