Construct a new DFA B from A where L(B) = L(A) - {w | w∈E* }

Question

Im having a bit of difficulty with the following question:

Given a DFA A = (E = {a,b,c} , Q ,q0 ,F , l) (where l is the transition function), build a new DFA B such that L(B) = L(A) - {a}.

Now I understand that Eb = Ea, but how can I define B transition function, or accepting states, without knowing the accepting states of A?

Thank you.

Answer 1

First, let us construct a DFA called C which accepts w. This DFA has |w| + 2 states: one initial state, one dead state, one accepting state.

Second, let us construct a DFA called D which accepts everything except w. Simply change all non-accepting states to accepting, and vice versa.

Third, let us construct B using the Cartesian Product Machine construction on input DFAs A and D with intersection as the operator. This DFA will hav |Q| x (|w| + 2) states in total.

The language of B is everything accepted by A and D simultaneously. D accepts anything that isn't w; so, B accepts anything in L(A) that isn't w, as required.

EDIT: Some more detail about what B ends up looking like.

Let the states of A be QA and the states of D be QD. Let the accepting states of A be FA and the accepting states of D be FD. Let dA be the transition function for A and dD be the transition function for D. From our construction above, we have:

• Q = {(x, y) for x in QA y in QD}
• E = the same alphabet as A and D, assumed to be the same. If w contains only symbols in A's alphabet then just use A's alphabet. If w contains symbols not in A's alphabet then w is not in L(A) and we can just let B = A.
• q0 = (q0, q0')
• F = {(x, y) in Q | x in FA and y in FD}
• d((x, y), s) = (dA(x, s), dD(y, s))

As for what D looks like:

• QD = {q0', q1', …, q(|w|+1)'}
• E = same as A's
• q0' is the initial state
• FD = QD \ {q(|w|)}
• d(qi, s) = q(i+1) if s is the (i+1)th symbol of w, or q(|w|+1) otherwise