Estou trabalhando no problema do sistema MIU de "Gödel, Escher, Bach", capítulo 2.

Uma das regras afirma

Rule III: If III occurs in one of the strings in your collection, you may make a new string with U in place of III.

O que significa que a stringMIII pode se tornarMU, mas para outras strings mais longas, pode haver várias possibilidades [correspondências entre colchetes]:

MIIII poderia renderM[III]I >>MUIMI[III] >>MIUMUIIIUIIIU poderia renderMU[III]UIIIU >>MUUUIIIUMUIIIU[III]U >>MUIIIUUUMUIIIIU poderia renderMU[III]IU >>MUUIUMUI[III]U >>MUIUU

Expressões claramente regulares, como/(.*)III(.*)/ são úteis, mas não consigo fazer com que gerem todas as correspondências possíveis, apenas a primeira que acontece.

Existe uma maneira de gerar todas as correspondências possíveis?

(Note, eu posso pensar em maneiras de fazer isso inteiramente manualmente, mas eu espero que haja uma maneira melhor de usar as ferramentas internas, regex ou outras)

(Editado para esclarecer as necessidades sobrepostas)