Tools

Vcsn comes with a set of programs that you use to manipulate automata, expressions, etc.

It is much less powerful than writing Python programs, however it comes handy occasionally to process a batch of files, or for a quick experiment.

Synopsis

vcsn COMMAND [OPTION...] ARG...

Run vcsn tools --help for details on the interface:

In [1]:
!vcsn tools --help
usage: vcsn COMMAND [OPTIONS...] [ARGS...]

General Options:
  -h, --help      display this help message and exit successfully
  -c, --commands  display the supported commands and exit successfully

Available COMMANDs:
  accessible add ambiguous-word are-equal are-equivalent
  are-isomorphic cat cerny coaccessible codeterminize cominimize
  compare complement complete component compose concatenate condense
  configuration conjugate conjunction constant-term context-of copy
  costandard cotrie de-bruijn delay-automaton derivation derived-term
  determinize difference divkbaseb eliminate-state evaluate expand
  expression-one expression-zero factor focus has-bounded-lag
  has-lightening-cycle has-twins-property identities-of inductive
  infiltrate insplit is-accessible is-ambiguous is-coaccessible
  is-codeterministic is-complete is-costandard is-cycle-ambiguous
  is-deterministic is-empty is-eps-acyclic is-functional is-letterized
  is-normalized is-out-sorted is-partial-identity is-proper
  is-realtime is-standard is-synchronized is-synchronized-by
  is-synchronizing is-trim is-useless is-valid join ladybird ldivide
  less-than letterize levenshtein lgcd lift lightest
  lightest-automaton lweight minimize multiply name normalize
  num-components num-tapes pair partial-identity prefix project proper
  push-weights quotkbaseb random-automaton
  random-automaton-deterministic random-expression random-weight
  rdivide realtime reduce rweight scc shortest shuffle sort split
  standard star star-height star-normal-form strip subword suffix
  synchronize synchronizing-word thompson to-automaton to-expansion
  to-expression transpose transposition trie trim tuple type u
  universal weight-one weight-series weight-zero zpc

Input/Output:
  -C CONTEXT    the context to use
                'lal, b', 'law, q', 'lan(abc), zmin', etc.
  -A            input is an automaton
  -B            input is a boolean
  -D            input is an identity

  -F            input is a float
  -L            input is a label (or a word)
  -N            input is a number
  -P            input is a polynomial
  -S            input is a string
  -W            input is a weight
  -e STRING     input is STRING
  -f FILE       input is FILE
  -I FORMAT     input format (daut, dot, efsm, fado, text)
  -O FORMAT     output format
                (daut, dot, efsm, grail, info, list, null, text, tikz, utf8)
  -o FILE       save output into FILE
  -q            discard any output

Input/Output Formats (for Automata, Expressions, Labels, Polynomials, Weights):
  daut   A      Simplified Dot syntax for Automata
  dot    A      GraphViz's Dot language
  efsm   A      Extended FSM format for OpenFST: use efstcompile
  fado   A      FAdo's format
  grail  A      Grail's format
  info   AE     facts about the result (size, etc.)
  latex   ELPW  display as a LaTeX formula
  list      P   display one monomial per line
  null   AELPW  no output at all (e.g., for benchmarks)
  text    ELPW  usual concrete syntax in ASCII
  tikz   A      LaTeX source for TikZ
  utf8    ELPW  usual concrete syntax in UTF-8

Examples:
  $ vcsn thompson -Ee '[ab]*a[ab]{3}' |
      vcsn proper |
      vcsn determinize |
      vcsn evaluate -L 'abba'

  $ vcsn thompson -Ee '[ab]*a[ab]{3}' |
      vcsn proper -f - |
      vcsn determinize -f - |
      vcsn evaluate -f - -L 'abba'

  $ vcsn derived-term -C 'lat<lan, lan>, q' -Ee 'a*|b*' |
      vcsn shortest 10

You can also run vcsn tools COMMAND -h to get information about a particular command.

In [2]:
!vcsn tools evaluate -h
usage: vcsn evaluate [OPTIONS...] [ARGS...]

