can I shorten this regular expression using intersection?

Question

I have this language L that contains only one string: written more concisely

This string has 2(2^n−1) characters and I want to reduce it. I was thinking of using intersection, if i can find some regular languages in which the intersection of their regular expressions will yield this string.

I have here the recursive function in case that would help:

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

This is NOT a regular language, so you cannot find a regular grammar to define it.

Consequently, there is no regular expression for this language.

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

This grammar defines your language and it is not a regular grammar.

A direct proof that this grammar does not define a regular language is that one needs more than a constant number of locations of memory to define the language. For a given N, one needs a number depending on N to keep the Nth word .

---

Consider each left symbol a location of memory. If you want to make it regular, you should have a finite number of rules. If you need to make it finite, it should be done so:

ATOM: a1

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

To create correctly this language, you would need a counter , in order to know what a_n to insert at each moment. But it is not possible to create counters of any kind using regular grammars.