# Construct DFA’s Accept all strings containing “ 011 ” or “ 001 ” as a substring and should not contain “ 010 ” as substring

My question is

Accept all strings containing “ 011 ” or “ 001 ” as a substring and should not contain “ 010 ” as substring

for the following languages over the alphabet {0,1}

i have solve it but , i have doubt if i can make the string contain 010 as substring goes to dead state ?!!!

• Your DFA accepts string like "011010" or "0010" although they are not in the language. So you need to use more final states and when DFA detects occurrence of substring "010" it should make a transition to the trap state. – kntgu Jun 5 '17 at 23:49

Make sure the transition function for the input DFAs is complete. The new set of states for the DFA is the cartesian product of the states of the 2 DFAs $Q' = Q_1 \times Q_2$. The transition function looks at the 2 states independently: $\delta'((Q_1, Q_2), s) = (\delta_1(Q_1, s), \delta_2(Q_2, s))$. The accepting states are those where both the original states are accepting $F' = F_1 \times F_2$.
For the union of the languages (string must be accepted by either DFA) it's the same except that the accepting state is where 1 or both of the states is accepting: $F' = (Q_1, F_2) \cup (F_1, Q_2)$. Here it is important that the transition functions are complete.
For completeness the negation of a DFA is the DFA where the accepting states are the states that are non accepting in the original DFA $F' = Q \backslash F$. Again it is important here that the transition function is complete.