# Minimal DFA for a given regular expression

How can I construct a minimal DFA from the following definition? $L=\{w \in \{a,b,c\}^*$: if the second-to-last letter from w is an $a$, then the number of $c$'s $\le 1\}$

$\verb![ab]*c?[ab]*a[ab] | [ab]*a[abc] | [abc]*[bc][abc]!$

• Are you familiar with the Myhill-Nerode theorem? Apr 2, 2014 at 21:08
• In this case, it'd probably easier to construct the DFA directly than to start from a regular expression. Then either apply the minimization algorith, or use the theorem Peter quoted to show that it's already minimal.
– fgp
Apr 2, 2014 at 22:26
• Ok, I played with this, the DFA gets a bit bigger than I'd have expected, so constructing it directly is a bit messy. But doable, it's got a fairly simply structure...
– fgp
Apr 2, 2014 at 22:45
• If you want to try to construct it directly, start from what you need to know, upon reaching the end of the string, to decide whether to accept or reject. You'll need to know whether or not the second-to-last letter was an $a$, and if so, whether it was followed by a $c$. You'll also need to know whether the total number of $c$'s was $0$, $1$ or $> 1$.
– fgp
Apr 2, 2014 at 23:40
• So your states are some subset of the set $\mathcal{P}(\{a,b,c\}^2) \times \{0,1,>1\}$, where the first component tells you the last two letters (or a list thereof, you don't need to distinguish all cases, hence the powerset) and the second the number of $c$'s.
– fgp
Apr 2, 2014 at 23:40

[ab]*c?[ab]* | [abc]*[bc][abc]