Automata Theory Questions and Answers – Conversions among Representations

This set of Automata Theory Multiple Choice Questions & Answers (MCQs) 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

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
View Answer

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
View Answer

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

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

Answer: c
Explanation: We can quadruple the size of the regular expression per round. Thus, we can simply write n3 expressions can take time O(n34n), 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

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

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

Answer: a
Explanation: We can eliminate e-transitions from an n state epsilon-NFA to build an ordinary NFA in O(n3) 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

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

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

Answer: a
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

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

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

Answer: a
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, here is complete set of 1000+ Multiple Choice Questions and Answers.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.