in Theory of Computation retagged by
1,013 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
in Theory of Computation retagged by
1.0k views

3 Comments

Option C is correct
0
0
Option C is Right
0
0

option C

0
0

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