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


In [1]:
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\}$ with an odd number of $a$ with an automaton accepting with words with an odd number of $b$:


In [2]:
%%automaton odda
$ -> 0
0 -> 0 b
0 -> 1 a
1 -> 1 b
1 -> 0 a
1 -> $


%3 I0 0 0 I0->0 F1 0->0 b 1 1 0->1 a 1->F1 1->0 a 1->1 b

In [3]:
%%automaton oddb
$ -> 0
0 -> 0 a
0 -> 1 b
1 -> 1 a
1 -> 0 b
1 -> $


%3 I0 0 0 I0->0 F1 0->0 a 1 1 0->1 b 1->F1 1->0 b 1->1 a

is an automaton that accepts only words with odd numbers of $a$ and $b$:


In [4]:
odda & oddb


Out[4]:
%3 I0 0 0, 0 I0->0 F3 1 1, 0 0->1 a 2 0, 1 0->2 b 1->0 a 3 1, 1 1->3 b 2->0 b 2->3 a 3->F3 3->1 b 3->2 a

In [5]:
(odda & oddb).shortest(10)


Out[5]:
$\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


In [6]:
import vcsn
c = vcsn.context('lal_char, seriesset<lal_char, z>')
std = lambda exp: c.expression(exp).standard()

In [7]:
x = std("<x>a*+<x>b*"); x


Out[7]:
%3 I0 0 0 I0->0 F0 F1 F3 0->F0 ⟨⟨2⟩x⟩ 1 1 0->1 ⟨x⟩a 3 3 0->3 ⟨x⟩b 1->F1 1->1 a 3->F3 3->3 b

In [8]:
y = std("<y>a*+<y>c*"); y


Out[8]:
%3 I0 0 0 I0->0 F0 F1 F3 0->F0 ⟨⟨2⟩y⟩ 1 1 0->1 ⟨y⟩a 3 3 0->3 ⟨y⟩c 1->F1 1->1 a 3->F3 3->3 c

In [9]:
x & y


Out[9]:
%3 I0 0 0, 0 I0->0 F0 F1 0->F0 ⟨⟨4⟩(xy)⟩ 1 1, 1 0->1 ⟨xy⟩a 1->F1 1->1 a

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.


In [10]:
x = std('<x>a')
y = std('<y>a')
z = std('<z>a')

In [11]:
x & y & z


Out[11]:
%3 I0 0 0, 0, 0 I0->0 F1 1 1, 1, 1 0->1 ⟨xyz⟩a 1->F1

In [12]:
xy = (x & y).__value__(); xy & z


Out[12]:
%3 I0 0 (0, 0), 0 I0->0 F1 1 (1, 1), 1 0->1 ⟨xyz⟩a 1->F1

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