É porque você está usando \d com * .
Quando você tem [a-z]|\d* , ele primeiro tentará corresponder a a-z . Caso contrário, tentará corresponder a 0 ou mais repetições de um dígito. No seu exemplo, ele corresponderá a a primeiro.
No entanto, ao contrário, ele tentará primeiro corresponder a 0 ou mais repetições de um dígito. Bem, a é 0 repetições de um dígito, então ele se qualifica como 'correspondência'. Ele não tentará avaliar a expressão [a-z] , já que ela está qualificada para 0 repetições.
Para usar este padrão adequadamente (especialmente se tiver para ser uma letra ou pelo menos um dígito), você poderia usar:
[a-z]|\d+ ou \d+|[a-z]
Isso procuraria por 1 ou mais repetições de um dígito, não corresponderia em a e, em seguida, avaliaria [a-z] , resultando na resposta esperada.