# 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)

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)

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)

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)

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]
```