A minimal automaton for a language quotient $w^{-1}L$ if $L$ is regular

Question

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.

Answer 1

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$.