A Lyndon word is a word lexicographically smaller than all of its proper right factors; see http://katlas.math.toronto.edu/drorbn/bbs/show?shot=Chu-071214-182203.jpg

LyndonQ[w_String] := And @@ (
OrderedQ[{w, #}]& /@ Table[StringDrop[w,i], {i,1,StringLength[w]-1}]
);
AllWords[0, _List] = {""};
AllWords[n_ /; n>0, ab_List] := AllWords[n, ab] = Flatten[Outer[
StringJoin[#1, #2]&,
AllWords[n-1, ab],
ab
]];
AllLyndonWords[n_, ab_List] := Select[AllWords[n, ab], LyndonQ]

LyndonQ["abba"]

LyndonQ["ababb"]

AllWords[1, {"1", "2"}]

AllWords[3, {"1", "2"}]

AllLyndonWords[3, {"1", "2"}]

Table[Length[AllLyndonWords[k, {"1", "2"}]], {k,10}]

Table[Length[AllLyndonWords[k, {"1", "2", "3"}]], {k,8}]

LyndonToLie[w_String /; StringLength[w]==1] := w;
LyndonToLie[w_String /; StringLength[w] > 1] := Module[
{rf},
rf=First[Sort[Table[StringDrop[w,i], {i,1,StringLength[w]-1}]]];
LyndonToLie /@ b[StringDrop[w, -StringLength[rf]], rf]
]

LyndonToLie["12122"] // TreeForm