Which formal 5-tuple correctly defines a Deterministic Finite Automaton (DFA)?
Option B is correct. Which formal 5-tuple correctly defines a Deterministic Finite Automaton (DFA)? Answer: Q, \Sigma , \delta , q₀, F where $\delta$: Q $\times \Sigma → Q$.
In an NFA with n states, what is the maximum number of states in its equivalent minimal DFA constructed via subset construction?
Option B is correct. In an NFA with n states, what is the maximum number of states in its equivalent minimal DFA constructed via subset construction? Answer: $2^n$.
Which theorem provides the necessary and sufficient condition for a language to be regular by defining an equivalence relation of finite index on $\Sigma *$?
Option A is correct. Which theorem provides the necessary and sufficient condition for a language to be regular by defining an equivalence relation of finite index on $\Sigma *$? Answer: Myhill-Nerode Theorem.
What is the time complexity of Hopcroft's algorithm for minimizing a DFA with n states over an alphabet $\Sigma$?
Option E is correct. What is the time complexity of Hopcroft's algorithm for minimizing a DFA with n states over an alphabet $\Sigma$? Answer: O(|$\Sigma | n log n)$.
Which equation represents Arden's Theorem for solving regular expressions of the form R = Q + RP (where P does not contain $\epsilon )$?
Option C is correct. Which equation represents Arden's Theorem for solving regular expressions of the form R = Q + RP (where P does not contain $\epsilon )$? Answer: R = QP*.