971 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.

(C) is the right answer
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,137 views
1 vote