Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


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? enter image description here

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?

share|cite|improve this question
$\{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
up vote 1 down vote accepted

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.

share|cite|improve this answer
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$$\cap$L$_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$_1$XQ$_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$$\in$Q$_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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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