automaton.rdivide(aut)

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

In other words, it is the automata equivalent of languages right quotient, denoted by the operator / and defined by:

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

where $K / v$ is the right quotient of K by the word v, defined like this:

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

The algorithm uses the fact that

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

where $\ldivide$ is the left quotient

Preconditions:

  • None

Examples

In [1]:
import vcsn
ctx = vcsn.context('lal_char, b')
aut = lambda e : ctx.expression(e).automaton()
In [2]:
a1 = aut('abcd')
a2 = aut('cd')
a1.rdivide(a2)
Out[2]:
%3 I0 0 0 I0->0 F2 1 1 0->1 a 2 2 1->2 b 2->F2 3 3 2->3 c 4 4 3->4 d

This demonstrates how rdivide is defined: as combination of ldivide and transpose.

In [3]:
(a2.transpose().ldivide(a1.transpose())).transpose()
Out[3]:
%3 I0 0 0 I0->0 F2 1 1 0->1 a 2 2 1->2 b 2->F2 3 3 2->3 c 4 4 3->4 d

More examples can be found for the left division (automaton.ldivide).