context.de_bruijn(n)

Create the "de Bruijn" automaton with $n+1$ states; it accepts word whose $n$-th letter before the end is an 'a'. This family of automata is close to be being a worst case for determinization: its determinized automaton has $2^n$ states (not $2^{n+1}$).

Preconditions:

  • the labelset has at least two generators

Postconditions:

  • the Result is isomorphic to the derived-term automaton of $(a+b)^*a(a+b)^n$.

See also:

Examples

In [1]:
import vcsn
b = vcsn.context('lal_char(ab), b')
In [2]:
a = b.de_bruijn(3)
a
Out[2]:
%3 I0 0 0 I0->0 F4 0->0 a, b 1 1 0->1 a 2 2 1->2 a, b 3 3 2->3 a, b 4 4 3->4 a, b 4->F4

The support of the determinized automaton is a de Bruijn graph:

In [3]:
a = b.de_bruijn(2)
a
Out[3]:
%3 I0 0 0 I0->0 F3 0->0 a, b 1 1 0->1 a 2 2 1->2 a, b 3 3 2->3 a, b 3->F3
In [4]:
a.determinize()
Out[4]:
%3 I0 0 0 I0->0 F4 F5 F6 F7 0->0 b 1 0, 1 0->1 a 2 0, 1, 2 1->2 a 3 0, 2 1->3 b 4 0, 1, 2, 3 2->4 a 5 0, 2, 3 2->5 b 6 0, 1, 3 3->6 a 7 0, 3 3->7 b 4->F4 4->4 a 4->5 b 5->F5 5->6 a 5->7 b 6->F6 6->2 a 6->3 b 7->F7 7->0 b 7->1 a