Search code examples
statedfaautomatanfa

Intersection of two DFA, how many states? Final States?

Consider the following languages over = {0, 1},

A = {2 : w contains 011 as a substring} B = the language matched by the regular expression 0(0 + 1)*1

Let M(B) be the DFA obtained by converting N(B) using the subset construction with all unnecessary states removed. Let ¬M(B) be the DFA obtained by swapping the final and non-final states of MB. Let M be the product of M(A) and ¬M(B) with all unnecessary state removed.

How many states would M have? How many final states would M have? How many states does M(B) have? This question has been boggling me, I have spent a few hours on jFlap putting together the intersection of these two DFA, for A and ¬B. No success. Thank you.

Solution

  • The language M has to satisfy 2 conditions,

    1) M(A) - has to have a substring 011

    2) ¬M(B) - should not start with 0 and end with 1

    You can solve this by breaking the language M into 2 parts,

    1) that starts with 0 but does not end with 1 and having substring 001

    2) and another that starts with 1 and having substring 001

    Therefore the DFA for M would be something like this

    The DFA

    The states from 2-5 takes care of part 1, and states from 6-9 takes care of part 2