Két újabb függvény: H és E

Bonyolultabbá válik a helyzet, amikor a harmadik és a negyedik szabályt akarjuk alkalmazni: ezek produktívabbak az első kettőnél, hiszen adott esetben ugyanarra a szóra több helyen is alkalmazhatjuk őket. Ennek megfelelően a hozzájuk tartozó függvények több szót is visszaadhatnak az új listában.

def rule1(list, i):
    word= list[i]
    if word[-1]=='I':
        return [ word+'U' ]
    else:
        return []

def rule2(list, i):
    word= list[i]
    return [ word+word[1:] ]

def rule3(list, i):
    word= list[i]
    lisu= []
    for j in range(1, len(word)-2):
        if word[j:j+3]=='III':
            lisu+= [ word[:j]+'U'+word[j+3:] ]
    return lisu

def rule4(list, i):
    word= list[i]
    lisu= []
    for j in range(1, len(word)-1):
        if word[j:j+2]=='UU':
            lisu+= [ word[:j]+word[j+2:] ]
    return lisu

def rules(list, i):
    list+= rule1(list, i)
    list+= rule2(list, i)
    list+= rule3(list, i)
    list+= rule4(list, i)
    return list, i+1

i= 0
list= [ 'MI' ]
while i<11:
    list, i= rules(list, i)
print(list)

Az eredmény első látásra megnyugtató: egymás után sorakoznak a korábban látott fa szélességi bejárásával kapott szavak (a kimenet az áttekinthetőség kedvéért áttördelve):

[
 'MI',
 'MIU', 'MII',
 'MIUIU', 'MIIU', 'MIIII',
 'MIUIUIUIU', 'MIIUIIU', 'MIIIIU', 'MIIIIIIII', 'MUI', 'MIU',
 'MIUIUIUIUIUIUIUIU', 'MIIUIIUIIUIIU', 'MIIIIUIIIIU', 'MUIU', 'MIUU', …
 … 'MIIIIIIIIU', 'MIIIIIIIIIIIIIIII', 'MUIIIII', 'MIUIIII', 'MIIUIII', …
 … 'MIIIUII', 'MIIIIUI', 'MIIIIIU', 'MUIU', 'MUIUI'
]

A figyelmes szemlélőnek azonban feltűnik, hogy a fában (balról számolva) a MI utáni harmadik szintet öt szó alkotja, míg a fenti listában hat szerepel. Ennek oka hamar felfedezhető: a MIU szó a fenti listában kétszer szerepel – mert (legalábbis) kétféleképpen állítható elő.

Ez azt jelenti, hogy a nyelv szavai nem alkotnak fát: egyes szavakhoz több út is vezet (esetleg végtelen sok út is). Vagy fogalmazhatunk másképpen: ha az előállított szavakat fában rendezzük el, akkor egyes szavak többször is szerepelnek a fában (esetleg végtelen sokszor is).

Egyik perspektíva sem túlzottan szívderítő: módosítsuk úgy a programot, hogy ha egy szót ismételten előállítunk, akkor azt ne jegyezzük fel ismét…