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

Chartulary

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. – Lenwood

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. – Lenwood

Well couldn't the initial state be 00 or 1? – Chartulary

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? – Lenwood

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 – Chartulary

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. – Lenwood

@MattHintzke let me know if you have other doubt. – Armin

Answer 1

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

Armin

check this also HOW TO WRITE REGULAR EXPRESSION FOR A DFA – Armin

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 ? – Ranged

@Ranged '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. – Armin

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 – Ranged

@Ranged First read this answer How does “δ:Q×Σ→Q” read in the definition of a DFA 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. – Armin

sorry L={10110} but what to do about the dead state while finding the complement of DFA for L – Ranged

@Ranged Oh! you remember!! yes I got job in New Delhi @ taxspanner. Thanks you dear – Armin

Can you provide me a link for TOC online references @Grijesh Chauhan – Ranged

@Ranged Below in comments of my linked answer 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 --) – Armin

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" – Midsection