PyQdeck LogoPyQdeckSubjectsSyllabusBlog
Back to the 2026 paper

Module 1: Introduction, Lexical Analysis

20262m

Which statement is true regarding DFA and NFA?
(i) NFA is strictly more powerful than DFA
(ii) DFA and NFA recognize the same class of languages
(iii) DFA is strictly more powerful than NFA
(iv) Every NFA requires more states than every equivalent DFA

Search GoogleAsk AI
Worked SolutionAI Assisted

Answer: (ii) DFA and NFA recognize the same class of languages

Explanation

Both DFAs and NFAs recognize exactly the regular languages.

  • Every DFA is already an NFA (a special case).
  • Every NFA can be converted to an equivalent DFA by the subset construction.

So neither is more powerful, which rules out (i) and (iii). An NFA is often smaller than the equivalent DFA: an NFA with nn states may need up to 2n2^n DFA states. That is a size difference only, and option (iv) is false because many NFAs need no more states than their DFAs (a DFA is itself an NFA).

(ii)\boxed{\text{(ii)}}

Similar questions

Formal Language & Automata TheoryThe maximum number of states of a DFA converted from an NFA with n states is (i) n (ii) n^2 (iii) 2^n (iv) None of the above20212mFORMAL LANGUAGE & AUTOMATA THEORYThe maximum number of states of a DFA converted from an NFA with n states is: (i) n (ii) n^2 (iii) 2^n (iv) None of the above20212mFormal Language & Automata TheoryLet N be an NFA with n states and let M be the minimized DFA with m states recognizing the same language. Which of the following is necessarily true? (i) m \le 2^n (ii) n \le m (iii) M has one accept state (iv) m = 2^n20212mFORMAL LANGUAGE & AUTOMATA THEORYLet N be an NFA with n states and let M be the minimized DFA with m states recognizing the same language. Which of the following is necessarily true? (i) m \le 2^n (ii) n \le m (iii) M has one accept state (iv) m = 2^n20232m
PreviousDynamic method dispatch is primarily used to implement: (i) Lexical analysis (ii) Constant folding (iii) Runtime polymorphism (iv) Register allocationNextExplain the different phases of compilation with a suitable example. Show the input and output produced at each phase.
Budget AppAndroid App

Pocketly on Android

Log daily food, travel, and hostel expenses instantly. Set monthly spending limits and see where your money goes without complex spreadsheets.

Install Pocketly