我可以用交集缩短这个正则表达式吗？

Question

我有这种语言L只包含一个字符串: 写得更简洁

这个字符串有2(2 ^ n-1)个字符,我想减少它.我正在考虑使用交集,如果我能找到一些常规语言,其正则表达式的交集将产生这个字符串.

我在这里有递归函数,以防有助于:

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

这不是常规语言，因此您无法找到常规语法来定义它。

因此，该语言没有正则表达式。

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

该语法定义了您的语言，它不是常规语法。

该语法没有定义常规语言的直接证据是，需要超过恒定数量的内存位置来定义该语言。对于给定的情况N，需要一个数字来N保留第N一个单词。

将每个左边的符号视为一个内存位置。如果你想让它变得有规律，你应该有有限数量的规则。如果你需要使其有限，应该这样做：

原子：a1

规则_{n+1}：原子| 规则_n 规则_n a_{n+1}

要正确创建这种语言，您需要一个计数器，以便知道a_n每个时刻要插入什么。但不可能使用常规语法创建任何类型的计数器。