2
$\begingroup$

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

enter image description here

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

enter image description here

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$
2
  • $\begingroup$ Did you mean (aa)*(bb)*a? $\endgroup$
    – Kenny Lau
    May 7 '16 at 10:03
  • $\begingroup$ @KennyLau: Yes I mean (aa)*a(bb)*. $\endgroup$
    – user963241
    May 7 '16 at 10:07
3
$\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 :

enter image description here

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 :

enter image description here

$\endgroup$
1
$\begingroup$

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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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