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']));

Vermillion

and what is your question ? – Intercede

Could you show us the grammar that uses intersection to describe your language? – Mainis

Assuming that you can use the intersection operator in your regular expressions. I want to shorten this regular expression by intersecting languages of different sorts using those n symbols to produce the string. – Vermillion

why you not set parameters of function as function f(begin,end) ? – Intercede

can you elaborate please – Vermillion

this doing what you need ? i not very good in math :), anyway you should get the idea – Intercede

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.

Baun

hmm, are you sure it's not. The language only contains that string. If you would be kind enough to provide your proof. I simply want a shorter way of describing this language using the standard operations (concatenation, union and Kleene star) and intersection to reduce the length of the string. – Vermillion

How does that grammar generates the string there is only two symbols there a1 and a2 while the string has a1 until an – Vermillion