made easy

Question

Which of the following statement is not correct?

• A. If $L$ is accepted by NFA, then there exists a DFA that accepts $L$
  
• B. If $L$ is accepted by an NFA with $\in$ transition, then $L$ can be accepted by NFA without $\epsilon$ transition
  
• C. If $L$ is accepted by a non-deterministic PDA then it is not always true that $L$ is also accepted by deterministic PDA
  
• D. If $L$ is accepted by turing Machine, which halts on every w in $L$ then $L^{\prime}$ is recursively enumerable but not recursive

Answer 1

DFA, NFA, epsilon NFA all have same power so option a and b are true

opt c also true non-deterministic PDA is more powerful than deterministic PDA so there are some language which will be accepted by NDPDA but not DPDA

opt d is false because if it halts on w which is not in L then it will be recursive language

so ans is d