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$
