The construction time for DFA from NFA with m nodes is: (i) O(m^2) (ii — PYQDeck

PyQdeckBEU PYQ Archive Subjects

Back to the 2021 paper

Module 1: Introduction & Regular Languages

20212m

The construction time for DFA from NFA with $m$ nodes is:

(i) $O(m^2)$
(ii) $O(2^m)$
(iii) $O(m)$
(iv) $O(\log m)$

Search Google Ask AI

Similar questions

Formal Language & Automata TheoryThe construction time for DFA from an equivalent NFA (m number of node) is (i) O(m^2) (ii) O(2^m) (iii) O(m) (iv) O(\log m)20212m FORMAL LANGUAGE & AUTOMATA THEORYFor an NFA with n states, the minimized DFA has: (i) m \le 2^n (ii) n \le m (iii) one accept state (iv) m = 2^n20212m 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 above20212m Formal 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 = 2n20192m

PreviousA minimum state DFA for the language: L = \{ w \in \{0,1\}^* : \#0(w) \equiv 0 \mod 3,\; \#1(w) \equiv 0 \mod 5 \} has: (i) 15 states (ii) 11 states (iii) 10 states (iv) 9 states NextTabulate the Chomsky hierarchy of grammars with an example for each.