6

私はこの言語Lを持っていますが、これには1つの文字列しか含まれていません： ここに画像の説明を入力してください より簡潔に書かれていますここに画像の説明を入力してください

この文字列は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応じた数が必要です。NN

左の各シンボルをメモリの場所と見なします。定期的にしたい場合は、有限数のルールを持つ必要があります。有限にする必要がある場合は、そうする必要があります。

アトム: a1

RULE_{n+1}: アトム | RULE_n RULE_n a_{n+1}

この言語を正しく作成するにはa_n、各瞬間に何を挿入するかを知るために counter が必要です。しかし、通常の文法を使用して、いかなる種類のカウンターも作成することはできません。

于 2012-12-13T20:11:37.190 に答える