retagged by
1,572 views
2 votes
2 votes

Complement of a $DFA$ can be obtained by :

  1. making starting state as final state.
  2. make final as a starting state.
  3. making final states non-final and non-final as final.
  4. None of the options
retagged by

3 Answers

2 votes
2 votes


Complement

Let M = < Q ,,q0 ,  , A > be a DFA that accepts a language L.

 

Then a DFA that accepts the complement of L, i.e. * - L, can be obtained by swapping its accepting states with its non-accepting states, that is Mc = < Q ,  , q0 ,  , Q - A > is a DFA that accepts * - L .

For example the following DFA accepts the language a+ over  = { a , b }.



            



A DFA that accepts its complement is obtained from the above DFA by changing all single circles to double circles and vice versa as shown below.



            



Remark 1: If we have NFA rather than DFA, we must first convert it to DFA before swapping states to get its complement.

Remark 2: Since a language is regular if and only if it is accepted by some NFA, the complement of a regular language is also regular.

So C is correct.

Ref: https://www.cs.odu.edu/~toida/nerzic/390teched/regular/fa/complement.html

0 votes
0 votes
The compliment of a DFA can be obtained by making the final states as non final states and vice vers.

(C) is the right answer
0 votes
0 votes
Option C) is correct , Complement of DFA can be obtained by making non-final states as final and final as non-final.
Answer:

Related questions

2 votes
2 votes
4 answers
1
admin asked Mar 31, 2020
1,631 views
The automaton which allows transformation to a new state without consuming any input symbols : $NFA$$DFA$$NFA - 1$All of the options
1 votes
1 votes
4 answers
2
admin asked Mar 31, 2020
3,616 views
Concatenation Operation refers to which of the following set operations : UnionDotKleeneNone of the options
1 votes
1 votes
2 answers
3
1 votes
1 votes
2 answers
4
admin asked Mar 31, 2020
991 views
What is the relation between $DFA$ and $NFA$ on the basis of computational power ?$DFA$ $NFA$$NFA$ $DFA$EqualCan't be said