4
$\begingroup$

I am looking for an example, which corresponds to what I've learned in my Applied Automata Theory Class:

Given a NFA $\mathcal{A}$,

  • a $\approx _\mathcal{A}$ quotient automaton can be bigger then a $\sim_\mathcal{A}$ quotient automaton and this can be bigger than an optimal quotient
  • and an optimal quotient does not need to be the smallest equivalent NFA.

$\approx _\mathcal{A}$ denotes the bisimulation relation (block refinement algorithm) and $\sim_\mathcal{A}$ denotes the canonical congruence, where $p \sim_\mathcal{A} q \text{ iff } \delta^*(p,w) \in F \text{ iff } \delta^*(q,w) \in F$, where DFA $\mathcal{A}= (Q, \Sigma, q_0, \delta, F)$.

Follow-up:

The original Automaton $\mathcal{A}$ over $\Sigma={\{a,b\}}$ recognizing $\mathcal{L} = \Sigma a^*$:

The original automaton $\mathcal{A} = (\{1,2,3,4,5,6\}, \Sigma, 1, \Delta, \{{3,4}\}) $ with $\Delta$: \begin{pmatrix} & 1 & 2 & 3 & 4 & 5 & 6\\ 1 &- & b & a & -& -&- & \\ 2 &b & b & - & a & -&- & \\ 3 &- & b & - & a& a&- & \\ 4 &- & b & - & a& a&- & \\ 5 &- & - & - & -& -&b & \\ 6 &- & - & & a& b&b & \\ \end{pmatrix}

The quotient automaton $\mathcal{A}_{\approx} = (\{12,34,5,6\}, \Sigma, 12, \Delta_{\approx}, \{{34}\}) $ with $\Delta_{\approx}$: \begin{pmatrix} & 12 & 34 & 5 & 6\\ 12 &b & a & - & - \\ 34 &b & a & a & - \\ 5 &- & - & - & b \\ 6 &- & a & b & b \\ \end{pmatrix}

The quotient automaton $\mathcal{A}_{\sim} = (\{126,34,5\}, \Sigma, 126, \Delta_{\sim}, \{{34}\}) $ with $\Delta_{\sim}$: \begin{pmatrix} & 126 & 34 & 5 \\ 126 &b & a & b \\ 34 &b & a & a \\ 5 &b & - & - \\ \end{pmatrix}

The optimal quotient automaton $\mathcal{A_{OPT}} = (\{1256,34\}, \Sigma, 1256, \Delta_{OPT}, \{{34}\}) $ with $\Delta_{OPT}$: \begin{pmatrix} & 1256 & 34 \\ 1256 &a,b & a \\ 34 &a,b & a \\ \end{pmatrix}

The first property is satisfied since $\mathcal{A}_{\approx}$ has 4 states and $\mathcal{A}_{\sim}$ has 3 states. But in my example $\mathcal{A}_{OPT}$ is the smallest automaton recognizing the given language. When do they differ?

$\endgroup$
  • 1
    $\begingroup$ What have you tried so far? It's instructive to compute these relations for a few simple languages. This way, either you'll find an example, or you can conclude that it's often the case that these relations are the same. $\endgroup$ – Yuval Filmus Jul 31 '13 at 18:46
  • $\begingroup$ I found an example constructing an NFA for the Language $L = \Sigma a^*$. $\endgroup$ – Laura Jul 31 '13 at 22:22
  • $\begingroup$ Can you post an answer with the details? $\endgroup$ – Yuval Filmus Aug 1 '13 at 3:49
  • $\begingroup$ Please see above $\endgroup$ – Laura Aug 1 '13 at 18:48

Your Answer

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

Browse other questions tagged or ask your own question.