1
$\begingroup$

This is the question 1.12 from Introduction to the Theory of Computation 3rd Edition by Michael Sipser. The questions says,

Let $D=\{w\mid w$ contains an even number of $\texttt{a}$'s and an odd number of $\texttt{b}$'s and does not contain the substring $\texttt{ab}$}. Give a DFA with five states that recognizes $D$ and a regular expression that generates $D$.

I was able to construct a minimal DFA by using the intersection operation on the three simpler parts of $D$. I think that the regular expression that would generate $D$ is b(bb)*(aa)* but I'm not sure about it.

Is my regular expression correct? If yes, then if I apply the subset construction algorithm on this diagram (eps denotes ε) and minimize the resultant DFA, I should get the minimal DFA that I constructed through intersection, right?

$\endgroup$
  • $\begingroup$ @RickDecker Ok. Is my ε-NFA correct? I'd like to think that it is but different books use different notations for representing Kleene Star and I just used the one that is used by Hopcroft & Ullman in their book. $\endgroup$ – Ayush Agarwal Aug 13 '16 at 18:34
  • 1
    $\begingroup$ Your DFA and regular expression are correct. For the rest, you should show that your DFA is minimal (it is). It appears that your NFA is correct, so if you convert that to a DFA and minimize it you should get your original DFA (though it would be tedious to do by hand). Don't worry about the fact that there different ways to do the NFA to DFA construction: either will work. $\endgroup$ – Rick Decker Aug 13 '16 at 18:35
  • 2
    $\begingroup$ @sixpointzero Seems to me that your real question here is "Is the minimal DFA always the same, no matter how I get it?". (We don't do homework checking.) $\endgroup$ – Raphael Aug 13 '16 at 19:19
  • $\begingroup$ @Raphael I wasn't sure whether my regex was correct or not and that was the primary question. Another issue that I'm facing is that I can't seem to get the same regex from my minimal DFA using Arden's Lemma as described in your answer (the answer that I get is just too long). I'm also unable to get the minimal DFA using the regex using subset construction. Oh well, I'll try again. By the way, this isn't homework. $\endgroup$ – Ayush Agarwal Aug 13 '16 at 21:50
  • $\begingroup$ 1) Yes, FA->RegEx methods are notorious for creating ugly and wildly different expressions that all are equivalent. Also, minimizing regular expressions is hard so checking them for equivalence it not always feasible. 2) If you get different automata after minimization you made a mistake. Check your steps! $\endgroup$ – Raphael Aug 14 '16 at 11:49
1
$\begingroup$

I was able to solve this question using two possible routes.

The 1st route involves constructing the DFA by using the intersection operation on the simpler parts of $D$, i.e.,

$\{$even number of $a$'s$\} \cap\{$odd number of $b$'s$\}\cap\{$does not contain the substring $ab\}$

After that, I was able to reduce the DFA into a RegEx using the State Elimination Method and Arden's Lemma. The regular expression can be achieved by using Arden's Lemma as follows.

$$1\to a2+b4$$

$$2\to a2+b2$$

$$3\to a5+b2+\varepsilon$$

$$4\to a5+b1+\varepsilon$$

$$5\to a3+b2$$

Note that $2\to a2+b2$ will resolve as $2\to \varnothing$ and not $2\to (a+b)^*$.

The 2nd route involves "knowing" that the regular expression is $b(bb)^*(aa)^*$ by analyzing the language $D$. This RegEx can be converted to an ε-NFA. After that, we can convert this ε-NFA to get a DFA which when minimized would give us this.

$\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.