Theory Of Computation

“Conversions among Representations”.

1. Which of the following conversion is not feasible?
a) Regular expression to automaton conversion
b) Automaton to Regular Expression Conversion
c) NFA to DFA
d) None of the mentioned
Answer: d

Explanation: Each of the four formats of representation of the regular language be it,
DFA, NFA, Regular Expression or e-NFA can be converted to the rest three forms.


2. The computation of e-closure of n-states takes ______ time.
a) O(n2)
b) O(n3)
c) O(2n)
d) None of the mentioned
Answer: b

Explanation: We must search from each of the n states along all arcs labelled e. If there
are n states, there can be no more than n2 states.


3. For a _________ state DFA, the time taken for DFA-NFA conversion is O(n).
a) n
b) n1/2
c) n2
d) 2n
Answer: a

Explanation: The conversion DFA to NFA is simple, and takes O(n) time on an n-state
DFA.


4. 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