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

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?
b) removal of a state
c) make the newly added state as final
d) more than one option is correct

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

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

4. Can the given state diagram be reduced?

a) Yes
b) No

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

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

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

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

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

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

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

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.

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