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¶

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

a1 = aut('ab').ldivide(aut('abcd'))
a1

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:

a1.trim()

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:

aut('a').ldivide(aut('ab + ac + bc'))

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:

aut('a+b').ldivide(aut('ab + ac + bd + be'))

Weighted automata¶

ldivide also works on weighted automata:

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

waut('<2>ab').ldivide(waut('<6>abcd'))

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$

def rdivide(a1, a2):
    return (a2.transpose().ldivide(a1.transpose())).transpose()

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