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 ?!!!

enter image description here

  • 1
    $\begingroup$ 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. $\endgroup$ – kntgu Jun 5 '17 at 23:49

To construct the DFA for a cross-section of the languages (string must be accepted by both DFAs) You can work as follows:

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.