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.

class sage.monoids.free_monoid.FreeMonoid(n, names=None)[source]#

Bases: Monoid_class, UniqueRepresentation

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 \(n\), 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 = 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: 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

>>> from sage.all import *
>>> F = FreeMonoid(Integer(3),'x'); F
Free monoid on 3 generators (x0, x1, x2)
>>> x = F.gens()
>>> x[Integer(0)]*x[Integer(1)]**Integer(5) * (x[Integer(0)]*x[Integer(2)])
x0*x1^5*x0*x2
>>> F = FreeMonoid(Integer(3), 'a')
>>> F
Free monoid on 3 generators (a0, a1, a2)

>>> F = FreeMonoid(names=('a', 'b', 'c', 'd', 'e',)); (a, b, c, d, e,) = F._first_ngens(5); F
Free monoid on 5 generators (a, b, c, d, e)
>>> FreeMonoid(index_set=ZZ)
Free monoid indexed by Integer Ring

>>> F = FreeMonoid(abelian=True, names=('x', 'y', 'z',)); (x, y, z,) = F._first_ngens(3); F
Free abelian monoid on 3 generators (x, y, z)
>>> FreeMonoid(index_set=ZZ, commutative=True)
Free abelian monoid indexed by Integer Ring
Element[source]#

alias of FreeMonoidElement

cardinality()[source]#

Return the cardinality of self.

This is \(\infty\) if there is at least one generator.

EXAMPLES:

sage: F = FreeMonoid(2005, 'a')
sage: F.cardinality()
+Infinity

sage: F = FreeMonoid(0, [])
sage: F.cardinality()
1

>>> from sage.all import *
>>> F = FreeMonoid(Integer(2005), 'a')
>>> F.cardinality()
+Infinity

>>> F = FreeMonoid(Integer(0), [])
>>> F.cardinality()
1
gen(i=0)[source]#

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

>>> from sage.all import *
>>> F = FreeMonoid(Integer(3), 'a')
>>> F.gen(Integer(1))
a1
>>> F.gen(Integer(2))
a2
>>> F.gen(Integer(5))
Traceback (most recent call last):
...
IndexError: argument i (= 5) must be between 0 and 2
ngens()[source]#

The number of free generators of the monoid.

EXAMPLES:

sage: F = FreeMonoid(2005, 'a')
sage: F.ngens()
2005

>>> from sage.all import *
>>> F = FreeMonoid(Integer(2005), 'a')
>>> F.ngens()
2005
sage.monoids.free_monoid.is_FreeMonoid(x)[source]#

Return True if \(x\) is a free monoid.

EXAMPLES:

sage: from sage.monoids.free_monoid import is_FreeMonoid
sage: is_FreeMonoid(5)
doctest:warning...
DeprecationWarning: the function is_FreeMonoid is deprecated;
use 'isinstance(..., (FreeMonoid, IndexedFreeMonoid))' instead
See https://github.com/sagemath/sage/issues/37897 for details.
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

>>> from sage.all import *
>>> from sage.monoids.free_monoid import is_FreeMonoid
>>> is_FreeMonoid(Integer(5))
doctest:warning...
DeprecationWarning: the function is_FreeMonoid is deprecated;
use 'isinstance(..., (FreeMonoid, IndexedFreeMonoid))' instead
See https://github.com/sagemath/sage/issues/37897 for details.
False
>>> is_FreeMonoid(FreeMonoid(Integer(7),'a'))
True
>>> is_FreeMonoid(FreeAbelianMonoid(Integer(7),'a'))
False
>>> is_FreeMonoid(FreeAbelianMonoid(Integer(0),''))
False
>>> is_FreeMonoid(FreeMonoid(index_set=ZZ))
True
>>> is_FreeMonoid(FreeAbelianMonoid(index_set=ZZ))
False