問題タブ [context-sensitive-grammar]

チョムスキーのヒエラルキーでは、再帰言語のセットは定義されていません。再帰言語は再帰的に列挙可能な言語のサブセットであり、すべての再帰言語は決定可能であることを知っています。

私が興味を持っているのは、再帰言語が文脈依存言語とどのように比較されるかということです。文脈依存言語は再帰言語の厳密なサブセットであり、したがってすべての文脈依存言語は決定可能であると仮定できますか?

Terence Parr による Definitive ANTLR リファレンスを読んでいます。

セマンティック述語は、ランタイム情報が認識を駆動できるようにすることで、コンテキスト依存の言語構造を認識する強力な手段です。

しかし、この本の例は非常に単純です。私が知る必要があるのは、ANTLR は次のような状況依存のルールを解析できるかということです。

xAy --> xBy

ANTLR がこれらの規則を解析できない場合、文脈依存の文法を扱う別のツールはありますか?

この種の文法[文脈自由文法と文脈依存文法]が文字列を受け入れる理由を誰かが私に説明できますか？

私が知っているのは

文脈自由文法は、すべての生成（書き換え）規則がV→wの形式である形式文法です。ここで、Vは単一の非終端記号であり、wは終端記号および/または非終端記号の文字列です。wは空にすることができます

状況依存文法は、任意の生成（書き換え）ルールの左側と右側を終端記号と非終端記号のコンテキストで囲むことができる形式文法です。

しかし、これらの文法が文字列を受け入れる理由をどのように説明できますか？

私は文脈依存の補題をポンピングすることをグーグルで調べました、そしてそれは文脈自由言語の結果だけを生み出すようです。

補題をポンピングすることは、言語が文脈自由のみであることを証明することだけを可能にしますか？コンテキストに依存しませんか？

どのようにアイデアはありますか？

非決定性チューリングマシンを使用して、言語が状況依存であることをどのように示すことができますか？

線形拘束オートマトン（LBA）で受け入れられる言語は、状況依存言語であることを私は知っています。また、LBAは非決定性チューリングマシンです。

これらすべてをどのように関連付けて、言語が状況依存であることを示すことができますか？

私は、チョムスキーによって設定された4つのレベルの形式文法（無制限、文脈依存、文脈自由、通常）のわかりやすい（つまり、非形式的な）説明を見つけようとしています。

形式文法を勉強してからもう少し経ちましたが、今ではいろいろな定義がわかりづらいです。明確にするために、私はあなたがどこにでもある正式な定義を探していません（例えばこことここ-私は他の誰と同じようにグーグルできます）、あるいは実際にはどんな種類の正式な定義さえも探していません。代わりに、私が見つけたいと思っていたのは、完全性のために明快さを犠牲にしない、クリーンでシンプルな説明でした。

言語 X = { m = 2n+1 で n >= 0 となる 0^m}

X の文脈依存文法を見つけるのを手伝ってくれる人はいますか? 私は何年も努力してきましたが、まだ近くにはいません。

私が今持っているもの：

S -> B0C|00

B0 -> DD0|00

BD -> DD

0C -> 0EE|00

EC -> EE

D -> B

E -> C

しかし、これはうまくいきません。ゼロの数を 2 倍にする方法がわかりません。

入力文字列が特定の言語仕様に対して有効かどうかをチェックする関数を作成する必要があります。これは標準のCFG->チョムスキー標準形、次にCYK解析になると思いましたが、言語の規則の1つは、これが起こらないようにすることです。

いくつかのルールは単純です。端末を定義する{a,b,c,d,e,f,P,Q,R,S}と、有効な文字列は次のようになります。

1）分離された小文字の端子のいずれか
2）'x'が有効な文字列である場合、Sxも有効です。

しかし、3番目のルールは

3）XとYが有効な入力文字列である場合、PXY、QXY、RXYも有効です。

ここで{P,Q,R}、は残りの大文字の終端記号であり、XとYは非終端記号です。

このための制作ルールはどのようになりますか？こんな感じになると思いました

しかし、これには2つの問題があります。1つ目は、これはCFG規則ではないということです。つまり、この言語は代わりにCSGを定義するということですか？

そして2つ目は、これが機能しないことです。

XY-> PXY-> PPXY

すべての場合に有効なメッセージではありません。

重複の可能性:
文脈依存文法と文脈自由文法

私の教科書では、これら2つの用語の説明は次のとおりです。

文脈依存文法:

文法は、w1 → w2 の形式の生成を持つことができます。ここで、w1 = lAr および w2 = lwr です。ここで、A は非終端記号であり、l および r は 0 個以上の終端または非終端記号の文字列であり、w は終端または非終端記号の空でない文字列です。非終端記号。また、S が他のプロダクションの右辺に現れない限り、プロダクション S → λ を持つこともできます。

文脈自由文法:

文法は、w1 → w2 の形式の生成のみを持つことができます。ここで、w1 は、終端記号ではない単一の記号です。タイプ 3 文法は、w1 = A および w2 = aB または w2 = a (A と B が非終端記号で a が終端記号)、または w1 = S と w2 = λ。

私の教科書では、著者は次のように述べています。 CSG は CFG の特殊なケースです。しかし、私はこの点を理解していません。CSGでは、lAr -> lwrだからです。l と r は、0個以上の終端または非終端の文字列にすることができます。つまり、ゼロの文字列の場合 (長さ = 0 を意味します)。lAr を A と書くことができます。したがって、CSG は CFG になります。だから、CSGはCFGです

私が理解していることは間違っていますか？私のためにそれを修正してください。

ありがとう ：）

プログラムされた文法を解析するために使用される解析アルゴリズムが何であるかを知りたいです。プログラムされた文法について読むことができるリンク、ブログ、またはIEEEの研究論文以外のアルゴリズムを解析するものはありますか?