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.
$\endgroup$ 22 Answers
$\begingroup$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$).
$\endgroup$
