6

我有这种语言 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']));
4

1 回答 1

3

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

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

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保留第Nth 单词的数字。

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

原子：a1

RULE_{n+1}：原子 | RULE_n RULE_n a_{n+1}

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

于 2012-12-13T20:11:37.190 回答