context.de_bruijn.ipynb

Kernel: Python 3

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:

• automaton.determinize

Examples

import vcsn
b = vcsn.context('lal_char(ab), b')

a = b.de_bruijn(3)
a

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

a = b.de_bruijn(2)
a

a.determinize()