Finding the complement of a DFA?

Question

I am asked to show DFA diagram and RegEx for the complement of the RegEx (00 + 1)*. In the previous problem I had to prove that the complement of a DFA is closed and is a regular expression also, so I know that to convert a DFA, M to the complement, M`, I just need to swap the initial accepting states and final accepting states.

However, it appears that the initial accepting states for the RegEx are {00, 1, ^} and the final accepting states are {00, 1, ^} as well. So swapping them will just result in the exact same RegEx and DFA which seems contradictory.

Am I doing something wrong or is this RegEx supposed to not have a real complement?

Thank you

A DFA only has one initial state, so you're probably making a mistake there. Write the DFA itself and verify it before trying to complement it. — aaaaaa123456789, Feb 10 '13 at 21:26
Also, in order to complement the DFA, you just swap "final-ness" for each state -- that is, make every non-final state final, and every final state non-final. — aaaaaa123456789, Feb 10 '13 at 21:28
Not really -- keep in mind that the initial state is where it begins reading the string, so it has read nothing so far. There's transitions from it with 00 and 1, though. Maybe you should look up some info on DFAs? — aaaaaa123456789, Feb 10 '13 at 21:40
well I understand that. technically, it starts as a null string and then 00 or 1 can be read. but that would not change my predicament — Matt Hintzke, Feb 10 '13 at 21:49
It would, actually. Anyway, as I said, you don't have to touch the initial state (it's still the same) -- you just have to make every final state non-final, and every non-final state final. If you simplified your DFA (used the least states possible), then you should only have 1 final state (which is the initial) and 1-2 non-final states -- if that's the case, make the initial state non-final, and the rest of them final. — aaaaaa123456789, Feb 10 '13 at 21:53

score 40 · Accepted Answer · edited May 23 '17 at 10:30

As you says in question:

I know that to convert a DFA, M to the complement, M`, I just need to swap the initial accepting states and final accepting states.

Its not complement, but you are doing something like reverse of a language and regular languages are closure under reversal.

Reversal of DFA

What is the Reversal Language ?

The reversal of a language L (denoted L^R) is the language consisting of the reversal of all strings in L.

Given that L is L(A) for some FA A, we can construct an automaton for L^R:

reverse all edges (arcs) in the transition diagram

the accepting state for the L^R automaton is the start state for A

create a new start state for the new automaton with epsilon transitions to each of the accept states for A

Note: By reversing all its arrows and exchanging the roles of initial and accepting states of a DFA you may get an NFA instead.
_{that's why I written FA(not DFA)}

Complement DFA

Finding the complement of a DFA?

Defination: The complement of a language is defined in terms of set difference from Σ* (sigma star). that is L^' = Σ^* - L.

And the complement language (L^') of L has all strings from Σ* (sigma star) except the strings in L. Σ* is all possible strings over the alphabet Σ.
_{Σ = Set of language symbols}

To construct the DFA D that accepts the complement of L, simply convert each accepting state in A into a non-accepting state in D and convert each non-accepting state in A into an accept state in D.
(Warning! This is not true for NFA's)

_{A is DFA of L, D is for complement}

Note: To construct complement DFA, old DFA must be a complete means there should all possible out going edge from each state(or in other words δ should be a complete function).

Complement: reference with example

Complement DFA for Regular Expression (00+1)*

below is DFA named A:

But not this DFA is not complete DFA. transition function δ is partially defined but not for full domain Q×Σ (missing out going edge from q1 for lable 1).

Its complete DFA can be as follows (A):

In the above DFA, all possible transactions are defined (*for every pair of Q,Σ *) and δ is a complete function in this case.

Reff: to learn what is Partial Function.

New complement DFA D can be constructed by changing all final states q0 to not final states and vice-versa.

So in complement q0 become non-final and q1, q2 are the final states.

Now you can write Regular expression for complement language using ARDEN'S THEOREM and DFA I given.

Here I am writing Regular Expression for complement directly:

(00 + 1)* 0 (^ + 1(1 + 0)*)

where ^ is null symbol.

some helpful links:
From here and through my profile you can find some more helpful answers on FA. Also, two good links on properties of regular language: one, second

check this also [**HOW TO WRITE REGULAR EXPRESSION FOR A DFA**](http://stackoverflow.com/questions/7550711/what-is-the-language-of-this-deterministic-finite-automata/13965717#13965717) — Grijesh Chauhan, Feb 11 '13 at 17:41
what about dead state ??If the DFA of a language L contains a dead state ,then how to tackle it..??Do i have to make the dead state also as accepting state ? — Coffee_lover, Dec 10 '13 at 02:46
@Coffee_lover 'Dead state' means string is unaccepted. Suppose while processing a string you reach to a dead state then string is not belongs to language of DFA. E.g in diagram-2 in above answer state `q2` is dead state Now suppose you have a string `10110` then to process this string you need this move `q0--1-->q0--0-->q1--1-->q2--1-->q2--0-->q2` Notice in this once you reach a dead `q2` then you can't change state for all language symbols. -----Generally we can ignore drawing dead states in a DFA. — Grijesh Chauhan, Dec 10 '13 at 04:38
my question is about complement for eg. L=10110 now how to draw complemented DFA for it.. u said change accepting into non accepting and vice versa but what about dead state...do i consider it as a non accepting state and convert into accepting state while drawing the complemented dfa — Coffee_lover, Dec 10 '13 at 05:35
@Coffee_lover First read this answer [How does `“δ:Q×Σ→Q”` read in the definition of a DFA](http://stackoverflow.com/questions/14870130/how-does-qq-read-in-the-definition-of-a-dfa-deterministic-finite-accepto/14940382#14940382) Learn definition of complete DFA. Again 'Dead states' means a stat from which a 'Accepting state' is unreachable. See expression/statement `L = 10110` is wrong do you means `L = {10110}` because a language is a set. — Grijesh Chauhan, Dec 10 '13 at 06:15
sorry L={10110} but what to do about the dead state while finding the complement of DFA for L — Coffee_lover, Dec 10 '13 at 06:18
@Coffee_lover Oh! you remember!! yes I got job in New Delhi @ [taxspanner](http://www.taxspanner.com/). Thanks you dear — Grijesh Chauhan, Dec 10 '13 at 06:36
Can you provide me a link for TOC online references @Grijesh Chauhan — Coffee_lover, Dec 30 '13 at 05:02
@Coffee_lover Below in [comments of my linked answer](http://stackoverflow.com/a/14024179/1673391) I have shared some links. If I find something new then I will share more (as I know there are some TOC lecture video from *virtual-university* on Youtube.com --) — Grijesh Chauhan, Dec 30 '13 at 06:13
This is one of the very few places on the Interweb that actually explains the part of forming the complement of a DFA that trips everybody up: "complete DFA" — Ron Burk, Aug 17 '21 at 03:23

Finding the complement of a DFA?

1 Answers1

Reversal of DFA

Complement DFA

Linked