さまざまなレベルのチョムスキー階層を理解しようとしています。
私はいくつかの例をチェックしましたが、ここに私が本当に理解していないものがあります。これが文脈依存言語ではない理由を誰かが知っているかもしれません:
S → aA
A → aA | ε
B → bA
1 に答える
0
あなたが提供する文法Gは、間違いなく文脈自由です (各ルールには、LHS に 1 つの非終端記号があり、RHS に終端記号と非終端記号の文字列があります)。したがって、Lそれが生成する言語は文脈自由です。したがって、文脈自由言語のカテゴリは文脈依存言語の適切なサブセットであるため、言語Lは文脈依存です。（あなたがどこでその言語を読んだかはわかりませんが、L文脈依存ではありません。あなたがこれを読み間違えたか、あなたが読んだものが単に間違っているかのどちらかです。）
この混乱の理由について推測してみます。文法 G( language Lではない) は文脈依存ではないと主張したとしましょう。さて、おそらく奇妙なことに、ある言語が文脈依存である場合、これはその言語を生成するすべての文法が文脈依存であるという意味ではありません(もちろん、制限のないものを除いて、他のカテゴリにも同じことが当てはまります)。言語が文脈依存である場合、これは、その言語を生成する文脈依存文法があることを意味します。したがって、状況依存であっても、L必ずしもそれGも状況依存であるとは限りません。
Gしかし、文脈自由文法である が文脈依存でなかったら奇妙です。これが真であるかどうかは、文脈依存文法の正確な定義に依存します。関連するウィキペディアの記事などで読めるように、文脈依存文法には少なくとも 2 つの代替定義があります。
- すべての規則が αAβ → αγβ の形式である文法。ここで、A は非終端記号であり、α、β、γ は終端と非終端の文字列です。
- すべての規則が α → β の形式である文法。ここで、α と β は終端と非終端の文字列ですが、α の長さは β の長さより大きくありません。例外として、開始シンボル S の規則 S → ε が存在する可能性があります (それ以外の場合は禁止されます)。
定義 1 によれば、文法Gは文脈依存です (文脈文字列 α と β は自明に空です)。ただし、定義 2 によればG、開始記号ではない非終端記号 A の生成規則が空であるため、文法はそうではありません。
G'ただし、両方の定義に従って文脈依存であり、同じ言語を生成する同等の文法を提供することは可能ですL。そのような文法の 1 つを次のように構成できます。
A は、0 個以上の "a" の文字列を生成します。その定義を次のように置き換えることができます。
A → A' | ε
A' → a | aA'
ここで、A' は 1 つ以上の "a" の文字列を生成します。A のルールは再帰的ではないことに注意してください。S と B のルールで A をプロダクションに置き換えて、非終端の A を削除できます。これにより、次のようになります。
S → aA' | a
A' → a | aA'
B → bA' | b
この文法 (A' と S が同じ言語を生成することに注意することでさらに単純化できます) は、上記の両方の定義に従って文脈依存です。
于 2016-03-30T23:17:26.323 に答える