Pracuję nad problemem systemu MIU z rozdziału 2 „Gödel, Escher, Bach”.

Jedna z zasad mówi

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.

Co oznacza, że ​​strunaMIII może zostaćMU, ale dla innych, dłuższych ciągów może istnieć wiele możliwości [dopasowania w nawiasach]:

MIIII może się poddaćM[III]I >>MUIMI[III] >>MIUMUIIIUIIIU może się poddaćMU[III]UIIIU >>MUUUIIIUMUIIIU[III]U >>MUIIIUUUMUIIIIU może się poddaćMU[III]IU >>MUUIUMUI[III]U >>MUIUU

Wyraźnie regularne wyrażenia, takie jak/(.*)III(.*)/ są pomocne, ale nie mogę ich zmusić do wygenerowania każdego możliwego dopasowania, tylko pierwszego, które się zdarza.

Czy istnieje sposób na wygenerowanie każdego możliwego dopasowania?

(Zauważ, że mogę wymyślić sposoby na zrobienie tego całkowicie ręcznie, ale mam nadzieję, że jest lepszy sposób używania wbudowanych narzędzi, wyrażeń regularnych lub innych)

(Edytowane w celu wyjaśnienia nakładających się potrzeb.)