Minimal DFA for a given regular expression

Question

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

I've already made a regular expression:

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

Thanks in advance

Answer 1

The definition translates directly into the regular expression

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

(That is, there's either at most one c, or the penultimate symbol is not an a.) This can be turned directly into a DFA using regular expression derivatives. I came up with a DFA with 12 states, from which the minimal seven-state DFA can easily be computed: Here the triangle is the initial state; accept states are marked in green.