可以使用交集缩短此正则表达式吗？

我有一个只包含一个字符串这种语言L： enter image description here 写更简洁可以使用交集缩短此正则表达式吗？

此字符串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']));

来源

2012-12-13 Jiyda Moussa

和你的问题是什么？ –

你能告诉我们使用交集来描述你的语言的语法吗？ – Bergi

假设您可以在正则表达式中使用交点运算符。我想通过使用这n个符号来交叉不同类型的语言来生成字符串来缩短这个正则表达式。 –

这不是一个普通的语言，所以你不能找到一个正规的语法来定义它。

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

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这个词。

考虑每个左边的符号的内存位置。如果你想使它规则化，你应该有一个有限数量的规则。如果你需要使它有限的，应该这样做：

ATOM：A1

RULE_ {N + 1}：ATOM | RULE_n RULE_n a_ {n + 1}

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

来源

2012-12-13 20:11:37 alinsoar

嗯，你确定它不是。该语言只包含该字符串。如果你愿意提供你的证明。我只是想要使用标准操作（连接，联合和Kleene星形）和交集来描述此语言的较短方式，以减少字符串的长度。 –

该语法如何生成字符串，其中只有两个符号a1和a2，而字符串具有a1直到 –

可以使用交集缩短此正则表达式吗？

回答

相关问题