Search code examples
regexregular-languageautomatadfanfa

Finding the complement of a DFA?

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

Solution

  • 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 LR) 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 LR:

    • reverse all edges (arcs) in the transition diagram

    • the accepting state for the LR 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:

    00+1

    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):

    completeDFA

    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.

    complement

    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