$\newcommand \ldiv{\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 \ldiv K^t)^t$$where $\ldiv$ is the left quotient
Preconditions:
import vcsn
ctx = vcsn.context('lal_char, b')
aut = lambda e : ctx.expression(e).automaton()
a1 = aut('abcd')
a2 = aut('cd')
a1.rdiv(a2)
This demonstrates how rdiv
is defined: as combination of ldiv
and transpose
.
(a2.transpose().ldiv(a1.transpose())).transpose()
More examples can be found for the left division (automaton.ldiv).