Question

With reference to Automaton to Regular Expression Conversion, for each of the n rounds, where n is the number of states of DFA, we can _________ the size of the regular expression constructed.

(a) double

(b) triple

(c) quadruple

(d) none of the mentioned

The question was posed to me in an interview for job.

This intriguing question comes from Conversions among Representations in section Properties of Regular Languages of Automata Theory

Answer 1

The correct answer is (c) quadruple

The explanation: We can quadruple the size of the regular expression per round. Thus, we can simply write n^3 expressions can take time O(n^34^n), where n =number of states of the DFA.