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
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
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
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
View Answer
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
View Answer
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λ.
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
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
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
View Answer
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
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
View Answer
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.
- Practice Computer Science MCQs
- Apply for Automata Theory Internship
- Buy Computer Science Books
- Buy Automata Theory Books
- Apply for Computer Science Internship
