4

そのため、解決できなかった文脈自由文法の問題が 1 つあります。成績とかではないので安心してください。

問題は次のようになります。

次のような文脈自由文法があります

S -> S1 | S2

S1 -> aS1B | B

S2 -> S2aB | B

B -> bS | b

タスクは、(任意のプログラミング言語で) 関数 count_words(n) を作成することです。関数は、この文脈自由言語に「含まれる」長さ「n」の単語の数を返す必要があります。

* count_words(3) で関数を呼び出したとしましょう。関数は、長さ 3 の可能な単語 (文脈自由言語内) の数を返す必要があります。つまり、bab、abb、aab などです。

誰でもそれで私を助けることができますか？まったくわかりません...難しいことではないと思いますが、正しい方法で考えるように強制することはできません。

4

1 に答える 1

2

文法をシミュレートする必要があります。a端子とが与えられた場合、b言語を受け入れるオートマトンを作成します。あなたが提示する文法は左再帰文法であるため、オプションはLRパーサーに似たプッシュダウンオートマトンを構築することです。結果の解析スタックを開始記号に減らすことができる場合、各記号プッシュの後、文字列は文法によって受け入れられます。希望の弦の長さになるまでこれを続けます。

基本的に、解析スタックを削減した後、可能なすべての入力を使用してシミュレートしようとするため、オートマトンをシミュレートして分岐します。

オートマトンを完全に構築することを避けることができ、与えられた各状態にどのルールがあるかを調べることができます。

于 2012-08-23T10:56:00.453 に答える