# The Construction of Free Semigroups and their Elements

## Structure Constructors

### `FreeSemigroup(n): RngIntElt -> SgpFP`

Construct the free semigroup $F$ on $n$ generators, where $n$ is a positive integer. The $i$-th generator may be referenced by the expression `F.i`, $i = 1, \ldots, n$. Note that a special form of the assignment statement is provided which enables the user to assign names to the generators of $F$. In this form of assignment, the list of generator names is enclosed within angle brackets and appended to the variable name on the **left hand side** of the assignment statement.

### `FreeMonoid(n): RngIntElt -> MonFP`

Construct the free monoid $F$ on $n$ generators, where $n$ is a positive integer. The $i$-th generator may be referenced by the expression `F.i`, $i = 1, \ldots, n$. Note that a special form of the assignment statement is provided which enables the user to assign names to the generators of $F$. In this form of assignment, the list of generator names is enclosed within angle brackets and appended to the variable name on the **left hand side** of the assignment statement.

### `Example: Free Semigroup (ex-70a198)`

The statement

```magma
> F := FreeSemigroup(2);

```

creates the free semigroup on two generators. Here the generators may be referenced using the standard names, $F.1$ and $F.2$.

The statement

```magma
> F<x, y> := FreeSemigroup(2);

```

defines $F$ to be the free semigroup on two generators and assigns the names $x$ and $y$ to the generators.

## Element Constructors

Suppose $S$ is an fp-semigroup, not necessarily free, for which generators have already been defined. A *word* is defined inductively as follows:

**(i)**
A generator is a word;

**(ii)**
The product $uv$ of the words $u$ and $v$ is a word;

**(iii)**
The power of a word, $u^n$, where $u$ is a word and $n$ is an integer, is a word.

An element (word) of $S$ may be constructed as an expression in the generators as outlined below.

### `S ! [i₁, ... iₛ]: SgpFP, [RngIntElt] -> SgpFPElt`

Given a semigroup $S$ defined on $r$ generators and a sequence $Q = [i_1, \cdots, i_s]$ of integers lying in the range $[1, r]$, construct the word $G.{i_1} G.{i_2} \cdots G.{i_s}$.

### `Id(M): MonFP -> MonFPElt`

### `M ! 1: MonFP -> MonFPElt`

Construct the identity element (empty word) for the fp-monoid $M$.