I'm trying to solve DFA

Question

I have to do L1 U L2 and intersection L1 n L2

Answer 1

You can run through the formal Cartesian product machine construction to algorithmically derive automata for the intersection and union of L1 and L2. However, since these languages are so easy, it might be simpler to give the languages and just write down a DFA for each one.

L1 is the language of all strings of as and bs with at least one a. L2 is the language of all strings of as and bs with at least two bs.

To accept the intersection of L1 and L2, we need to see at least one as and two bs. Below, we have six states:

1. q0, the initial state, where we need one a and two bs
2. q1, where we still need two bs
3. q2, where we still need one b
4. q3, where we need no more (accepting state)
5. q4, where we still need one a and one b

6. q5, where we still need one a

   --->q0-a->q1-b->q2-b->q3 -b->q4-a->q2 q3 -b->q5-a->q3

(where transitions are missing, they are self loops)

Note that there are six states: this is the same as if we had done the Cartesian product machine construction on the original DFAs of two and three states, respectively.

For union, we can use the exact same DFA and change the set of accepting states to q1, q3, q5. This captures the fact that we now accept when either condition is true (and states q1 and q5 are where one, but not both (as in q3) conditions become satisfied).