Available versions:
  AUT:automaton L:word -> weight
    Evaluate L on AUT.

  AUT:automaton P:polynomial -> weight
    Evaluate P on AUT.

Try 'vcsn tools --help' for more information.

Or simply vcsn COMMAND -h.

In [3]:
!vcsn multiply -h
usage: vcsn multiply [OPTIONS...] [ARGS...]

Available versions:
  AUT:automaton MIN:number [MAX=-2:number] [ALGO="auto":string] -> automaton
    Repeated multiplication (concatenation) of an automaton with itself.
    Parameters:
      AUT  the automaton.
      MIN  the minimum number.  If -1, denotes 0.
      MAX  the maximum number.
           If -1, denotes infinity, using star.
           If -2, denotes the same value as min.
      ALGO  how to compute the result
        - "standard"    AUT is standard,
                        build a standard automaton.
        - "general"     no requirement on AUT,
                        but add spontaneous transitions.
        - "auto"        "standard" if AUT is standard,
                        "general" otherwise.

  E:expression MIN:number [MAX=-2:number] -> expression
    Repeated multiplication (concatenation) of an expression with itself.
    Parameters:
      E    the expression.
      MIN  the minimum number.  If -1, denotes 0.
      MAX  the maximum number.
           If -1, denotes infinity, using star.
           If -2, denotes the same value as min.

  E:weight MIN:number [MAX=-2:number] -> weight
    Repeated multiplication of a weight with itself.
    Parameters:
      E    the weight.
      MIN  the minimum number.  If -1, denotes 0.
      MAX  the maximum number.
           If -1, denotes infinity, using star.
           If -2, denotes the same value as min.

  L:label NUM:number -> label
    Repeated multiplication of a label with itself.
    Parameters:
      L    the label.
      NUM  the exponent.

  LHS:automaton RHS:automaton [ALGO="auto":string] -> automaton
    Multiply (concatenate) two automata.
    Parameters:
      LHS   an automaton.
      RHS   another one.
      ALGO  how to compute the result
        - "standard"    both LHS and RHS are standard,
                        build a standard automaton.
        - "general"     no requirement on LHS and and RHS,
                        but add spontaneous transitions.
        - "auto"        "standard" if both automata are standard,
                        "general" otherwise.

  LHS:expression RHS:expression -> expression
    Multiply (concatenate) two expressions.

  LHS:label RHS:label -> label
    Multiply (concatenate) two labels.

  LHS:polynomial RHS:polynomial -> polynomial
    Multiply two polynomials.

  LHS:weight RHS:weight -> weight
    Multiply two weights.

Try 'vcsn tools --help' for more information.

Examples

To generate the standard automaton of $(a+b)^*c$ and save it in abc.gv:

In [4]:
!vcsn standard -Ee '[ab]*c' -o abc.gv
In [5]:
import vcsn
vcsn.automaton(filename='abc.gv')
Out[5]:
%3 I0 0 0 I0->0 F3 1 1 0->1 a 2 2 0->2 b 3 3 0->3 c 1->1 a 1->2 b 1->3 c 2->1 a 2->2 b 2->3 c 3->F3

To generate a Thompson automaton, make it proper, determinize it and extract a rational expression from it:

In [6]:
!vcsn thompson -Ee '[ab]*c' | vcsn proper | vcsn determinize | vcsn to-expression
c+aa*c+(b+aa*b)(b+aa*b)*(c+aa*c)

Likewise, but with an additional minimization step:

In [7]:
!vcsn thompson -Ee '[ab]*c' | vcsn proper | vcsn determinize | vcsn minimize | vcsn to-expression
(a+b)*c

The Python equivalent of these runs are:

In [8]:
vcsn.B.expression('[ab]*c').thompson().proper().determinize().expression()
Out[8]:
$c + a \, {a}^{*} \, c + \left(b + a \, {a}^{*} \, b\right) \, \left(b + a \, {a}^{*} \, b\right)^{*} \, \left(c + a \, {a}^{*} \, c\right)$
In [9]:
vcsn.B.expression('[ab]*c').thompson().proper().determinize().minimize().expression()
Out[9]:
$\left(a + b\right)^{*} \, c$