Automata Theory Questions and Answers – Conversion by Eliminating states

This set of Automata Theory MCQs focuses on “Conversion by Eliminating states”.

1. Which of the following is an utility of state elimination phenomenon?
a) DFA to NFA
b) NFA to DFA
c) DFA to Regular Expression
d) All of the mentioned
View Answer

Answer: c
Explanation: We use this algorithm to simplify a finite automaton to regular expression or vice versa. We eliminate states while converting given finite automata to its corresponding regular expression.

2. If we have more than one accepting states or an accepting state with an outdegree, which of the following actions will be taken?
a) addition of new state
b) removal of a state
c) make the newly added state as final
d) more than one option is correct
View Answer

Answer: d
Explanation: If there is more than one accepting state or if the single accepting state as an out degree, add a new accepting state, make all other states non accepting, and hold an e-transitions from each former accepting state to the new accepting state.

3. Which of the following is not a step in elimination of states procedure?
a) Unifying all the final states into one using e-transitions
b) Unify single transitions to multi transitions that contains union of input
c) Remove states until there is only starting and accepting states
d) Get the resulting regular expression by direct calculation
View Answer

Answer: b
Explanation: While eliminating the states, we unify multiple transitions to one transition that contains union of input and not the vice versa.
advertisement
advertisement

4. Can the given state diagram be reduced?
The state q2 can be eliminated with ease
a) Yes
b) No
View Answer

Answer: a
Explanation: The state q2 can be eliminated with ease and the reduced state diagram can be represented as:
The reduced state diagram of state q2 can be eliminated with ease

5. Which of the following methods is suitable for conversion of DFA to RE?
a) Brzozowski method
b) Arden’s method
c) Walter’s method
d) All of the mentioned
View Answer

Answer: a
Explanation: Brzozowski method takes a unique approach to generating regular expressions. We create a system of regular expressions with one regular expression unknown for each state in M, and then we solve the system for Rλ where Rλ is the regular expression associated with starting state qλ.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

6. State true or false:
Statement: The state removal approach identifies patterns within the graph and removes state, building up regular expressions along each transition.
a) true
b) false
View Answer

Answer: a
Explanation: This method has the advantage over the transitive closure technique as it can easily be visualized.

7. The behaviour of NFA can be simulated using DFA.
a) always
b) never
c) sometimes
d) none of the mentioned
View Answer

Answer: a
Explanation: For every NFA, there exists an equivalent DFA and vice versa.
advertisement

8. It is suitable to use ____________ method/methods to convert a DFA to regular expression.
a) Transitive Closure properties
b) Brzozowski method
c) State elimination method
d) All of the mentioned
View Answer

Answer: d
Explanation: For converting RE to DFA , first we convert RE to NFA (Thompson Construction), and then NFA is converted into DFA(Subset Construction).

9. State true or false:
Statement: For every removed state, there is a regular expression produced.
a) true
b) false
View Answer

Answer: a
Explanation: For every state which is eliminated, a new regular expression is produced. The newly generated regular expression act as an input for a state which is next to removed state.
advertisement

10. Is it possible to obtain more than one regular expression from a given DFA using the state elimination method?
a) Yes
b) No
View Answer

Answer: a
Explanation: Using different sequence of removal of state, we can have different possible solution of regular expressions. For n-state deterministic finite automata excluding starting and final states, n! Removal sequences are there. It is very tough to try all the possible removal sequences for smaller expressions.

Sanfoundry Global Education & Learning Series – Automata Theory.
To practice MCQs on all areas of Automata Theory, here is complete set of 1000+ Multiple Choice Questions and Answers.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]

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.