# NFA to DFA for odd a's and even b's

The regular expression for accepting odd a's and even b's I calculated is: (aa)*a(bb)* and the NFA:

+-------+-----+---+
| State | a   | b |
+-------+-----+---+
|   A   | B,C |   |
|   B   |     | D |
|   C   | A   |   |
|   D   |     | B |
+-------+-----+---+


Now I want to convert this into DFA so I transform the transistion table as:

+-------+-----+---+
| State | a   | b |
+-------+-----+---+
|   A   |[BC] |   |
| [BC]  | A   | D |
+-------+-----+---+


I think that there's something wrong with DFA of it. It seems to have a missing transition from D to CB for 'b' which I don't see in table.

• Did you mean (aa)*(bb)*a? May 7 '16 at 10:03
• @KennyLau: Yes I mean (aa)*a(bb)*. May 7 '16 at 10:07

Your given regular expression is : $(aa)^*a(bb)^*$.

Regular language is : $\{a^{2m+1}b^{2n}|m,n\ge 0\}$

Your given NFA is for above language :

So, the transitition table for above NFA is :

+-------+-----+---+
| State | a   | b |
+-------+-----+---+
|   A   | B,C |   |
|   B   |     | D |
|   C   | A   |   |
|   D   |     | B |
+-------+-----+---+


Conversion from NFA to DFA :

+-------+-----+---+
| State | a   | b |
+-------+-----+---+
|   A   | B,C | Φ |
|  B,c  | A   | D |
|   D   | Φ   | B |
|   B   | Φ   | D |
|   Φ   | Φ   | Φ |
+-------+-----+---+


The DFA will be :

Hint: Let's consider your second table, it's not completed yet, since you have $D$ in the third column. So, you need another row: put $D$ into the column "State" and fill respective states into columns $a$ and $b$ (it should be $\emptyset$ and $B$ respectively). Then you'll need to do the same for state $B$. And so on, you'll need a new row for every new state that could be obtained in the right hand side of the table (in columns $a$ or $b$). And also (very important!) don't forget to fill the row for the state $\emptyset$ (it will be the row: $\emptyset\:|\:\emptyset\:|\:\emptyset$).