Languages

Regular languages

EXAMPLES:

Language over all finite words on an alphabet:

sage: from slabbe.language import Language
sage: Language(alphabet=['a', 'b'])
Language of finite words over alphabet ['a', 'b']

Finite language:

sage: from slabbe.language import FiniteLanguage
sage: S = ['a', 'ab', 'aab', 'aaab']
sage: FiniteLanguage(alphabet=['a', 'b'], words=S)
Finite language of cardinality 4 over alphabet ['a', 'b']

Regular language:

sage: from slabbe.language import RegularLanguage
sage: alphabet = ['a', 'b']
sage: trans = [(0, 1, 'a'), (1, 2, 'b'), (2, 3, 'b'), (3, 4, 'a')]
sage: automaton = Automaton(trans, initial_states=[0], final_states=[4])
sage: RegularLanguage(alphabet, automaton)
Regular language over ['a', 'b']
defined by: Automaton with 5 states

Predefined languages:

sage: from slabbe.language import languages
sage: languages.ARP()
Regular language over [1, 2, 3, 123, 132, 213, 231, 312, 321]
defined by: Automaton with 7 states

AUTHORS:

  • Sébastien Labbé, initial clean and full doctested version, October 2015

class slabbe.language.FactorialLanguage(alphabet, L)

Bases: slabbe.language.Language

Factorial language, the set of factors of the provided list of words.

INPUT:

  • alphabet – iterable of letters

  • words – finite iterable of words

class slabbe.language.FiniteLanguage(alphabet, words)

Bases: slabbe.language.Language

Finite language

INPUT:

  • alphabet – iterable of letters

  • words – finite iterable of words

EXAMPLES:

sage: from slabbe.language import FiniteLanguage
sage: L = ['a', 'aa', 'aaa']
sage: FiniteLanguage(alphabet=['a'], words=L)
Finite language of cardinality 3 over alphabet ['a']
automaton()

Return the automaton recognizing this finite language.

EXAMPLES:

sage: from slabbe.language import FiniteLanguage
sage: L = ['a', 'aa', 'aaa']
sage: F = FiniteLanguage(alphabet=['a'], words=L)
sage: F.automaton()
Automaton with 7 states
minimal_automaton()

Return the minimal automaton recognizing this finite language.

Note

One of the state is not final. You may want to remove it…

EXAMPLES:

sage: from slabbe.language import FiniteLanguage
sage: L = ['a', 'aa', 'aaa']
sage: F = FiniteLanguage(alphabet=['a'], words=L)
sage: F.minimal_automaton()
Automaton with 5 states
number_of_states()

EXAMPLES:

sage: from slabbe.language import FiniteLanguage
sage: L = ['a', 'aa', 'aaa']
sage: F = FiniteLanguage(alphabet=['a'], words=L)
sage: F.number_of_states()
5
class slabbe.language.Language(alphabet)

Bases: object

Language of finite words

INPUT:

  • alphabet – iterable of letters

EXAMPLES:

sage: from slabbe.language import Language
sage: Language(alphabet=['a', 'b'])
Language of finite words over alphabet ['a', 'b']
alphabet()

Return the alphabet of the language

EXAMPLES:

sage: from slabbe.language import Language
sage: L = Language(alphabet=['a'])
sage: L.alphabet()
['a']
bispecial_factors(n)

Return the bispecial factors of length n

INPUT:

  • length – integer

OUTPUT:

list of pairs of (factor, list of extensions)

EXAMPLES:

sage: from slabbe.language import FactorialLanguage
sage: alphabet = ['a', 'b', 'c', 'd']
sage: L = FactorialLanguage(alphabet, ['abc', 'acd'])
sage: result = L.bispecial_factors(0)
sage: [(key, sorted(val)) for (key,val) in result]
[(word: , [('a', 'b'), ('a', 'c'), ('b', 'c'), ('c', 'd')])]
sage: L.bispecial_factors(1)
[]
bispecial_table(max_length)

Return the table of the bispecial factors of a word.

INPUT:

  • max_length – integer

OUTPUT:

table

EXAMPLES:

sage: from slabbe.language import FactorialLanguage
sage: alphabet = [0, 1]
sage: w = words.FibonacciWord()
sage: L = FactorialLanguage(alphabet, [w[:10000]])
sage: L.bispecial_table(20)
  |w|   word                  m(w)   info   d^-(w)   d^+(w)
+-----+---------------------+------+------+--------+--------+
  0                           0      ord.   2        2
  1     0                     0      ord.   2        2
  3     010                   0      ord.   2        2
  6     010010                0      ord.   2        2
  11    01001010010           0      ord.   2        2
  19    0100101001001010010   0      ord.   2        2
sage: w = words.ThueMorseWord()
sage: L = FactorialLanguage(alphabet, [w[:10000]])
sage: L.bispecial_table(20)
  |w|   word               m(w)   info     d^-(w)   d^+(w)
