Complement of a DFA can be obtained bya)making starting state as final...
String accepted in previous DFA will not be accepted and non accepting string will be accepted .
View all questions of this test
Complement of a DFA can be obtained bya)making starting state as final...
Complement of a DFA can be obtained by making final states non-final and non-final states final.
To understand how to obtain the complement of a DFA (Deterministic Finite Automaton), let's break down the process into steps:
Step 1: Understand the DFA
First, we need to have a clear understanding of the given DFA. A DFA consists of a set of states, an input alphabet, a transition function, a start state, and a set of final states. It is represented using a state transition table or a state transition diagram.
Step 2: Identify the Final States
In the given DFA, we need to identify the final states. These are the states where the DFA accepts the input and stops. Final states are typically denoted by double circles in a state transition diagram.
Step 3: Make Final States Non-Final
To obtain the complement of the DFA, we need to make the final states non-final. This means that the DFA should not accept the input when it reaches these states. To do this, we can simply change the status of the final states from final to non-final. In a state transition diagram, we can remove the double circles from the final states.
Step 4: Make Non-Final States Final
Next, we need to make the non-final states final. This means that the DFA should accept the input when it reaches these states. To achieve this, we can change the status of the non-final states from non-final to final. In a state transition diagram, we can add double circles to the non-final states.
Step 5: Resultant Complement DFA
After making the necessary changes to the final and non-final states, we obtain the complement of the given DFA. The resultant DFA will have the same set of states, the same input alphabet, the same transition function, and the same start state as the original DFA. However, the final and non-final states will be swapped.
Example:
Let's consider a simple DFA with three states: A, B, and C. The start state is A and the final state is C. The transition function is as follows:
- A on input '0' goes to B
- A on input '1' goes to A
- B on input '0' goes to C
- B on input '1' goes to A
- C on input '0' goes to C
- C on input '1' goes to C
In this example, the final state is C. To obtain the complement of this DFA, we need to make C non-final and A, B non-final. The resulting complement DFA will have final states as A and B, and the non-final state as C.
Therefore, option 'C' is the correct answer.
To make sure you are not studying endlessly, EduRev has designed Computer Science Engineering (CSE) study material, with Structured Courses, Videos, & Test Series. Plus get personalized analysis, doubt solving and improvement plans to achieve a great score in Computer Science Engineering (CSE).