Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
r""" Free Monoids
AUTHORS:
- David Kohel (2005-09) - Simon King (2011-04): Put free monoids into the category framework
Sage supports free monoids on any prescribed finite number `n\geq 0` of generators. Use the ``FreeMonoid`` function to create a free monoid, and the ``gen`` and ``gens`` functions to obtain the corresponding generators. You can print the generators as arbitrary strings using the optional ``names`` argument to the ``FreeMonoid`` function. """ #***************************************************************************** # Copyright (C) 2005 David Kohel <kohel@maths.usyd.edu> # # This program is free software: you can redistribute it and/or modify # it under the terms of the GNU General Public License as published by # the Free Software Foundation, either version 2 of the License, or # (at your option) any later version. # http://www.gnu.org/licenses/ #***************************************************************************** from __future__ import absolute_import from six import integer_types
from sage.rings.integer import Integer from sage.structure.category_object import normalize_names from .free_monoid_element import FreeMonoidElement
from .monoid import Monoid_class
from sage.combinat.words.finite_word import FiniteWord_class
from sage.structure.factory import UniqueFactory from sage.misc.cachefunc import cached_method from sage.misc.decorators import rename_keyword from sage.rings.all import ZZ
class FreeMonoidFactory(UniqueFactory): """ Create the free monoid in `n` generators.
INPUT:
- ``n`` - integer
- ``names`` - names of generators
OUTPUT: free monoid
EXAMPLES::
sage: FreeMonoid(0,'') Free monoid on 0 generators () sage: F.<a,b,c,d,e> = FreeMonoid(5); F Free monoid on 5 generators (a, b, c, d, e) sage: F(1) 1 sage: mul([ a, b, a, c, b, d, c, d ], F(1)) a*b*a*c*b*d*c*d """ def create_key(self, n, names): def create_object(self, version, key, **kwds):
FreeMonoid_factory = FreeMonoidFactory("sage.monoids.free_monoid.FreeMonoid_factory")
@rename_keyword(deprecation=15289, n="index_set") def FreeMonoid(index_set=None, names=None, commutative=False, **kwds): r""" Return a free monoid on `n` generators or with the generators indexed by a set `I`.
We construct free monoids by specifing either:
- the number of generators and/or the names of the generators - the indexing set for the generators
INPUT:
- ``index_set`` -- an indexing set for the generators; if an integer, than this becomes `\{0, 1, \ldots, n-1\}`
- ``names`` -- names of generators
- ``commutative`` -- (default: ``False``) whether the free monoid is commutative or not
OUTPUT:
A free monoid.
EXAMPLES::
sage: F.<a,b,c,d,e> = FreeMonoid(); F Free monoid on 5 generators (a, b, c, d, e) sage: FreeMonoid(index_set=ZZ) Free monoid indexed by Integer Ring
sage: F.<x,y,z> = FreeMonoid(abelian=True); F Free abelian monoid on 3 generators (x, y, z) sage: FreeMonoid(index_set=ZZ, commutative=True) Free abelian monoid indexed by Integer Ring
TESTS::
sage: FreeMonoid(index_set=ZZ, names='x,y,z') Free monoid indexed by Integer Ring """
names, index_set = index_set, names
index_set = names.count(',') else:
raise ValueError("names must be specified")
def is_FreeMonoid(x): """ Return True if `x` is a free monoid.
EXAMPLES::
sage: from sage.monoids.free_monoid import is_FreeMonoid sage: is_FreeMonoid(5) False sage: is_FreeMonoid(FreeMonoid(7,'a')) True sage: is_FreeMonoid(FreeAbelianMonoid(7,'a')) False sage: is_FreeMonoid(FreeAbelianMonoid(0,'')) False sage: is_FreeMonoid(FreeMonoid(index_set=ZZ)) True sage: is_FreeMonoid(FreeAbelianMonoid(index_set=ZZ)) False """
class FreeMonoid_class(Monoid_class): """ The free monoid on `n` generators. """ Element = FreeMonoidElement def __init__(self, n, names=None): """ Create free monoid on `n` generators.
INPUT:
- ``n`` - integer
- ``names`` - (optional) variable name or list of variable names
EXAMPLES::
sage: F = FreeMonoid(3,'x'); F Free monoid on 3 generators (x0, x1, x2) sage: x = F.gens() sage: x[0]*x[1]**5 * (x[0]*x[2]) x0*x1^5*x0*x2 sage: F = FreeMonoid(3, 'a') sage: F Free monoid on 3 generators (a0, a1, a2)
::
sage: M = FreeMonoid(3, names=['a','b','c']) sage: TestSuite(M).run() """ raise TypeError("n (=%s) must be an integer."%n) raise ValueError("n (=%s) must be nonnegative."%n) #self._assign_names(names)
def __eq__(self, other): """ Test for equality. """ return False
def __ne__(self, other): """ Test for unequality. """
def _repr_(self):
def _element_constructor_(self, x, check=True): """ Return ``x`` coerced into this free monoid.
One can create a free monoid element from the integer 1, from a list of 2-tuples of integers `(i,j)`, where `(i,j)` corresponds to `x_i^j`, where `x_i` is the `i`-th generator, and from words in the same alphabet as the generators.
EXAMPLES::
sage: F = FreeMonoid(3, 'a') sage: F(1) 1 sage: F(F.gen(0)) a0 sage: F(0) Traceback (most recent call last): ... TypeError: Argument x (= 0) is of the wrong type.
An example with a list::
sage: F([(0,5),(1,2),(0,10),(0,2),(1,2)]) a0^5*a1^2*a0^12*a1^2
An example using words::
sage: F = FreeMonoid(3, 'a,b,c') sage: w = Word('aabbcabac') sage: F(w) a^2*b^2*c*a*b*a*c sage: F(Word([])) 1 """ ## There should really some careful type checking here... return x return self.element_class(self,x._element_list,check)
def __contains__(self, x):
def gen(self,i=0): """ The `i`-th generator of the monoid.
INPUT:
- ``i`` - integer (default: 0)
EXAMPLES::
sage: F = FreeMonoid(3, 'a') sage: F.gen(1) a1 sage: F.gen(2) a2 sage: F.gen(5) Traceback (most recent call last): ... IndexError: Argument i (= 5) must be between 0 and 2. """
def ngens(self): """ The number of free generators of the monoid.
EXAMPLES::
sage: F = FreeMonoid(2005, 'a') sage: F.ngens() 2005 """
def cardinality(self): r""" Return the cardinality of ``self``, which is `\infty`.
EXAMPLES::
sage: F = FreeMonoid(2005, 'a') sage: F.cardinality() +Infinity """ from sage.rings.all import ZZ return ZZ.one()
|