+-----+------------------+------+--------+--------+--------+
  0                        1      strong   2        2
  1     0                  0      ord.     2        2
  1     1                  0      ord.     2        2
  2     01                 1      strong   2        2
  2     10                 1      strong   2        2
  3     010                -1     weak     2        2
  3     101                -1     weak     2        2
  4     0110               1      strong   2        2
  4     1001               1      strong   2        2
  6     011001             -1     weak     2        2
  6     100110             -1     weak     2        2
  8     01101001           1      strong   2        2
  8     10010110           1      strong   2        2
  12    011010010110       -1     weak     2        2
  12    100101101001       -1     weak     2        2
  16    0110100110010110   1      strong   2        2
  16    1001011001101001   1      strong   2        2
complexity(length)

Returns the number of words of given length.

Note

This method is defined from words_of_length_iterator().

INPUT:

  • length – integer

EXAMPLES:

sage: from slabbe.language import Language
sage: F = Language(alphabet=['a', 'b'])
sage: [F.complexity(n) for n in range(5)]
[1, 2, 4, 8, 16]
factors_extensions(n)

Return a dict of factors to list of extensions

INPUT:

  • length – integer

OUTPUT:

dict

EXAMPLES:

sage: from slabbe.language import FactorialLanguage
sage: alphabet = ['a', 'b', 'c', 'd']
sage: L = FactorialLanguage(alphabet, ['abc', 'acd'])
sage: d = L.factors_extensions(0)
sage: for key in sorted(d): key, sorted(d[key])
(word: , [('a', 'b'), ('a', 'c'), ('b', 'c'), ('c', 'd')])
sage: d = L.factors_extensions(1)
sage: for key in sorted(d): key, sorted(d[key])
(word: b, [('a', 'c')])
(word: c, [('a', 'd')])
words_of_length_iterator(length)

Return an iterator over words of given length.

INPUT:

  • length – integer

EXAMPLES:

sage: from slabbe.language import Language
sage: F = Language(alphabet=['a', 'b'])
sage: it = F.words_of_length_iterator(2)
sage: list(it)
[word: aa, word: ab, word: ba, word: bb]
class slabbe.language.LanguageGenerator

Bases: object

ARP()

Return the Arnoux-Rauzy-Poincaré regular language.

sage: from slabbe.language import languages sage: L = languages.ARP() sage: L Regular language over [1, 2, 3, 123, 132, 213, 231, 312, 321] defined by: Automaton with 7 states sage: [L.complexity(n) for n in range(4)] [1, 9, 57, 345]

Brun()

Return the Brun regular language.

EXAMPLES:

sage: from slabbe.language import languages
sage: L = languages.Brun()
sage: L
Regular language over [123, 132, 213, 231, 312, 321]
defined by: Automaton with 6 states
sage: [L.complexity(n) for n in range(4)]
[1, 6, 18, 54]
sage: list(L.words_of_length_iterator(2))
[word: 123,123,
 word: 123,132,
 word: 123,312,
 word: 132,123,
 word: 132,132,
 word: 132,213,
 word: 213,213,
 word: 213,231,
 word: 213,321,
 word: 231,123,
 word: 231,213,
 word: 231,231,
 word: 312,231,
 word: 312,312,
 word: 312,321,
 word: 321,132,
 word: 321,312,
 word: 321,321]
Cassaigne()

Return the Cassaigne regular language over the alphabet [11, 22, 122, 211, 121, 212].

EXAMPLES:

sage: from slabbe.language import languages
sage: L = languages.Cassaigne()
sage: L
Regular language over [11, 22, 121, 122, 211, 212]
defined by: Automaton with 1 state
sage: [L.complexity(n) for n in range(4)]
[1, 6, 36, 216]
Selmer()

Return the Selmer regular language.

EXAMPLES:

sage: from slabbe.language import languages
sage: L = languages.Selmer()
sage: L
Regular language over [123, 132, 213, 231, 312, 321]
defined by: Automaton with 6 states
sage: [L.complexity(n) for n in range(4)]
[1, 6, 12, 24]
sage: list(L.words_of_length_iterator(2))
[word: 123,132,
 word: 123,312,
 word: 132,123,
 word: 132,213,
 word: 213,231,
 word: 213,321,
 word: 231,123,
 word: 231,213,
 word: 312,231,
 word: 312,321,
 word: 321,132,
 word: 321,312]
class slabbe.language.RegularLanguage(alphabet, automaton)

Bases: slabbe.language.Language

Regular language

INPUT:

  • alphabet – iterable of letters

  • automaton – finite state automaton

EXAMPLES:

sage: from slabbe.language import RegularLanguage
sage: alphabet = ['a', 'b']
sage: trans = [(0, 1, 'a'), (1, 2, 'b'), (2, 3, 'b'), (3, 4, 'a')]
sage: automaton = Automaton(trans, initial_states=[0], final_states=[4])
sage: RegularLanguage(alphabet, automaton)
Regular language over ['a', 'b']
defined by: Automaton with 5 states
words_of_length_iterator(length)

Return an iterator over words of given length.

INPUT:

  • length – integer

EXAMPLES:

sage: from slabbe.language import RegularLanguage
sage: alphabet = ['a', 'b']
sage: trans = [(0, 1, 'a'), (1, 2, 'b'), (2, 3, 'b'), (3, 4, 'a')]
sage: automaton = Automaton(trans, initial_states=[0], final_states=[4])
sage: R = RegularLanguage(alphabet, automaton)
sage: [list(R.words_of_length_iterator(i)) for i in range(6)]
[[], [], [], [], [word: abba], []]
class slabbe.language.SturmianLanguage(alphabet)

Bases: slabbe.language.Language

Language of all Sturmian sequences

INPUT:

  • alphabet – list of size 2

EXAMPLES:

sage: from slabbe.language import SturmianLanguage
sage: S = SturmianLanguage(['a', 'b'])
sage: sorted(S(0))
[word: ]
sage: sorted(S(1))
[word: a, word: b]
sage: sorted(S(2))
[word: aa, word: ab, word: ba, word: bb]
sage: sorted(S(4))
[word: aaaa, word: aaab, word: aaba,
 word: abaa, word: abab, word: abba, word: abbb,
 word: baaa, word: baab, word: baba, word: babb,
 word: bbab, word: bbba, word: bbbb]
sage: [len(S(n)) for n in range(5)]
[1, 2, 4, 8, 14]

The number of factors of length n is well-known (http://oeis.org/A005598):

sage: [len(S(n)) for n in range(15)] # not tested
[1, 2, 4, 8, 14, 24, 36, 54, 76, 104, 136, 178, 224, 282, 346]
sage: oeis.find_by_subsequence(_)                                  # not tested
0: A005598: a(n) = 1 + Sum_{i=1..n} (n-i+1)*phi(i).
factor(slope, intercept, length)

EXAMPLES:

sage: from slabbe.language import SturmianLanguage
sage: S = SturmianLanguage('ab')
sage: S.factor(1/3, 0, 5)
word: aabaa
sage: S.factor(1/3, 4/5, 5)
word: baaba
unit_square_parameter_partition(length)

Return the partition of the unit square where each polygonal atom represents the set of parameter associated to a factor of length n.

See Chapter 2 from this book:

Filiot, Emmanuel, Anna Frid, Franck Hétroy-Wheeler, Kolja Knauer, Arnaud Labourel, Jean-Luc Mari, Pierre-Alain Reynier, et Gérard Subsol. Informatique Mathématique Une photographie en 2019. https://www.gdr-im.fr/im-photographie/

EXAMPLES:

sage: from slabbe.language import SturmianLanguage
sage: S = SturmianLanguage('ab')
sage: S.unit_square_parameter_partition(5)
Polyhedron partition of 24 atoms with 24 letters

We check that the sizes are ok:

sage: [len(S.unit_square_parameter_partition(i)) for i in range(10)] # long time (2s)
[1, 2, 4, 8, 14, 24, 36, 54, 76, 104]
sage: oeis.find_by_subsequence(_)                   # not tested
0: A005598: a(n) = 1 + Sum_{i=1..n} (n-i+1)*phi(i).

TESTS:

sage: [len(S.unit_square_parameter_partition(i)) for i in range(15)] # not tested
[1, 2, 4, 8, 14, 24, 36, 54, 76, 104, 136, 178, 224, 282, 346]
words_of_length_iterator(length)

Return an iterator over words of given length.

INPUT:

  • length – integer

EXAMPLES:

sage: from slabbe.language import SturmianLanguage
sage: S = SturmianLanguage('ab')
sage: sorted(S.words_of_length_iterator(0))
[word: ]
sage: sorted(S.words_of_length_iterator(1))
[word: a, word: b]
sage: sorted(S.words_of_length_iterator(2))
[word: aa, word: ab, word: ba, word: bb]
sage: sorted(S.words_of_length_iterator(3))
[word: aaa,
 word: aab,
 word: aba,
 word: abb,
 word: baa,
 word: bab,
 word: bba,
 word: bbb]
sage: sorted(S.words_of_length_iterator(4))
[word: aaaa,
 word: aaab,
 word: aaba,
 word: abaa,
 word: abab,
 word: abba,
 word: abbb,
 word: baaa,
 word: baab,
 word: baba,
 word: babb,
 word: bbab,
 word: bbba,
 word: bbbb]
sage: [len(set(S.words_of_length_iterator(i))) for i in range(10)] # long time
[1, 2, 4, 8, 14, 24, 36, 54, 76, 104]