`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$.

Examples



In [1]:

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









    



:0: FutureWarning: IPython widgets are experimental and may change in the future.



In [2]:

    
a = b.de_bruijn(3)
a









    Out[2]:

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



In [3]:

    
a = b.de_bruijn(2)
a









    Out[3]:



In [4]:

    
a.determinize()









    Out[4]:

context.de_bruijn(n)

Examples

`context`.`de_bruijn`(`n`)