# automaton.ldivide(aut)¶

$\newcommand\ldivide{\setminus}$ Compute the left quotient of two automata, i.e. the automaton recognizing the language of words $v$ such that there exists a word $u$ recognized by lhs with $uv$ recognized by rhs.

In other words, it is the automata equivalent of languages left quotient, denoted by the operator $\ldivide$ or by a $-1$ exposant on the left-hand side, and defined by:

$$K \ldivide L = K^{-1}L = \bigcup\limits_{u \in K} u^{-1}L$$

where $u^{-1}L$ is the (left) quotient of L by the word u, defined like this:

$$u^{-1}L = \bigcup\limits_{v \in L}u^{-1}v = \{w \mid uw \in L\}$$

## Algorithm¶

### Boolean case¶

For two automata $\mathcal{A}_1, \mathcal{A}_2$ with respective state set $Q_1, Q_2$, the algorithm works as follows:

• Remove all initial transitions of $\mathcal{A}_2$
• For every state pair $(q_1, q_2) \in Q_1 \times Q_2$, set $q_2$ as initial if the following conditions are respected:

• $(q_1, q_2)$ is accessible in $\mathcal{A}_1 \times \mathcal{A}_2$

• $q_1$ is final

Let $i_n$ and $f_n$ denote an initial and a final state of $\mathcal{A}_n$. The first condition ensures that, for any path $i_2 \xrightarrow{u} q2 \xrightarrow{v} f_2$, there is a path $(i_1, i_2) \xrightarrow{u} (q_1, q2)$ in $\mathcal{A}_1 \times \mathcal{A}_2$, and therefore a path $i_1 \xrightarrow{u} q_1$ in $\mathcal{A}_1$. The second condition ensures that $u$ is recognized by $\mathcal{A}_1$.

• Since $q_2$ is set as initial, $\mathcal{A}_2$ now recognizes $v$. So for any path accepting $uv$ in $\mathcal{A}_2$, the constructed automaton recognizes $v$ if and only if $u$ is recognized by $\mathcal{A}_1$.

Preconditions:

• None

Postconditions:

• None

### Weighted case¶

In the weighted case, the algorithm is similar to the conjunction between $\mathcal{A}_1$ and $\mathcal{A}_2$ except for three things:

• $\mathcal{A}_1$ continues matching even when it reaches an accepting state
• if $\mathcal{A}_1$ has not reached an accepting state yet, transitions are labelled one
• weights are divided rather than multiplied

Preconditions:

• the labelset is free

Postconditions:

• None

# Examples¶

In [1]:
import vcsn
ctx = vcsn.context('lan_char, b')
aut = lambda e: ctx.expression(e).automaton()


## Quotient of two words¶

The quotient can be seen as a prefix-remover operator, such that the identity $u\backslash (uv) = v$ is respected for any word $u$ and $v$.

In [2]:
a1 = aut('ab').ldivide(aut('abcd'))
a1

Out[2]:

On this example, $u = ab$ and $v = cd$. The suppression of the original initial transitions (on state 0 in this example) will often lead to non-accessible states, which we may want to remove with the automaton.trim method:

In [3]:
a1.trim()

Out[3]:

## Quotient of a language by a word¶

The quotient of a language by a word is the union of word quotients for all words of the language:

In [4]:
aut('a').ldivide(aut('ab + ac + bc'))

Out[4]:

Since "a" is not a prefix of "bc", it is not taken into account in the resulting automaton.

## Quotient of two languages¶

The quotient of two languages is the union of the quotient of the right-hand side by words of the left-hand side:

In [5]:
aut('a+b').ldivide(aut('ab + ac + bd + be'))

Out[5]:

## Weighted automata¶

ldivide also works on weighted automata:

In [6]:
wctx = vcsn.context('lan_char, q')
waut = lambda e: wctx.expression(e).automaton()

In [7]:
waut('<2>ab').ldivide(waut('<6>abcd'))

Out[7]:

## Right quotient¶

The right quotient of a language by a word is defined similarly as the left quotient:

$L / v = \bigcup\limits_{u \in L}u / v = \{w \mid wv \in L\}$

Which naturaly leads to the right quotient of two languages:

$K / L = \bigcup\limits_{v \in L} K / v$

The right quotient can be expressed using the left quotient and the transpose operator:

$K / L = (L^t \ldivide K^t)^t$

In [8]:
def rdivide(a1, a2):
return (a2.transpose().ldivide(a1.transpose())).transpose()

rdivide(aut('abc'), aut('c'))

Out[8]: