# Find the DFA for the language $L = \{a^nb: n \geq 0\} \cup \{b^na : n \geq 1\}$

Problem

Find the DFA for the language $$L = \{a^nb: n \geq 0\} \cup \{b^na : n \geq 1\}$$

This is a problem from the book "An Introduction to Formal Languages amd Automata 4th edition", exercise 2 b) page 68.

Since there are very few examples in the textbook, I found it very difficult to test my work, especially self-taught. This is my attempt, does it look reasonable?

Another question is: how does $\cup$ differ from $\cap$ in a DFA? For instance, if we change the language above to: $$L = \{a^nb: n \geq 0\} \cap \{b^na : n \geq 1\}$$ With NFA, the $\cup$ is straightforward, but for DFA, I'm not quite sure. Any suggestion?

-
$\{a^nb: n \geq 0\} \cap \{b^na : n \geq 1\}$ is the empty language. –  Chris Eagle Jun 17 '11 at 8:41
@Chris Eagle: It actually is, Thank you –  Chan Jun 17 '11 at 18:51

Your DFA looks good to me. I don't know what you mean by one thing "differentiating" with another.

EDIT: I have three suggestions for treating the intersection (and no promise that they will be helpful).

1. Since you say you can handle the NFA, do that, and then apply techniques you may know for turning an NFA into a DFA.

2. Using De Morgan's laws, any intersection can be turned into a combination of union and negation: $A\cap B=(A'\cup B')'$. So if you can handle union and negation, you can handle intersection.

3. My colleague, Chris Cooper, has written up some notes for a discrete math course we teach here at Macquarie University, and I believe he handles all these problems in those notes. I don't have the URL handy, but you might find the notes if you do a little sniffing about.

-
Thank you. Sorry for the confusion, I used the wrong word. I meant to say they're different, the right word should be "differ". –  Chan Jun 17 '11 at 7:47

For NFA $\cap$ is easy to simulate. But for DFA we can view language as two different languages, L = L$_1$$\capL_2 as L_1 and L_2 and construct their DFA and then for implementing L as: Let DFA for L_1 is D_1 = (Q_1,\sum,q_o$$_1$,$\delta$$_1,F_1) For L2 = D_2 = (Q_2,\sum,q_o$$_2$,$\delta$$_2,F_2) And DFA D for L can be defined as : 1: Q = Q_1XQ_2, we view state as binary tuple like [q_1,q_2] 2: \delta : [Q_1,Q_2]X\sum$$\implies$[Q$_1$,Q$_2$] , $\delta$([q$_1$,q$_2$],a) = [$\delta$$_1(q_1,a),\delta$$_2$(q$_2$,a)] where q$_1$$\inQ_1. q_2$$\in$Q$_2$, $\forall$ a, a$\in$$\sum$.
3: F = F$_1$XF$_2$ This DFA D only accepts those languages which are accepted by both D1 and D2, i.e L

-