2
$\begingroup$

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

$\endgroup$
6
  • 2
    $\begingroup$ Are you familiar with the Myhill-Nerode theorem? $\endgroup$ Apr 2, 2014 at 21:08
  • $\begingroup$ 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. $\endgroup$
    – fgp
    Apr 2, 2014 at 22:26
  • $\begingroup$ 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... $\endgroup$
    – fgp
    Apr 2, 2014 at 22:45
  • $\begingroup$ 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$. $\endgroup$
    – fgp
    Apr 2, 2014 at 23:40
  • 1
    $\begingroup$ 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. $\endgroup$
    – fgp
    Apr 2, 2014 at 23:40

1 Answer 1

0
$\begingroup$

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: Minimal DFA for math.se.737211 Here the triangle is the initial state; accept states are marked in green.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .