1

入力文字列が特定の言語仕様に対して有効かどうかをチェックする関数を作成する必要があります。これは標準の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は非終端記号です。

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

XY -> PXY (and QXY, RXY)

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

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

XY-> PXY-> PPXY

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

4

1 に答える 1

3

私があなたの言っていることを誤解しない限り、この文法は文脈自由だと思います。

まず、Aを非終端記号とし、最初の2つのルールを使用して作成された有効な文字列に展開します。

A -> a | b | c | d | e | f

ここで、2番目のルールは、文字列ωを作成できる場合はSωを作成できることを示しています。それを次のようにエンコードできます

A -> SA

最後に、XとYの2つの文字列がある場合、それらを次のように組み合わせることができると言いました。

PXY
QXY
RXY

これについて考える1つの方法は、文字列Pを生成し、その後に任意の2つの有効な文字列（QまたはRで同じ）を生成することです。したがって、ルールを追加できます

A -> PAA | QAA | RAA

これにより、最終的な文法が得られます

A -> a | b | c | d | e | f
A -> SA
A -> PAA | QAA | RAA

お役に立てれば！

于 2012-05-07T03:16:42.327 に答える