12/4    If a DFA of M accepts all languages in L, then what exactly is
        the "complement of L"? Isn't the complement of L everything that
        M does not accept, which is an infinite set?
        \_ Usually you phrase things as "a DFA M accepts the language L"
           with the extraneous "in" and "of".  The complement of L is
           usually everything not in L which is what M does not accept
           which can be an infinite set.  This is not a problem.  Consider
           the language L = {} (e.g. L contanis only the empty string).
           In this case L complement is all non-empty strings.  It is
           trivial to build a DFA to recognize L complement.  -emin
        \_ ok thx emin. I can prove that if a DFA M can accepts all L
           in polynomial time, then ~L can also be accepted in polynomial
           time. However, how do I prove/disprove that if a DFA M can
           accept context free grammar, then ~M can accept all ~L?
           \_ DFA's can't accept CFG's.  Did you mean "PDA M"?
              Take your method of converting M into ~M and prove that
              it accepts the inverse language.
              \_ Actually DFA's can accept any CFG which is also a
                 regular language.  For example, the language L = {}
                 is both regular and context free.  However, as you
                 point out, there exist CFG's which DFAs can not
                 recognize.  To the original poster: I'm not quite
                 sure what question you are asking, but the following
                 information might be useful to you.  CFGs are not
                 closed under complement.  That is if L is a CFG then
                 ~L need not be a CFG. -emin
                        \_ YOU KICK ASS    -original poster taking CS GRE