This set of Automata Theory online quiz focuses 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

View Answer

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(n^{2})

b) O(n^{3})

c) O(2^{n})

d) None of the mentioned

View Answer

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 n

^{2}states.

3. For a _________ state DFA, the time taken for DFA-NFA conversion is O(n).

a) n

b) n^{1/2}

c) n^{2}

d) 2^{n}

View Answer

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

d) none of the mentioned

View Answer

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

^{3}4

^{n}), 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

View Answer

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

^{3}.

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

View Answer

Explanation: We can eliminate e-transitions from an n state epsilon-NFA to build an ordinary NFA in O(n

^{3}) 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

View Answer

Explanation: 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

View Answer

Explanation: 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

View Answer

Explanation: 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

View Answer

Explanation: 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.

**Sanfoundry Global Education & Learning Series – Automata Theory.**

To practice all areas of Automata Theory for online Quizzes, __here is complete set of 1000+ Multiple Choice Questions and Answers__.