The construction time for DFA from an equivalent NFA (m number of node — PYQDeck

PyQdeckBEU PYQ Archive Subjects

Back to the 2021 paper

Module 1: Introduction, Regular languages and finite automata

20212m

The 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)$

Search Google Ask AI

Similar questions

FORMAL LANGUAGE & AUTOMATA THEORYThe 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)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 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

PreviousA minimum state deterministic FA accepting the language L = \{w \mid w \in \{0, 1\}^*\} where number of 0's and 1's in w are divisible by 3 and 5 respectively, has (i) 15 states (ii) 11 states (iii) 10 states (iv) 9 states NextTabulate Chomsky hierarchy of grammar with an example for each.