L = {2^x * 2^y * 2^z = 2 ^（x + y + z）の文脈自由文法。 x、y、z> 0}

Question

タイトルが説明しています。私は "方程式"の左辺を右辺に同期させることに問題があります。なぜなら、左辺に2を生成するたびに、右辺に1つずつ表示する必要があるからです。この言語は文脈自由ではないのでしょうか？ ありがとうございます！

L = {2^x ∗ 2^y ∗ 2^z = 2^(x+y+z) | x, y, z > 0}

編集：これは、数学の方程式とは何の関係もありません。 「*」と「=」は、言語のアルファベットの単なる記号であり、2から「x」の累乗は、2がx回繰り返されていることを意味します。 乗算 文字列の連結と 累乗 繰り返しについての基本的な事実を使用して

Example of this language: 
222*2*22=222222 
2*2*2=222 
2*222222*22=222222222 

Answer 1

として、我々はあなたの言語を再定義することができます。

Lz = { 2^z = 2^z | z > 0 } 
Ly = { 2^y * w 2^y | y > 0, w ∈ Lz } 
Lx = { 2^x * w 2^x | x > 0, w ∈ Ly } 
L = Lx 

：この言語定義をさらにとして精緻化することができ

L = { 2^x * 2^y * 2^z = 2^z 2^y 2^x | x, y, z > 0 } 

次に、Lzの文法を定義できます。

Z ::= 2 = 2 
Z ::= 2 Z 2 

そしてLyのための1：

{ include Lz's grammar } 
Y ::= 2 * Z 2 
Y ::= 2 Y 2 

とLXのための1つ：

{ include Ly's grammar } 
X ::= 2 * Y 2 
X ::= 2 X 2 

Lので= LX、合成文法の開始シンボルはXである：

Answer 2

ここであり222*2*22=222222,2*2*2=222などの文脈自由文法の例です。

<literal>: 2 | <literal>2; 
<number>: <literal> | <number>*<number>; 
<expression>: <number>=<number>; 

これらのプロダクションでは、必要な文字列はすべて有効な<expression>です。それが問題だかどうか、あなたの質問から私には明らかではありません

22=2 

：「間違った」ある文字列は次のように、また文法的です。あなたのプロジェクトの最初のビジネスは、セマンティクスを心配することなく文字列を解析し、文法的な文字列のセマンティクスを評価することです。

編集：私は実際に私の答えに何か問題がありますかどうかを知るために好奇心が強いか、私はちょうど「私の芝生をオフのまま」downvoteを受け取った場合。

Answer 3

これ以上必要になることはありません。あなたの言語は次のような特徴があります

1. はRHSがちょうど2秒
ある =
3. 途中
にLHSが始まり、終了 2とし、 2 sおよび *秒を持っている途中に持っています
4. LHSとRHS上の2の数は等しい
5. LHSには**が含まれていません。

これらのルールは、文法に入れるのは簡単です：

(P1) S -> 2=2 
(P2) S -> 2S2 
(P3) S -> 2*S2 

最初のルールは、当社の基本ケースであると=は常にLHSとRHS分離しなければならないことを立証します。また、LHSは2で終わらなければならず、RHSは2で始まる必要があります。

第2および第3の規則は、2を追加して、言語でより長い文字列を取得できるようにします。 2番目のルールでは、「いつでも2をLHSの前面に置くことができます。そうした場合は、RHSの最後に1つ置く必要があります。 3番目のルールは、私たちがいる限り、我々はRHS」上に少なくとも1つのSを置くようLHSに*を配置することができます

あなたの例：。

222*2*22=222222 
S 
2S2     P2 
22S22     P2 
222*S222    P3 
222*2*S2222   P3 
222*2*2S22222   P2 
222*2*22=222222  P1 

2*2*2=222 
S     
2*S2     P2 
2*2*S22    P2 
2*2*2=222    P3 

2*222222*22=222222222 
S 
2*S2     P3 
2*2S22     P2 
2*22S222    P2 
2*222S2222    P2 
2*2222S22222   P2 
2*22222S222222   P2 
2*222222*S2222222  P3 
2*222222*2S22222222 P2 
2*222222*22=222222222 P1 

ことを示し伴うだろうこの文法のための形式的な正しさの証明（a）言語のすべての文字列が生成され、（2）生成されたすべての文字列が言語に含まれています。 、P1によって生成されます。短い文字列は生成されません。 誘導仮説：長さがk未満のすべての文字列が生成され、その言語で設定されていることを前提としています（これらの文字セットは長さが同じで、長さはkです）。 誘導ステップ：k以上の長さの文字列も一致している必要があります。長さがk以上の文字列（あるいは文法によって生成されたもの）の場合は、22x22または2*x2の形式である必要があります。xは別の文字列です（あるいは、文法によって生成されます）。 xの長さがkより小さいか、またはこの引数がx自体に再帰的に適用されます。 xは長さがk未満であるため、誘導仮説は文法によって生成されることができることを意味します（あるいは、それは言語内にあります）。 P2の2つのアプリケーションとP3の1つのアプリケーション（または、言語そのものの定義によって）によって、両方の形式を生成することができます（あるいは、言語でもあります）。

UPDATE：

コメントは*の数が2に固定されることになっていることを私の注意にしました。これには、文法の定義を変更する必要があります。

S -> 2S2 | 2*R2 
R -> 2R2 | 2*T2 
T -> 2T2 | 2=2 

これは、上記の議論を比較的軽微で予測可能な方法で変更します。基本的には、P3のアプリケーション数を追跡し、2回目以降のアプリケーションを許可しないで、同時に2つ以上のアプリケーションを見た後ですべての非終端点を排除することができます。