automaton.rdivide.ipynb

Kernel: Python 3

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

See also:

• automaton.ldivide

• expansion.ldivide

• expression.ldivide

• expression.rdivide

• label.ldivide

• label.rdivide

• polynomial.ldivide

Examples

import vcsn
ctx = vcsn.context('lal_char, b')
aut = lambda e : ctx.expression(e).automaton()

a1 = aut('abcd')
a2 = aut('cd')
a1.rdivide(a2)

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

(a2.transpose().ldivide(a1.transpose())).transpose()

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