問題タブ [context-free-grammar]

${...}または$someCommand{...}の形式の式も探しながら、主にリテラルテキスト（スペース、文字、記号など）を分析する文脈自由文法をどのように作成しますか？「今日は$10を手に入れました」と表示された場合は、特別なことは何もしないでください。

出来ますか？

文法をチョムスキー標準形に翻訳する練習をしようとしています。私は通常の状況でこれを行う方法を理解していますが、今回は私が使用している文法は正しい再帰的です。（技術的には、文法は前の質問に対する答えなので、ガンマが間違っている可能性があります。）

εルールの代わりに固定シーケンスのルールを使用することでこれを実行できると思いますが、間違った方向に向かっていないことを確認したいと思います。例を使って説明する方が簡単です。

nが0より大きく3の倍数であるn'aを生成する文法の場合:(心配しないでください。これは私の実際の文法とはまったく異なります）

正しい翻訳は次のようになりますか？

手始めに、これは宿題の質問です。アイデアはありますが、それでも正しい答えを得ることができません。私は答えを求めているのではなく、質問に答えるために助けを求めているだけです。

私は現在、その言語の文脈自由文法を書き込もうとしています。

したがって、基本的には、2の間にbとadの2倍のaがあります。次に例を示します。

これが私が持っているものについてです、私はあまり持っていません...私はこれらのCFGの概念を理解しています。私はこの質問の論理についてよくわかりません。私が正しい方向に進んでいるかどうかはわかりません...

ありがとう。

A が文脈自由でないことを示す必要があります。これには Pumping Lemma を使用する必要があると思いますが、どうすればよいでしょうか?

これは奇妙に聞こえるかもしれませんが、パーサーで使用されているので、フォームの何かを解析できるようにしたいと思います

foo [bar]

したがって、これはリストで次のように表されます。

[foo、[、bar、[]たぶんそのような単語はDCGで次のように書かれるでしょう：

問題は、角括弧が予約文字であるということです。それで、これをプロローグでどのように表すことができますか？

有限オートマトンのクラスを受講しています。中期的な準備をしていますが、特定の言語の文法を作成するのに問題があります。単純なものは非常に直感的ですが、より複雑になると、どこから始めればよいのかわからないようです。例えば：

L = {w E {a、b、c} *：nb（w）！= na（w）+ nc（w）}

答えは次のとおりです。

S→S1| S2S1
→bS3| S3b | S3bS3S3
→S0| S1S2
→XS4| S4X | S4XS4S4
→S| S2S0
→bS0XS0| XS0bS0 | eX→ a
| c

誰かが私に関係する思考プロセスについて少しのガイダンスを与えることができれば、それは大いにありがたいです。

私は{a^i b^j c^k | i,j,k>=0 & i>j & j>k} 、m文字列が

次に、文字列が空にならない(z =) uvwxyように分割され 、「」を選択すると混乱します。私が選ぶとしたら、私が持っているとしましょう： そして、私には言語にあるvwxを選ぶことができるように見えるので、そこからどこへ行くべきか完全にはわかりません。vx#(vwx)<=mii=1uv^1wx^1y

助言がありますか？

アルファベット：a、b、c私は受け入れるPDAを定義しようとしています

受け入れられる文字列は次のとおりです。＃abc＃; ＃aabbcc＃; ＃aaabbbccc＃; ＃abbccc＃; ＃aaabbc＃などa、b、cの数は必ずしも同じではありません。

一番右の黒いスペースでプッシュダウンオートマトンの頭を開始します。

通常、私はPDAを列に書き込みます。

等々...

アルファベット：0、1

各文字を反転する反転を考えてみましょう: 0 -> 1; 1 -> 0 したがって、w = 0011 の場合、w-flip = 1100

逆順は逆順の文字であると考えてください。したがって、w = 01101 の場合、w-reverse = 10110 です。

今、私は文字列 w を受け取り、w を印刷する PDA を作成しようとしています (w-flip-reversed)

したがって、これは次のように出力されます: "011001"

# はブランク文字と見なしてください。したがって、文字列は #011# で始まります

遷移表は次のようになります。

等々

何か案は？

文脈自由文法を Greibach Normal Form (GNF) に変換しています。主な変換 (Hopcroft & Ullman による) は、文法のインデックス付き変数に対する一連の反復です。それは本質的に「ステートレス」です。適切なインデックスに対する一連の折り畳みとして実装しました (実装はかなり簡単です)。

maxIndex rlは、一連のルール内の最大変数インデックスを返します。subst rl kjは、右辺がjインデックスの変数で始まるルールによって、 kインデックスのルールで置換を実行します。gnfを実行した後、逆の順序で文法の最終パスを実行する必要があります。

問題はnoLRで、左再帰のkインデックス規則で文法を変換します。noLRが適用されるルール (またはkインデックス付きルール)ごとに一意の変数を生成する必要があるため、これは「ステートフル」関数です。だから私はステートフル関数を書いた

noLRがパラメーターとして取るnを更新するために、 noLRを一緒にシーケンスすることができます。ただし、上記の関数のstep2内でnoLRを実行する方法がわかりません。ステートフルな計算がいくつかの再帰関数内に埋め込まれているため、スキーマでlet ...を使用できないようです。

私がやりたいのは、 nの明示的なスレッド化と同様に、 nを何らかのタイプのグローバル変数にすることです。これは、 step2内で呼び出して更新できます。これが、もともと関数をeta -expansion (for n）。この種の効果を達成するために状態モナド内でgnfを構造化する方法を知っている人はいますか? フォールド内の最後の計算を除いて、他に何も「ステートフル」ではありません。私は「些細な」例で状態モナドを使用することに慣れているだけです。私はむしろ迷っています。