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 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']
-
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]
-
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 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], []]