250+ TOP MCQs on Conversions among Representations and Answers

Automata Theory online quiz on “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
Clarification: 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(n²)
b) O(n³)
c) O(2ⁿ)
d) None of the mentioned

Answer: b
Clarification: 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 n² states.

3. For a _________ state DFA, the time taken for DFA-NFA conversion is O(n).
a) n
b) n^1/2
c) n²
d) 2ⁿ

Answer: a
Clarification: 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
d) none of the mentioned

Answer: c
Clarification: We can quadruple the size of the regular expression per round. Thus, we can simply write n³ expressions can take time O(n³4ⁿ), where n =number of states of the DFA.

5. Conversion of regular expression to e-NFA takes ___________ time.
a) linear
b) exponential
c) logarithmic
d) none of the mentioned

Answer: a
Clarification: It is possible to parse the expression efficiently, using a technique that takes only O(n) time on a expression of length n³.

6. The conversion of NFA to DFA can be done in:
a) exponential time
b) linear time
c) logarithmic time
d) all of the mentioned

Answer: a
Clarification: We can eliminate e-transitions from an n state epsilon-NFA to build an ordinary NFA in O(n³) time, without changing the number of states.Next, producing to DFA can take exponential time.

7. Which of the following cannot be converted in an ordinary NFA?
a) DFA
b) Regular Expression
c) e-NFA
d) None of the mentioned

Answer: d
Clarification: Each of the following can expressed in terms of ordinary NFA with different time complexities.

8. NFA to DFA conversion is done via
a) Subset Construction method
b) Warshalls Algorithm
c) Ardens theorem
d) None of the mentioned

Answer: a
Clarification: Powerset or subset construction method is a standard method for converting a non deterministic finite automata into DFA which recognizes the same formal language.

9. State true or false:
Statement: Regular expression can directly be converted to DFA without intermediate steps.
a) true
b) false

Answer: b
Clarification: There exists subsequent steps like formation of epsilon-NFA and NFA before the formation of corresponding DFA.

10. Is the following statement correct?
Statement: Thompson construction is used to convert Regular expression to finite automata.
a) Yes
b) No

Answer: a
Clarification: Thompson’s Construction is used to find out a Finite Automaton from a Regular Expression. We will reduce the regular expression into smallest regular expressions and convert them to NFA and finally to DFA.