Using complement to create a DFA with a specific condition

Question

In my understanding, the complement of an automaton is when the final states become non-final and the non-final states become final.

I tried to apply this method to create an automaton that never contains a certain substring. I first tried to create a DFA that always contains a certain substring at least once, planning to then give its complement for the opposite property. Let's say the alphabet is {a, b} and the substring is "bab".

I started with the regular expression (a|b)*bab(a|b)* to create an automaton that contains any word (including no word) before & after the substring "bab", which occurs at least once. However, by this point, I realised a complement would not result in the desired automaton, as the transitions b->a->b would still exist regardless, and even so, with a final state in the (a|b)* segment of the automaton, the substring "bab" is always possible.

I deduced that I misunderstood this method of creating a DFA. In this example, I am looking for a DFA that defines a language with every word except words with a given substring, but I would like to know if there is a general method to obtain DFAs with opposite conditions, such as an even number of characters, never having a character appear a certain amount of times, etc. My question is this; how do you create a DFA with certain conditions and then give the complement that results in a DFA without those conditions?

Answer 1

If the automaton you construct is complete, complementation works just as you described.

Are you sure that the automaton you construct is a DFA, i.e., it is deterministic? When you speak about "the transitions b->a->b" and a "final state in the $(a|b)^*$ segment of the automaton" it sound like you have an initial state with a loop for both a and b, then the "transitions b->a->b" and a final state with a loop for a and b again. But this is not deterministic: from the start state with b you have the option of staying there or going into the b->a->b sequence.

A DFA would be one with the transitions:

• $q_0,a\rightarrow q_0,\ \ q_0,b\rightarrow q_b,$
• $q_b,a\rightarrow q_a,\ \ q_b,b\rightarrow q_b,$
• $q_a,a\rightarrow q_0,\ \ q_a,b\rightarrow q_f,$
• $q_f,a\rightarrow q_f,\ \ q_f,b\rightarrow q_f.$

Now you can try the complementation with this one.