Contact
CoCalc Logo Icon
StoreFeaturesDocsShareSupport News Sign UpSign In
| Download
Views: 45854
Kernel: Python 3

automaton & aut

The (accessible part of the) "conjunction" of automata.

Also Known As:

  • synchronized product

  • Hadamard product

  • intersection

Preconditions:

  • all the labelsets are letterized

See also:

Examples

Boolean Automata

import vcsn

The synchronized product of Boolean automata computes the intersection of their languages. For instance, the conjunction of an automaton that accepts only words on {a,b}\{a, b\} with an odd number of aa with an automaton accepting with words with an odd number of bb:

%%automaton odda $ -> 0 0 -> 0 b 0 -> 1 a 1 -> 1 b 1 -> 0 a 1 -> $
Image in a Jupyter notebook
%%automaton oddb $ -> 0 0 -> 0 a 0 -> 1 b 1 -> 1 a 1 -> 0 b 1 -> $
Image in a Jupyter notebook

is an automaton that accepts only words with odd numbers of aa and bb:

odda & oddb
Image in a Jupyter notebook
(odda & oddb).shortest(10)

abbaaaabaabaabaaabbbbaaababbbbabbbba\mathit{ab} \oplus \mathit{ba} \oplus \mathit{aaab} \oplus \mathit{aaba} \oplus \mathit{abaa} \oplus \mathit{abbb} \oplus \mathit{baaa} \oplus \mathit{babb} \oplus \mathit{bbab} \oplus \mathit{bbba}

Weighted automata

import vcsn c = vcsn.context('lal_char, seriesset<lal_char, z>') std = lambda exp: c.expression(exp).standard()
x = std("<x>a*+<x>b*"); x
Image in a Jupyter notebook
y = std("<y>a*+<y>c*"); y
Image in a Jupyter notebook
x & y
Image in a Jupyter notebook

Associativity

This operator is associative, and it is actually implemented as a variadic operator; a & b & c is not exactly the same as (a&b)&c: they are the same automata, but the former is labeled with 3-uples, not 2-uples.

x = std('<x>a') y = std('<y>a') z = std('<z>a')
x & y & z
Image in a Jupyter notebook
xy = (x & y).__value__(); xy & z
Image in a Jupyter notebook

The __value__ call here is an internal detail used to force Vcsn into the binary call. You should forget about it