Multiple choice

Which of the following statements is false?

  1. Every NFA can be converted to an equivalent DFA

  2. Every non-deterministic Turing machine can be converted to an equivalent deterministic Turing machine

  3. Every regular language is also a context-free language

  4. Every subset of a recursively enumerable set is recursive
Reveal answer Fill a bubble to check yourself
D Correct answer
Explanation

(1) true since NFA $\rightarrow$DFA conversion possible. (2) N.D turing M/C so true. (3) every rex is a CFL but reverse is not true. (4) false, since these may be proper subset of each other so not necessary

Keep practicing — related questions