*= s|S    <--- hijo izquierdo y derecho del nodo raíz.
s= t|T    <--- hijo izquierdo y derecho del nodo izquierdo de raíz
S= t|T    <--- hijo izquierdo y derecho del nodo derecho de raíz
t= r|R     // etc...
T= r|R
r= i|I
R= i|I
i= n|N
I= n|N
n= g|G
N= g|G
g=
G=

Estructura Nodo
    char Nombre 
    byte NumHijos
    arrayde Nodo Hijos()   // 2
    boleano Terminal
    entero Indice
Fin estructura

Array de nodo Nodos()

nodos(0).Nombre = "*"
nodos(0).NumHijos = 2
nodos(0).Hijos(0) =  nodos(1) // 's'
nodos(0).Hijos(1) =  nodos(2) // 'S'
nodos(0).Indice = 0
nodos(0).Terminal = FALSE

nodos(1).Nombre = "s"
nodos(1).NumHijos = 2
nodos(1).Hijos(0) =  nodos(3)  // 't'
nodos(1).Hijos(1) =  nodos(4)  // 'T'
nodos(1).Indice = 1
nodos(1).Terminal = FALSE

nodos(2).Nombre = "S"
nodos(2).NumHijos = 2
nodos(2).Hijos(0) =  nodos(3)  // 't'
nodos(2).Hijos(1) =  nodos(4)  // 'T'
nodos(2).Indice = 2
nodos(2).Terminal = FALSE
...
...
...

nodos(10).Nombre = "N"
nodos(10).NumHijos = 2
nodos(10).Hijos(0) =  nodos(11)  // 'g'
nodos(10).Hijos(1) =  nodos(12)  // 'G'
nodos(10).Indice = 10
nodos(10).Terminal = FALSE

nodos(11).Nombre = "g"
nodos(11).NumHijos = 0
nodos(11).Hijos // no dimensionado.
nodos(11).Indice = 11
nodos(11).Terminal = TRUE

nodos(12).Nombre = "G"
nodos(12).NumHijos = 0
nodos(12).Hijos // no dimensionado.
nodos(12).Indice = 12
nodos(12).Terminal = TRUE

Funcion Recorrer(nodo n, entero i, entero xWord, string parcial, array string Salida() )
    entero j, k

    bucle para k desde 0 hasta n.NumHijos-1
        j = n.Hijos(k).Indice
        
        parcial.Add( nodos(j).Nombre, i)         //añade el char de 'nodos(j).Nombre' en la posición 'i' del string 'parcial'
        i +=1
        
        Si (nodos(j).Terminal = TRUE)
            Salida(xWord) = parcial
            xWord +=1
        Sino
            Recorrer(nodos(j), i, xWord, parcial, Salida)
        fin si

        i -=1
        // estrictament esto no es necesario, ya que 'i' permitirá sobrescribir sin borrar el previo.
        parcial.Remove( i)     // elimina de parcial el char en la posición 'i' 
    Siguiente
Fin funcion

nodos(3).Hijos(0) =  nodos(?????)  // 'r'
nodos(3).Hijos(1) =  nodos(?????)  // 'R'

Array de String() = funcion CombinatoriaMayusMinus(string Palabra)
    entero sizeArray = (2 ^ palabra.size)
    array de String Salida(0 a sizeArray -1)
    string s = Palabra
    entero indexChar =0, indexWord =0


    Llamada a ParseEntrada(Palabra)
    Llamada a Recorrer(nodos(0), indexChar, indexWord , s, Salida)
    Devolver  Salida
fin funcion

Funcion ParseEntrada(string Palabra)
    entero k, j, i, n

    dimensionar nodos(0 a palabra.size * 2)    // esta declarado a nivel raiz (ver más arriba)
    
    nodo(0).Nombre = "*"    // <--- nodo raíz
    nodo(0).Indice = 0
    nodo(0).NumHijos = 2
    nodo(0).Terminal = False

    j = 0
    bucle para k desde 0 hasta palabra.Size -2  // la última letra es terminal y no tiene 'siguiente letra'
        j +=1
        nodo(j).Nombre = palabra.charAt(k).ToLower   //// <---- la minuscula
        nodo(j).Indice = j
        nodo(j).NumHijos = 2   ' porque es mayus y minus
        nodo(j).Terminal = False
        
        j +=1
        nodo(j).Nombre = palabra.charAt(k).ToUpper    // <---- la mayuscula
        nodo(j).Indice = j
        nodo(j).NumHijos = 2   ' porque es mayus y minus
        nodo(j).Terminal = False
    Siguiente

    j +=1
    nodo(j).Nombre = palabra.charAt(k).ToLower   //// <---- la minuscula
    nodo(j).Indice = j
    nodo(j).NumHijos = 0   
    nodo(j).Terminal = TRUE
        
    j +=1
    nodo(j).Nombre = palabra.charAt(k).ToUpper    // <---- la mayuscula
    nodo(j).Indice = j
    nodo(j).NumHijos = 0
    nodo(j).Terminal = TRUE

// -------------------- fin primera fase ----------------
   
    // Ahora falta asociar los hijos a cada nodo. 
    //    Siendo siempre solo 2 hijos es muy simple y no hace falta esta busqueda, es deducible 
    //    pero en casos con diferente número de hijos, tocará buscar...
    n = (j-2)
    bucle para k desde 0 hasta n
        bucle para i desde 0 hasta nodos(k).NumHijos -1
            j = BuscarNodo(... )  // <--- esta función y los parámetros que deba recibir, los dejo a tu esfuerzo
            // pero para la palabra 'string', para '*' buscamos nodo(?).nombre, donde nombre son  's' y 'S' (en cada ciclo)
            //    para 'R' buscamos 'i' e 'I', etc...
            nodos(k).Hijos(i) = nodos(j)
        Siguiente
    Siguiente

// -------------------- fin segunda fase ----------------
fin funcion