grammar - 無制限の文法

Question

この一般的な文法は何をしますか?

S -> LR 
L -> L0Y 
L -> LX 
X1 -> 1X 
X0 -> 0X 
X0 -> 1Y 
Y1 -> 0Y 
YR -> R     
L  -> epsilon 
R  -> epsilon

開始記号は S です。この文法から文字列を生成しようとしたところ、すべての 2 進数が得られました。しかし、私はそれが何か特定のことをすると思います。

Answer 1

S -> LR 
L -> L0Y 
L -> LX 
X1 -> 1X 
X0 -> 0X 
X0 -> 1Y 
Y1 -> 0Y 
YR -> R     
L  -> epsilon 
R  -> epsilon

端子: 0,1 開始: S

文法を分割しましょう:

S -> LR 
L -> L0Y 
L -> LX

これにより、との文字列の形式Lで文字列が生成されます。X0YR

X1 -> 1X 
X0 -> 0X 
X0 -> 1Y 
Y1 -> 0Y 
YR -> R

XandYをバイナリ文字列に作用するものとして扱います:Xは右に伝搬し、a0を に変更し、1後続のすべての1s を0s に変更します。実際には、シングルXは、文字列の長さを変更せずに (またはスタックして)、2 進数をインクリメントします。

リーディングは、すべての s の文字列をすべての s にY書き換えます(またはスタックします)。10

L文字列の右側の可能なアクションとしてルールを扱います。L => L0Y文字列をすべて 1 からすべて 0 にリセットし、その長さを 1 増やします。L => LX他の数値を増やしますが、値が最大の場合は失敗します。

これら 2 つのアクションを組み合わせると、0 と 1 のすべての文字列 (空の文字列を含む) を (非効率的に) 生成するのに十分です。

L  -> epsilon 
R  -> epsilon

センチネルのみをクリーンアップします。

4 語以内の言語の 1 つの可能な説明:

すべての文字列のセット