posso abbreviare questa espressione regolare utilizzando l'intersezione?

Question

Ho questo linguaggio L che contiene solo una stringa: scritto in modo più conciso

Questa stringa ha 2 caratteri (2^n-1) e voglio ridurlo. Stavo pensando di usare l'intersezione, se riesco a trovare alcune lingue regolari in cui l'intersezione delle loro espressioni regolari produrrà questa stringa.

Ho qui la funzione ricorsiva nel caso che avrebbe aiutato:

function recursiveRegex(charset) { 
if(charset.length == 0) { 
    return []; 
} else { 
    var char = charset.splice(charset.length - 1, 1); 
    var returnVal = recursiveRegex(charset); 
    return returnVal.concat(returnVal) + char ; 
} 
} 

console.log(recursiveRegex(['a1', 'a2', 'a3', 'a4'])); 

Answer 1

Questo NON è un linguaggio regolare, quindi non è possibile trovare una grammatica regolare per definirlo.

Di conseguenza, non esiste un'espressione regolare per questa lingua.

A_1: a_1 

A_2: A_1 A_1 a_2 

A_3: A_2 A_2 a_3 

A_n: A_{n-1} A_{n-1} a_n 

Questa grammatica definisce la lingua e non è una grammatica regolare.

Una prova diretta che questa grammatica non definisce una lingua normale è che è necessario più di un numero costante di posizioni di memoria per definire la lingua. Per un dato N, è necessario un numero in base a N per mantenere la parola N.

---

Considerare ogni simbolo sinistro una posizione di memoria. Se vuoi renderlo regolare, dovresti avere un numero finito di regole. Se avete bisogno di farlo finito, dovrebbe essere fatto in modo da:

ATOM: a1

RULE_ {n + 1}: ATOM | RULE_n RULE_n a_ {n + 1}

Per creare correttamente questa lingua, è necessario un contatore, per sapere quale a_n inserire in ogni momento. Ma non è possibile creare segnalini di alcun tipo usando grammatiche regolari.