0
$\begingroup$

For a given language $L$ and $w \in X^{\ast}$ denote by $w^{-1} L := \{ u \in X^{\ast} : wu \in L \}$ the (left) quotients of $L$. The left quotients are closely related to the minimal automaton of $L$ in case $L$ is regular, i.e. in that case $(X, Q, \delta, q_0, F)$ with $Q := \{ w^{-1} L : w \in X^{\ast} \}$, $\delta(w^{-1}L, x) := x^{-1}(w^{-1}L)$,$F := \{ w^{-1}L \in Q : \varepsilon \in w^{-1}L \}$ is isomorphic to the minimal complete automaton accepting $L$.

I am interested in the minimal automaton of a given quotient $w^{-1}L$ in case $L$ is regular, is there a way to construct it? Also as the quotients and the states in a minimal automaton correspond to each other, I am somehow interested in the set $\{ u^{-1}(w^{-1}L) : u \in X^{\ast} \}$ for given quotient $w^{-1}L$.

Note also that the quotients are closely connected to the Nerode (right) congruence, i.e. $u \sim_L v \Leftrightarrow \forall x \in X^{\ast} : ux \in L \leftrightarrow vx \in L \Leftrightarrow u^{-1}L = v^{-1}L$, giving a bijection between them; and also yielding that the minimal automaton of $L$ is an accepting automaton for the nerode classes.

$\endgroup$
  • 2
    $\begingroup$ $w^{-1}L$ is regular so of course you can construct the minimal automaton. What is your question exactly? Are you interested in the complexity? Then how is your input given? Observe that from the minimal automaton A of L you can construct a minimal one for $w^{-1}L$ pretty easily: every quotient of $w^{-1}L$ is a quotient of $L$ too so you just have to change the initial state to be $w^{-1}L$, change the final states to be $\{(wu)^{-1}L : \epsilon \in (wu)^{-1}L\}$ and remove states from A that can't be reached from the new initial states or from which we cannot reach a final state. $\endgroup$ – holf Dec 7 '16 at 12:48
  • $\begingroup$ Yes, that was my question, thank you. Would you like to make it in an answer? $\endgroup$ – StefanH Dec 7 '16 at 13:02
  • 1
    $\begingroup$ I don't think this is a research level question, so I suggest to close this question. $\endgroup$ – J.-E. Pin Dec 8 '16 at 19:25
  • $\begingroup$ I see, it isn't research level, but rather then closing maybe migrating it to cs.stackexchange or math.stackexchange would be better... $\endgroup$ – StefanH Dec 9 '16 at 13:43
5
$\begingroup$

Now that the question is clarified, I transform my comment into an answer and improve the construction. Our goal is to construct a minimal automaton for $w^{-1}L$ given a minimum automaton $A$ for $L$ and $w$.

It is known that $A$ is isomorphic to the automaton where the state correspond to quotients of $L$. This is the minimal automaton that you describe in your question.

Observe that the quotients of $w^{-1}L$ are also quotients of $L$ since $u^{-1}(w^{-1}L) = (wu)^{-1}L$. Thus, intuitively, you have in $A$ all the states that you need for constructing a minimal automaton for $w^{-1}L$.

First, we claim that the automaton $A$ where we change the initial state to be $w^{-1}L$ recognize $w^{-1}L$. Indeed, by reading $v$ from $w^{-1}L$, you end up in the state $v^{-1}w^{-1}L$. We have then $v \in w^{-1}L$ if and only if $\epsilon \in v^{-1}w^{-1}L$ iff $v^{-1}w^{-1}L$ is final.

Now we have two things to do: first, find the state in $A$ that corresponds to $w^{-1}L$: it is easy, it is the state reached by reading $w$ from $q_0$. Second, we have to minimize this automaton. We claim that if we only keep states that are reachable from state $w^{-1}L$ then we will have a minimal automaton for $w^{-1}L$. Indeed, this automaton still recognize $w^{-1}L$ as we only removed dead state. Moreover each remaining state represents a non-empty quotient of $w^{-1}L$ and two states represent two different quotients. Thus, it has the required minimal size.

To summarize the algorithm:

  • read $w$ in $A$ and reach state $q$
  • remove states that can't be reached from $q$
  • set $q_0 := q$.
$\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.