可以使用交集縮短此正則表達式嗎？

我有一個只包含一個字符串這種語言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直到 –

可以使用交集縮短此正則表達式嗎？

回答

相關問題