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.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']
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: map(F.complexity, range(5))
[1, 2, 4, 8, 16]
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: map(L.complexity, 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: map(L.complexity, 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, 122, 211, 121, 212]
defined by: Automaton with 1 state
sage: map(L.complexity, 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: map(L.complexity, 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], []]