250+ TOP MCQs on Conversion by Eliminating states and Answers

Automata Theory MCQs 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

Answer: c
Clarification: We use this algorithm to simplify a finite automaton to regular expression or vice versa. We eliminate states while converting a 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

Answer: d
Clarification: 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

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

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

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

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

Answer: a
Clarification: 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λ.

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

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

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

Answer: d
Clarification: 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

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