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

automatacomputer science

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

Best Answer

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.

Related Question