automaton.ldivide.ipynb

Kernel: Python 3

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\}$$

See also:

• automaton.rdivide

• expansion.ldivide

• expression.ldivide

• expression.rdivide

• label.ldivide

• label.rdivide

• polynomial.ldivide

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

Left quotient also works on weighted automata:

q = vcsn.context('lan_char, q')
qaut = lambda e: q.expression(e).automaton()
qaut('<2>ab').ldivide(qaut('<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'))