expression.constant_term()

Compute the "constant term" of an expression, i.e., the weight associated with the empty word.

Preconditions:

  • The expression is valid

Algorithm:

  • Based on a simple bottom-up traversal of the tree of the expression: $$ \newcommand{\eword}{\varepsilon} \newcommand{\lweight}[2]{\bra{#1}{#2}} \newcommand{\rweight}[2]{#1\bra{#2}} \newcommand{\lmulq}[2]{\bra{#1}^?{#2}} \newcommand{\rmulq}[2]{#1\bra{#2}^?} \newcommand{\bra}[1]{\langle#1\rangle} \newcommand{\K}{\mathbb{K}} \newcommand{\zed}{\mathsf{0}} \newcommand{\und}{\mathsf{1}} \newcommand{\zeK}{0_{\K}} \newcommand{\unK}{1_{\K}} \newcommand{\Ed}{\mathsf{E}} \newcommand{\Fd}{\mathsf{F}} \newcommand{\Gd}{\mathsf{G}} \newcommand{\AND}{\mathbin{\&}} \newcommand{\infiltrate}{\mathbin{\uparrow}} \newcommand{\shuffle}{\mathbin{\between}} \newcommand{\coloneqq}{:=} \begin{align} c(\zed) & \coloneqq \bra{\zeK} \\ c(\und) & \coloneqq \bra{\unK} \\ c(a) & \coloneqq \bra{\zeK}, \forall a \in A \\ c(\Ed+\Fd) & \coloneqq c(\Ed) + c(\Fd) \\ c(\lweight{k}{\Ed}) & \coloneqq \lweight{k}{c(\Ed)} \\ c(\rweight{\Ed}{k}) & \coloneqq \rweight{c(\Ed)}{k} \\ c(\Ed \cdot \Fd) & \coloneqq c(\Ed) \cdot c(\Fd) \\ c(\Ed^*) & \coloneqq c(\Ed)^* \\ c(\Ed \AND \Fd) & \coloneqq c(\Ed) \cdot c(\Fd) \\ c(\Ed \shuffle \Fd) & \coloneqq c(\Ed) \cdot c(\Fd) \\ c(\Ed \infiltrate \Fd) & \coloneqq c(\Ed) \cdot c(\Fd) \\ c(\Ed^c) & \coloneqq c(\Ed)^c \end{align} $$

See also:

Examples

The following function allows to display nicely expressions and their constant term.

In [1]:
import vcsn
from IPython.display import Latex

def c(*es):
    eqs = []
    for e in es:
        e = vcsn.Q.expression(e)
        eqs.append(r'{e:x} &\Rightarrow {c:x}'
                   .format(e=e, c=e.constant_term()))
    return Latex(r'''\begin{{aligned}}
        {eqs}
\end{{aligned}}'''.format(eqs=r'\\'.join(eqs)))
In [2]:
c('a', r'\e', r'<2>\e', 'a*', '(<1/6>a)*', '<1/6>a*', '<1/6>a*+<1/3>b*', '(<1/6>a*+<1/3>b*)*')
Out[2]:
\begin{aligned} a &\Rightarrow 0\\\varepsilon &\Rightarrow 1\\ \left\langle 2 \right\rangle \,\varepsilon &\Rightarrow 2\\{a}^{*} &\Rightarrow 1\\\left( \left\langle \frac{1}{6} \right\rangle \,a\right)^{*} &\Rightarrow 1\\ \left\langle \frac{1}{6} \right\rangle \,{a}^{*} &\Rightarrow \frac{1}{6}\\ \left\langle \frac{1}{6} \right\rangle \,{a}^{*} + \left\langle \frac{1}{3} \right\rangle \,{b}^{*} &\Rightarrow \frac{1}{2}\\\left( \left\langle \frac{1}{6} \right\rangle \,{a}^{*} + \left\langle \frac{1}{3} \right\rangle \,{b}^{*}\right)^{*} &\Rightarrow 2 \end{aligned}