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:
Language
Factorial language, the set of factors of the provided list of words.
INPUT:
alphabet
– iterable of letterswords
– finite iterable of words
- class slabbe.language.FiniteLanguage(alphabet, words)¶
Bases:
Language
Finite language
INPUT:
alphabet
– iterable of letterswords
– 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:
Language
Regular language
INPUT:
alphabet
– iterable of lettersautomaton
– 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:
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]