1,013 views

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

Option C is correct
Option C is Right

option C

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.

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

Option C) is correct , Complement of DFA can be obtained by making non-final states as final and final as non-final.
by

1
1,168 views
1 vote