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

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

In [3]:
(a2.transpose().ldivide(a1.transpose())).transpose()

Out[3]:

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