Editing Free monoid (section)

== Free generators and rank ==
The members of a set ''A'' are called the '''free generators''' for ''A''<sup>&lowast;</sup> and ''A''<sup>+</sup>. The superscript * is then commonly understood to be the [[Kleene star]]. More generally, if ''S'' is an abstract free monoid (semigroup), then a set of elements which maps onto the set of single-letter words under an isomorphism to a monoid ''A''<sup>&lowast;</sup> (semigroup ''A<sup>+</sup>'') is called a ''set of free generators'' for ''S''.

Each free monoid (or semigroup) ''S'' has exactly one set of free generators, the [[cardinality]] of which is called the ''rank'' of ''S''.

Two free monoids or semigroups are isomorphic if and only if they have the same rank. In fact, ''every'' [[Monoid#Generators|set of generators]] for a free monoid or semigroup ''S'' contains the free generators, since a free generator has word length 1 and hence can only be generated by itself. It follows that a free semigroup or monoid is finitely generated if and only if it has finite rank.

A [[submonoid]] ''N'' of ''A''<sup>&lowast;</sup> is '''stable''' if ''u'', ''v'', ''ux'', ''xv'' in ''N'' together imply ''x'' in ''N''.<ref name=BPR61>{{harvtxt|Berstel|Perrin|Reutenauer|2010|p=61}}</ref>  A submonoid of ''A''<sup>&lowast;</sup> is stable if and only if it is free.<ref name=BPR62>{{harvtxt|Berstel|Perrin|Reutenauer|2010|p=62}}</ref>
For example, using the set of [[bit]]s { "0", "1" } as ''A'', the set ''N'' of all bit strings containing an even number of "1"s is a stable submonoid because if ''u'' contains an even number of "1"s, and ''ux'' as well, then ''x'' must contain an even number of "1"s, too. While ''N'' cannot be freely generated by any set of single bits, it ''can'' be freely generated by the set of bit strings { "0", "11", "101", "1001", "10001", ... } – the set of strings of the form "10<sup>''n''</sup>1" for some nonnegative integer ''n'' (along with the string "0").

===Codes===
A set of free generators for a free monoid ''P'' is referred to as a '''basis''' for '''P''': a set of words ''C'' is a '''code''' if ''C''* is a free monoid and ''C'' is a basis.<ref name=Lot5/>  A set ''X'' of words in ''A''<sup>&lowast;</sup> is a '''prefix''', or has the '''prefix property''', if it does not contain a proper [[prefix (computer science)|(string) prefix]] of any of its elements<!--- deleted, since "≤" as shorthand for "string prefix of" has not been defined yet, and is not used elsewhere in the article: that is, ''x'',''y'' in ''X'' with ''x'' ≤ ''y'' implies ''x'' = ''y''--->.  Every prefix in ''A''<sup>+</sup> is a code, indeed a [[prefix code]].<ref name=Lot5/><ref name=BPR58>{{harvtxt|Berstel|Perrin|Reutenauer|2010|p=58}}</ref>

A submonoid ''N'' of ''A''<sup>&lowast;</sup> is '''right unitary''' if ''x'', ''xy'' in ''N'' implies ''y'' in ''N''.  A submonoid is generated by a prefix if and only if it is right unitary.<ref name=Lot15>{{harvtxt|Lothaire|1997|p=15}}</ref>