DFA for complement language of given language

Question

We have a language W over the alphabet {a,b,c,d,e,f,g} that is defined by, starting with :

<A> ::= <A> <Z> 'c' | <A> <X> 'd' | 'b'
<Z> ::= <Y'> 'e' <Z> | ''
<Y'> ::= 'f' | 'g'
<X> ::= <X> 'a' | 'e'

What are the rules when it comes to make a DFA that regocnizes the complement language of W? With other words a DFA that recognizes all the string over the given alphabet that is not in W.

I have attempted it and from what I have read it says that the complement language of a given language in a DFA is just to change the accepting states to non accepting states and then you are good, but i cant seem to correctly understand the transitions between the different states.

Answer 1

What you list is a grammar and not a DFA, and finding a grammar for the complement of a regular language is not quite as immediate as finding a DFA for the complement given a DFA for the language.

If you have a DFA M for language L, the then to construct a DFA M' for the complement L' of L, you do just swap the accepting states to non-accepting and vice versa... so M' is defined as:

• M' has the same alphabet as M
• M' has the same states as M
• M' has the same initial state as M
• A' = Q \ A, where A' are the accepting states of M', Q is the shared set of states of both automata, A is the set of accepting states of M, and \ is set difference
• M' has the same transition function as M

If you want a grammar for the complement, you can:

1. construct a DFA from your grammar by first reducing the grammar to a left-regular grammar and then interpreting the productions as transitions and nonterminals as states
2. construct the DFA for the complement as described above
3. interpret the states of the resulting DFA as nonterminals and the transitions as productions of a new left-regular grammar for the language of the complement